TWOEARRAY

Xem PDF
Tác giả:
Small
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho 2 dãy số nguyên \(A, B\) đều gồm \(N\) phần tử. Ban đầu tất cả các phần tử của dãy \(A\) đều bằng 0.

Bạn cần biến dãy \(A\) thành dãy \(B\) bằng cách thực hiện nhiều lần thao tác sau: chọn ra \(K\) phần tử của dãy \(A\) và tăng mỗi phần tử thêm 1 đơn vi.

Yêu cầu Kiểm tra xem có thể biến dãy \(A\) thành dãy \(B\) được hay không?

Input

  • Dòng đầu tiên chứa số nguyên \(T\) là số bộ thử nghiệm. Mỗi bộ thử nghiệm gồm 2 dòng, dòng đầu chứa 2 số nguyên dương \(N\) và \(K\), dòng thứ 2 chứa dãy \(B\).

Output

  • Với mỗi bộ thử nghiệm, in kết quả ra 1 dòng, in YES nếu dãy \(A\) có thể biến thành dãy \(B\) và NO nếu ngược lại.

Constants

  • \(T < 1000\).
  • \(K < N < 10^5\).
  • \(B[i] < 10^9\).
  • Tổng \(N\) trong tất cả bộ thử nghiệm không quá \(10^6\).

Example

Test 1

Input 
2
5 3
1 2 3 4 5
3 2
1 1 4
Output 
YES
NO
Note
  • Ở test ví dụ 1, ta có thể thực hiện biến đổi như sau:
    • \(A = 0, 0, 0, 0, 0, B = 1, 2, 3, 4, 5\);
    • Chọn 3 chỉ số \(1, 2, 5 \rightarrow A = 1, 1, 0, 0, 1\); 
    • Chọn 3 chỉ số \(2, 4, 5 \rightarrow A= 1, 2, 0, 1, 2\);
    • Chọn 3 chỉ số \(3, 4, 5 \rightarrow A= 1, 2, 1, 2, 3\);
    • Chọn 3 chỉ số \(3, 4, 5 \rightarrow A= 1, 2, 2, 3, 4\);
    • Chọn 3 chỉ số \(3, 4, 5 \rightarrow A= 1, 2, 3, 4, 5\);
    • Như vậy ta có thể biến đổi dãy \(A\) thành dãy \(B\) sau 5 thao tác như trên.

Bình luận

Không có bình luận nào.