COCI '16 Contest 6 #1 H-indeks

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

How do we evaluate the success of a scientist? By the number of published papers or by their impact - more precisely, the number of citations? Both elements matter. We say that a scientific paper has a citation score C if other scientists cited the paper in question in their paper (referred to it) a total of C times. One of the possible metrics of the success of scientists is their h-index that takes into account both the amount of papers and their citation scores.

A scientist's h-index is defined as the largest number H with the following properties: the scientist can choose H papers such that their citation score is at least H. For example, if a scientist wrote 10 papers such that each of them has been cited 10 or more times, their h-index is (at least) 10.

Write a programme that inputs the citation scores of all papers of a given scientist and outputs their h-index.

Input Specification

The first line of input contains the positive integer N (1 \leq N \leq 500\,000), the number of papers of a given scientist.

The following line contains N non-negative integers from the interval [0, 1\,000\,000], the citation scores of the respective papers.

Output Specification

The first and only line of output must contain the required h-index.

Sample Input 1

5
1 1 4 8 1

Sample Output 1

2

Explanation for Sample Output 1

The scientist has two papers with citation scores larger than or equal to 2 (the papers with citation scores 4 and 8).

Sample Input 2

5
8 5 3 4 10

Sample Output 2

4

Explanation for Sample Output 2

The scientist has four papers with citation scores larger than or equal to 4 (the papers with citation scores 8, 5, 4 and 10).


Comments

There are no comments at the moment.