50109. H-index

I'm a slow walker, but I never walk backwards.

Write a program to compute h-index for scholars.

Task Description

The h-index is an author-level metric that attempts to measure both the productivity and citation impact of the publications of a scholar. The definition of the index is that a scholar with an index of $h$ has published $h$ papers each of which has been cited in other papers at least $h$ times. You are given many papers, each of them has scholar name and the number of times it was cited, now you need to compute the h-index for each scholar and print them in alphabetic (dictionary) order according to the names of scholars.

For example, if Tom with $5$ publications with $5$, $3$, $10$, $8$, and $4$ citations, respectively, the h-index is four because Tom has four papers each of which has been cited at least four times, but he does not have five papers each of which has been cited five times.

Subtask

  • 10 points: There is only one scholar and all papers have the same number of citations.
  • 30 points: There is only one scholar and his papers may have different numbers of citations. You need to use qsort() or you might get TLE.
  • 70 points: Nothing is guaranteed. You need to use qsort() or you might get TLE.

Input Format

The input contains only one test case. Each line has a string indicating the scholar name ($\textit{length} \lt 16$), and a non-negative integer indicating the number of times this paper was cited. You need to process all inputs until $EOF$. There will be no more than $20000$ papers.

Output Format

Print the names and h-indices of scholars in alphabetic (dictionary) order.

Sample Input 1

Tom 3
Tom 3
Tom 3
Tom 3
Tom 3

Sample Output 1

Tom 3

Sample Input 2

Tom 5
Tom 3
Tom 10
Tom 8
Tom 4

Sample Output 2

Tom 4

Sample Input 3

Morris 10
Tom 0
John 2
John 25
Morris 2
Morris 8

Sample Output 3

John 2
Morris 2
Tom 0

Note

Use the following algorithm to compute the H-index. Put all papers into an array and sort it, so that the papers from the same scholar will be together, and sorted in decreasing number of citation order. For example, the input of sample input 3 will be as follows.

John 25
John 2
Morris 10
Morris 8
Morris 2
Tom 0

Now all papers of Morris will be put together and have citations $\lbrace 10, 8, 2\rbrace $. We then check the first number of citations to see if it is at least $1$, if so then the H-index is at least $1$. In the example it is so we try the second step. Now we check the second number to see if it is at least $2$. If so then the H-index is at least $2$, so we check the third number. However, the third number is $2$, which is less than $3$, so we conclude that the h-Index for Morris is $2$.

Discussion