2009 Bulgarian Olympiad in Informatics
Task 2: Money-boxen
The programmer Pesho is a very thrifty person. The money which he earns from web-site design he stores in N money boxen (1 ≤ N ≤ 100,000), labeled by the integers from 1 to N. The intention of Pesho is to buy a new super-computer. In order to avoid the temptation to spend the money for rubbis, before the necessary sum is collected, he dropped all keys of the money-boxen in a random way inside the boxen themselves.
Fortunately, Pesho marked on a list of paper where the key for each money-box is stored. Now, the necessary money is finally collected and Pesho has to open all the money-boxen to take the money.
Unfortunately, no keys are available: Pesho must break the boxen! Pesho doesn't like breaking things, so he'd like to break as few boxen as possible. He realized that when a broken money-box contains a key of another money-box then the second money-box could be simply unlocked.
Write a program to determine the minimal number of money-boxen that have to be broken in order to collect all the stored money.
InputThe program has to solve two test cases for each run. Each test case starts with a line containing the number N of money-boxen. Then N lines follow with one integer from 1 to N - on the ith line is the box in which the key for the ith box is stored.
OutputOutput the minimal number of boxen that must be broken.
Separate the numbers with a space.
4 2 1 2 4 3 3 3 3
In the first test case the 4th box must be broken, because it contains its own key. Then, you can simply break the 1st box - it contains the key for box 2, which contains the key for box 3.
In the second case, you can just break box 3 to enter everything.
Point Value: 20
Time Limit: 1.00s
Memory Limit: 32M
Added: May 10, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3