Nội dung Bài tập
- Mã:
- MAXMINA
- Tên:
- Maxmina
- Dạng thi:
- acm
- Thang điểm:
- 1 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Nguồn bài tập:
- Codeforces
- Link nguồn:
- https://codeforces.com/co...
- Được tạo bởi:
- 4801104016
MAXMINA
Bạn có một mảng a gồm n phần tử chứa các số hoặc 0 hoặc 1 và một số nguyên k. Với mỗi thao tác, bạn có thể thực hiện một trong các thao tác dưới đây:
+> Chọn 2 phần tử liên tiếp của a và thay thế bằng phần tử nhỏ nhất trong hai phần tử đó (có nghĩa là, thay
a:=[a1,a2,…,ai−1,min(ai,ai+1),ai+2,…,an] thỏa 1 ≤ i ≤ n−1). Thao tác này sẽ giảm kích cỡ của mảng a đi 1 đơn vị.
+> Chọn k phần tử liên tiếp của a và thay thế bằng phần tử lớn nhất trong các phần tử đó (có nghĩa là, thay
a:=[a1,a2,…,ai−1,max(ai,ai+1,…,ai+k−1),ai+k,…,an] thỏa 1 ≤ i ≤ n−k+1). Thao tác sẽ này giảm kích cỡ của mảng a đi k−1 đơn vị.
Kiểm tra xem có thể nào biến mảng a thành [1] sau một số (hoặc là 0) thao tác như trên hay không.
Input
Mỗi test bao gồm nhiều testcase. Dòng đầu là số lượng testcase t (1 ≤ t ≤ 1000). Mỗi testcase đều được trình bày như sau.
Dòng đầu tiên của mỗi testcase gồm hai số nguyên n và k (2 ≤ k ≤ n ≤ 50), là kích cỡ của mảng a và chiều dài của đoạn con mà bạn có thể thực hiện thao tác loại hai.
Dòng thứ hai gồm n số nguyên a1,a2,…,an (ai là 0 hoặc 1), các phần tử của mảng a.
Output
Với mỗi testcase, nếu có thể biến a thành [1], viết "YES", còn không thì viết "NO".
Ví dụ:
Input
Output
7
3 2
0 1 0
5 3
1 0 1 1 0
2 2
1 1
4 4
0 0 0 0
6 3
0 0 1 0 0 1
7 5
1 1 1 1 1 1 1
5 3
0 0 1 0 0
YES
YES
YES
NO
YES
YES
YES
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...