Mock CCC '15 J3 - Problem-setting Pandemonium

View as PDF

Submit solution

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

Problem type
2015 Mock CCC by Alex and Timothy

You are planning to run N (1 \le N \le 100) programming contests in the next few weeks, but you quickly realized that you've bitten off more than you can chew. As a novice problem-setter, you quickly learned that the rumours are true. Indeed, original and interesting problems are really hard to write.

Fortunately, you're not alone in your contest-writing endeavours. Your friend is there with you. However, you know deep down that in order to be credited for helping create the contest, you just need to supply a single problem for it. You know that your friend will take care of the rest, even if it means he'll be very angry for having to do all the remaining work.

The contests are numbered from 1 to N. Both of you have agreed that in the i^{th} (1 \le i \le N) contest, you must contribute a problem of difficulty level D_i (1 \le D_i \le 1000). You don't want to do a lot of work, so you want to create as few problems as possible to get the job done. Your master plan is to repeat problems when multiple contests require problems of the same difficulty. Surely, nobody will notice.

Since you will focus solely on making problems for the next few days (who needs to eat or sleep?), you are able to make an original problem of any difficulty level if you try hard enough. What is the minimum number of original problems that you'll need to write for the N contests?

Input Specification

Line 1 of input will contain a single integer N, representing the number of contests you're responsible for.
Line 2 of input will contain N space-separated integers D_1, D_2, \dots, D_N, the difficulty levels of the problems you have to contribute for the contests.

Output Specification

The first and only line of output should consist of a single integer, the minimum number of problems you have to write to be able to supply a problem for all the contests.

Sample Input 1

1 2 3 4 6

Sample Output 1


Explanation for Sample 1

Unfortunately, you can't slack off — all contests will need their own new problem!

Sample Input 2

3 2 2 1 3 3

Sample Output 2


Explanation for Sample 2

You only need to make 3 different problems — one with difficulty 1, one with difficulty 2, and one with difficulty 3.