RiseOJ – 소들의 셔플

설명

행복한 소가 더 많은 우유를 만든다고 확신한 농부 존은 헛간에 거대한 디스코 볼을 설치하고 소들에게 춤을 가르치기로 했다!

인기 있는 소 춤들을 찾아본 농부 존은 소들에게 "소들의 셔플(Bovine Shuffle)"을 가르치기로 했다. 소들의 셔플은 $$N$$ 마리의 소 ( $1 \leq N \leq 100,000$ )가 어떤 순서로 한 줄로 선 다음, "셔플"을 연속으로 수행하는 춤으로, 각 셔플마다 소들의 순서가 바뀔 수 있다. 소들이 자기 위치를 쉽게 찾을 수 있도록, 농부 존은 줄의 위치를 $1 \ldots N$ 으로 표시해 두었다. 즉, 줄의 첫 번째 소는 위치 1에, 다음 소는 위치 2에, 이런 식으로 위치 $$N$$ 까지 서게 된다.

셔플은 $$N$$ 개의 수 $a_1 \ldots a_N$ 으로 표현되며, 셔플 동안 위치 $$i$$ 에 있는 소는 위치 $$a_i$$ 로 이동한다 (따라서 각 $$a_i$$ 는 $1 \ldots N$ 범위이다). 셔플 동안 모든 소는 자신의 새 위치로 이동한다. 안타깝게도 모든 $$a_i$$ 가 반드시 서로 다르지는 않으므로, 셔플 동안 여러 소가 같은 위치로 이동하려 할 수 있으며, 그 이후에는 남은 모든 셔플 동안 함께 이동하게 된다.

농부 존은 셔플을 아무리 많이 수행해도 항상 소가 있는 위치들이 있다는 것을 알아차렸다. 그러한 위치의 개수를 세는 것을 도와주자.

Problem credits: Brian Dean

제약

Problem credits: Brian Dean

입력 형식

입력의 첫째 줄에 소의 수 $$N$$ 이 주어진다. 다음 줄에 $$N$$ 개의 정수 $a_1 \ldots a_N$ 이 주어진다.

출력 형식

셔플을 아무리 많이 수행해도 항상 소가 있는 위치의 개수를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 shuffle.in · 출력을 쓸 파일 shuffle.out

예제 1

입력

4
3 2 1 3

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2017-2018 > December > Silver

올림피아드 > USACO > 2017-2018 > December > Silver

태그

JudgeUSACO

소들의 셔플

평가 및 의견

풀이 제출