Thứ Bảy, 30 tháng 7, 2016

Drumpf for President!


Donald Drumpf đã dành toàn bộ thời gian mùa hè để vận động tranh cử cho cuộc tuyển chọn hội đồng sinh viên. Ở trường đại học của anh ta, có tất cả N sinh viên. Mỗi sinh viên trong trường bỏ một phiếu. Số lượng sinh viên trong hội đồng được xác định bằng số lượng sinh viên nhận được ít nhất K phiếu bầu.
Mỗi người nhận được ít nhất K phiếu sẽ có một ghế trong hội đồng sinh viên. Trưởng khoa để ý thấy mỗi năm, có một số sinh viên tự bỏ phiếu cho mình. Ông đã quyết định thêm luật để loại bỏ những cá nhân tự bỏ phiếu cho chính mình tức là họ sẽ không được vào hội đồng sinh viên.
Bạn được cho một mảng A, với Ai thể hiện người mà sinh viên thứ i bỏ phiếu cho. Bạn có thể tính được hội đồng sinh viên có bao nhiêu người không?
Dữ liệu vào:
·       Dòng đầu tiên chứa một số nguyên T – số lượng test.
·       Với mỗi test, dòng đầu tiên chứa 2 số nguyên N, K.
·       Dòng thứ hai của mỗi test chứa N số thể hiện mảng A, với số thứ iAi.
Dữ liệu ra:
·       Với mỗi test, in ra một dòng duy nhất chứa một số nguyên tương ứng với số người trong hội đồng sinh viên.
Ràng buộc:
·       1 T 100
·       1 K N
Subtasks
Subtask #1: (30 điểm)
·       1 N 3
Subtask #2: (70 điểm)
·       1 N 100
Ví dụ:
Input
2
3 2
2 1 2
2 1
1 2
Output
1
0
Giải thích:
Trong test đầu tiên, có 3 học sinh. Một học sinh nhật được ít nhất 2 phiếu bầu sẽ được tham gia vào hội đồng sinh viên. Sinh viên 1 bỏ phiếu cho sinh viên 2, sinh viên 2 bỏ phiếu cho sinh viên 1, sinh viên 3 bỏ phiếu cho sinh viên 2. Do đó, sinh viên 2 nhận được 2 phiếu bầu và là người duy nhất đủ điều kiện vào hội đồng sinh viên. 
Trong test thứ hai, mặc dù cả hai học sinh đều nhận được đủ số phiếu yêu cầu, tuy nhiên họ bị loại vì tự bỏ phiếu cho mình. Vì vậy, số người trong hội đồng sinh viên là 0