시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 1024 MB | 212 | 60 | 51 | 33.333% |
드디어 HI-ARC의 첫 MT가 시작되었다. HI-ARC의 운영진들은 재밌는 의자 게임을 준비하였다. 방 안에는 $1$번, $2$번, $\dots$, $N$번 의자가 순서대로 놓여있다. 즉, 가장 오른쪽에 있는 $N$번 의자를 제외하면, $i$번 의자의 오른쪽에는 $i+1$번 의자가 있다. 각 의자에는 $N$명의 참가자가 앉아있으며, 모든 참가자는 $1$ 이상 $N$ 이하의 정수인 등번호를 부여받았다. 등번호는 같을 수도 있다.
게임은 우승자가 나오기 전까지 다음의 순서대로 규칙에 따라 진행된다.
하지만 이럴 수가! 게임이 진행되던 도중, 운영진들은 이 게임이 영원히 끝나지 않을 수도 있다는 것을 깨달았다. 운영진들은 참가자를 슬쩍 추가하여 이 문제를 해결하려 한다. 규칙 2번에서 규칙 1번으로 돌아가기 전, 원한다면 아래의 방식대로 참가자를 한 명 추가할 수 있다.
운영진들은 게임의 흥을 깨지 않기 위해 최소한의 참가자만을 추가하고 싶다. 게임이 언젠가는 끝나게 하기 위해서, 운영진들은 최소 몇 명의 참가자를 추가해야 할까?
다음과 같이 입력이 주어진다.
$N\ K$
$a_1\ a_2\,\dots\ a_N$
게임이 유한한 시간 내에 끝나기 위해서 추가해야 하는 최소 인원수를 출력한다.
3 3 3 1 2
0
$\require{extpfeil}\Newextarrow{\xRightarrow}{5,5}{0x21D2}$$[3, 1, 2]$ $\xRightarrow[\textsf{규칙 $1$}]{}$ $[2, 3, 1]$ $\xRightarrow[\textsf{규칙 $1$}]{}$ $[1, 2, 3]$
규칙 2로 인해, $[\underline{1, 2, 3}]$ 이 승리한다.
4 3 1 4 4 4
2
$\require{extpfeil}\Newextarrow{\xRightarrow}{5,5}{0x21D2}$$[1, 4, 4, 4]$ $\xRightarrow[\textsf{규칙 $1$}]{}$ $[4, 1, 4, 4]$ $\xRightarrow[\textsf{$2$ 추가}]{}$ $[4, 1, 4, 4, 2]$ $\xRightarrow[\textsf{규칙 $1$}]{}$ $[2, 4, 1, 4, 4]$ $\xRightarrow[\textsf{$3$ 추가}]{}$ $[2, 4, 1, 4, 4, 3]$ $\xRightarrow[\textsf{규칙 $1$}]{}$ $[3, 2, 4, 1, 4, 4]$ $\xRightarrow[\textsf{규칙 $1$}]{}$ $[4, 3, 2, 4, 1, 4]$
규칙 2로 인해, $[4, \underline{3, 2, 4}, 1, 4]$ 이 승리한다.
University > 신촌지역 대학생 프로그래밍 대회 동아리 연합 > 2021 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2021 Winter) J번