Học bổng

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài

Cuối học kỳ, Phòng Công tác sinh viên xét học bổng khuyến khích học tập cho một khoa có ~n~ sinh viên; sinh viên thứ ~i~ có điểm xét học bổng là số nguyên ~a_i~. Nhà trường dự kiến cấp ~k~ suất và xét theo quy trình sau:

  • Sắp xếp điểm của cả ~n~ sinh viên theo thứ tự từ cao xuống thấp. Gọi ~c~ là điểm đứng ở vị trí thứ ~k~ trong dãy đã sắp xếp;
  • Mọi sinh viên có điểm lớn hơn hoặc bằng ~c~ đều được đưa vào danh sách xét. Như vậy những sinh viên đồng điểm với người đứng thứ ~k~ cũng được xét, và danh sách xét có thể có nhiều hơn ~k~ người;
  • Trong danh sách xét, chỉ những sinh viên có điểm lớn hơn hoặc bằng điểm sàn ~T~ mới được nhận học bổng.

Yêu cầu

Hãy cho biết có bao nhiêu sinh viên được nhận học bổng.

Dữ liệu vào

  • Dòng thứ nhất chứa ba số nguyên ~n~, ~k~ và ~T~;
  • Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~.

Kết quả ra

Ghi ra một số nguyên duy nhất là số sinh viên được nhận học bổng.

Ràng buộc

~1 \le k \le n \le 10^5~; ~0 \le T \le 1000~; ~0 \le a_i \le 1000~.

  • Subtask 1 (30% số điểm – test 01–06): ~n \le 100~ và các điểm đôi một khác nhau;
  • Subtask 2 (30% số điểm – test 07–12): ~n \le 5000~;
  • Subtask 3 (40% số điểm – test 13–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1
7 3 800
850 920 780 850 600 850 990
Kết quả ra mẫu 1
5
Dữ liệu vào mẫu 2
7 3 900
850 920 780 850 600 850 990
Kết quả ra mẫu 2
2

Giải thích

Dãy điểm sau khi sắp xếp là ~990, 920, 850, 850, 850, 780, 600~; điểm đứng ở vị trí thứ ~3~ là ~c = 850~, nên danh sách xét gồm ~5~ sinh viên có điểm ~990, 920, 850, 850, 850~.

Ở ví dụ thứ nhất, điểm sàn là ~800~: cả ~5~ sinh viên trong danh sách xét đều đạt. Ở ví dụ thứ hai, điểm sàn là ~900~: chỉ hai sinh viên có điểm ~990~ và ~920~ được nhận.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.