USACO 2021 - Open - Silver - Acowdemia

View as PDF

Submit solution

Points: 0.10 (partial)
Time limit: 0.5s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=1136
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cô bò Bessie đã tham gia khóa học đào tạo Tiến sĩ ngành Khoa học máy tính với niềm đam mê Tin học và ước mơ trở thành tiến sĩ. Trong thời gian nghiên cứu hàn lâm, Bessie đã xuất bản ~N~ bài nghiên cứu ~(1 \le N \le 10^5)~ và bài nghiên cứu thứ ~i~ đã được trích dẫn ~c_i~ ~(0 \le c_i \le 10^5)~ lần từ những bài nghiên cứu khác trong giới nghiên cứu.

Bessie biết rằng sự thành công của một giảng viên được tính bằng chỉ số ~h~ của họ. Chỉ số ~h~ được định nghĩa là số ~h~ lớn nhất sao cho giảng viên đó có ít nhất ~h~ bài nghiên cứu, mỗi bài có ít nhất ~h~ lần trích dẫn. Ví dụ, một giảng viên có ~4~ bài nghiên cứu và lượng trích dẫn là ~(1, 100, 2, 3)~ có chỉ số ~h~ là ~2~, còn nếu lượng trích dẫn là ~(1, 100, 3, 3)~ thì chỉ số ~h~ của người đó là ~3~.

Để tăng chỉ số ~h~ của cô ấy, Bessie dự định sẽ viết tối đa ~K~ ~(0 \le K \le 10^5)~ bài báo, mỗi bài trích dẫn một số bài nghiên cứu của cô. Tuy nhiên, bởi vì số lượng trang có hạn, Bessie chỉ có thể trích dẫn tối đa ~L~ ~(0 \le L \le 10^5)~ bài nghiên cứu trong một bài báo. Đương nhiên, một bài báo không thể trích dẫn một bài nghiên cứu nhiều lần (nhưng một bài nghiên cứu có thể được trích dẫn bởi nhiều bài báo).

Hãy giúp Bessie xác định chỉ số ~h~ lớn nhất mà cô ấy có thể đạt được sau khi viết các bài báo này. Trong một bài báo của cô, Bessie không được phép trích dẫn các bài báo khác.

Input

Dòng đầu tiên chứa ~3~ số nguyên ~N~, ~K~ và ~L~.

Dòng thứ hai chứa ~N~ số nguyên ~c_1, c_2, \ldots, c_N~ cách nhau bởi một dấu cách.

Output

In ra chỉ số ~h~ cao nhất Bessie có thể đạt được.

Sample Input 1

4 4 1
1 100 1 1

Sample Output 1

3

Giải thích: Trong ví dụ này, Bessie có thể viết tối đa ~4~ bài báo, mỗi bài trích dẫn tối đa ~1~ bài nghiên cứu. Nếu Bessie trích dẫn bài nghiên cứu thứ nhất hai lần và bài nghiên cứu thứ ba hai lần, thì chỉ số ~h~ của cô sẽ trở thành ~3~.

Sample Input 2

4 1 4
1 100 1 1

Sample Output 1

2

Giải thích: Trong ví dụ này, Bessie có thể viết tối đa ~1~ bài báo, trích dẫn tối đa ~4~ bài nghiên cứu. Nếu Bessie trích dẫn một trong ba bài nghiên cứu thứ nhất, thứ ba hay thứ tư thì chỉ số ~h~ của cô sẽ trở thành ~2~.

Ràng buộc

  • Các test 1-6 thỏa mãn ~N \le 100~.
  • Các test 7-16 không có thêm ràng buộc nào.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.