Bob's Rocks

View as PDF

Submit solution

All submissions

Best submissions

Points: 5

Time limit: 1.0s

Memory limit: 128M

Authors:

maxcruickshanks, feliser

Problem type

After dealing with his $n$ $n$ rocks for too long, Bob decides to pawn some of them off: he will pawn off the most valuable group of rocks, valued by their age in years. In accordance with the buyers, Bob can only sell rocks of the same age.

Since Bob is busy dealing with the buyers, he wants you to tell him which age of rocks to sell!

Input Specification

The first line of input will contain $n$ $n$ $(1 \le n \le 1\,000\,000)$ $(1 \leq n \leq 1 000 000)$ , the total number of rocks.

The second line will contain $n$ $n$ integers $(0 \le A_i \le 50)$ $(0 \leq A_{i} \leq 50)$ , representing the age, in years, of each rock.

Output Specification

The age of the rocks Bob should sell to maximize his revenue.

Note: It is guaranteed that there is only $1$ $1$ maximal answer.

Sample Input 1

Copy

10
1 5 9 0 3 10 3 9 3 2

Sample Output 1

Copy

Explanation for Sample Output 1

Bob has rocks of $7$ $7$ distinct ages: $0, 1, 2, 3, 5, 9, 10$ $0, 1, 2, 3, 5, 9, 10$ . Out of these ages, he can sell $2$ $2$ rocks of age $9$ $9$ for a total of $18$ $18$ dollars $(2 \times 9 = 18)$ $(2 \times 9 = 18)$ ; the second-best age would be $10$ $10$ for a total of $10$ $10$ dollars $(1 \times 10 = 10)$ $(1 \times 10 = 10)$ .

Comments

9

yeerk16 commented on Jan. 27, 2021, 9:55 p.m.

Neat little problem for intro to time complexity.

I gotta find a way to use this somewhere. Thank you!