2015 Mock CCC by Alex and Timothy
Problem J3: Problem-setting Pandemonium (Junior)
You are planning to run N (1 ≤ N ≤ 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 endeavors. 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 contest are numbered from 1 to N. Both of you have agreed that in the i-th (1 ≤ i ≤ N) contest, you must contribute a problem of difficulty level Di (1 ≤ Di ≤ 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?
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 D1, D2, …, DN, the difficulty levels of the problems you have to contribute for the contests.
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
5 1 2 3 4 6
Sample Input 2
Explanation of Sample 1
Unfortunately, you can't slack off – all contests will need their own unique problem!
Sample Input 2
6 3 2 2 1 3 3
Sample Output 2
Explanation of Sample 2
You only need to make 3 different problems – one with difficulty 1, one with difficulty 2, and one with difficulty 3.
Point Value: 5
Time Limit: 1.00s
Memory Limit: 64M
Added: Feb 18, 2015
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3