COCI 2016/2017 - Contest 6 - Hindeks

View as PDF

Submit solution

Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 128M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 6
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Làm thế nào để ta đánh giá sự thành công của một nhà khoa học? Bằng số lượng bài báo xuất bản hay bằng tầm ảnh hưởng (số lần được trích dẫn) của nhà khoa học đó? Cả 2 yếu tố đều quan trọng. Chúng ta nói một bài báo khoa học có điểm trích dẫn là ~C~ nếu như nó được trích dẫn trong những bài báo của các nhà khoa học khác tổng cộng ~C~ lần. Một trong những chỉ số đánh giá sự thành công của các nhà khoa học là h-index. Chỉ số này cân nhắc cả số lượng bài báo và số điểm trích dẫn của họ.

h-index của một nhà khoa học được định nghĩa là số ~H~ lớn nhất thỏa mãn điều kiện: nhà khoa học có thể chọn ~H~ bài báo của mình mà điểm trích dẫn của mỗi bài báo ít nhất là ~H~. Ví dụ, nếu một nhà khoa học viết ~10~ bài báo và cả ~10~ bài đều được trích dẫn ít nhất ~10~ lần, thì h-index của nhà khoa học đó ít nhất là ~10~.

Viết chương trình nhận vào điểm trích dẫn của tất cả các bài báo của một nhà khoa học và in ra h-index của nhà khoa học đó.

Input

Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 5 \cdot 10^5)~, số bài báo mà một nhà khoa học đã viết

Dòng tiếp theo chứa ~N~ số nguyên không âm không quá ~10^6~, điểm trích dẫn của mỗi bài báo mà nhà khoa học đó viết.

Output

In ra một số nguyên duy nhất là h-index của nhà khoa học.

Sample 1

Input
5
1 1 4 8 1
Output
2
Giải thích

Nhà khoa học có ~2~ bài báo với điểm trích dẫn lớn hơn hoặc bằng ~2~ (các bài báo với điểm trích dẫn lần lượt là ~4~ và ~8~)

Sample 2

Input
5
8 5 3 4 10
Output
4
Giải thích

Nhà khoa học có ~4~ bài báo với điểm trích dẫn lớn hơn hoặc bằng ~4~ (các bài báo với điểm trích dẫn lần lượt là ~8~, ~5~, ~4~, ~10~)


Comments

Please read the guidelines before commenting.