Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ
Slovak University of Technology
University of Zilina
cz
Masaryk University
University of West Bohemia
CTU Open Contest 2017
Dark Ride with Monsters
monsters.c, monsters.cpp, monsters.c11, Monsters.java, monsters.py
A narrow gauge train drives the visitors through the sequence of chambers in the Dark Ride
attraction. The chambers are occupied by IT monsters which are specially programmed to scare
the visitors in various wicked ways. There is one monster in each chamber. For strange and
obscure reasons, some of the monsters might have been installed in wrong chambers. The task of
Freddie and Morcia, who themselves are employees and not monsters, is to reinstall the monsters
in the correct chambers.
To avoid any additional confusion or threat, Freddie and Morcia work in episodes. In one
episode, they choose two distinct chambers. Freddie picks the monster in one of the chambers
and transports it to other chamber, while Morcia picks the monster in the other chamber and
transports it to the chamber from which Freddie has just picked his monster. Thus, Freddie and
Morcia effectively swap the monsters in two chambers during one episode. After some number
of episodes, all monsters should be placed in correct chambers. Swapping monsters is a tedious
task. Quite understandably, Freddie and Morcia want to minimize the number of episodes.
Input Specification
There are more test cases. Each test case consists of two lines. The first line contains one integer
N (1 ≤ N ≤ 2 · 105 ) specifying the number of chambers. The chambers are labeled 1, 2, . . . , N
and also the monsters are labeled 1, 2, . . . , N . The label of each chamber should coincide with
the label of a monster correctly installed in it. The second line contains N labels of the monsters
which are currently installed in the chambers. The monster denoted by the first label on the line
is installed in the chamber 1, the monster denoted by the second label on the line is installed in
the chamber 2, etc.
Output Specification
For each test case, print a single line with one integer denoting the minimum number of episodes
required to install the monsters in correct chambers.
Sample Input
3
12
3
5
54
321
5
54
123
4
43
12
6
56
3412
10
98
10 5 3 2 4 7 6 1
Output for Sample Input
0
2
3
3
2
9
