34134번 - [Y] 새로운 요세푸스 문제 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 103 | 24 | 12 | 24.000% |
문제
평화로운 삶을 살던 하이히는 어느 날 갑자기 바이비의 새로운 요세푸스 게임에 참가하게 되었다! 새로운 요세푸스 게임은 다음과 같이 진행된다.
- 게임이 시작하기 전, 양의 정수 $M$이 정해진다.
- $1$번 참가자부터 $N$번 참가자까지 시계 방향으로 차례로 원을 그리며 앉는다.
- 시작할 때는 화살표를 $N$번 참가자를 가리키도록 놓는다.
- 이후 모든 사람이 탈락할 때까지 다음 과정을 반복한다.
- $1$ 이상 $M$ 이하의 정수 $K$가 정해진다. 이 수는 이전과 같을 수도, 다를 수도 있다.
- 화살표를 시계 방향으로 $K$번 돌린다. 이때, 탈락한 참가자의 자리는 건너뛴다.
- 이후 화살표가 가리키는 참가자가 탈락한다. 이로 인해 화살표가 돌아가지는 않는다.
예로, 다음은 $N = 7$, $M = 10$일 때 가능한 새로운 요세푸스 게임의 진행 과정이다.
원래라면 어디에 있어야 탈락하지 않고 끝까지 남을 수 있을지 궁금해하는 것이 일반적이지만, 호기심에 가득 찬 하이히는 사람들이 탈락한 순서가 주어질 때 $K$가 최소 몇 번 달라졌는지 구해보기로 했다!
입력
첫째 줄에는 참가자의 수 $N$과 정해지는 수의 최댓값 $M$이 공백으로 구분되어 주어진다. $(1\le N\le 200\, 000;$ $1\le M\le 10^9)$
둘째 줄에는 참가자들의 번호 $A_1,A_2,\ldots ,A_N$이 탈���한 순서대로 공백으로 구분되어 주어진다. $(1\le A_i\le N;$ $A_i\neq A_j\text{ iff } i\neq j)$
실제로 참가자가 해당 순서대로 탈락할 수 있는 입력만이 주어진다.
출력
첫째 줄에 게임이 진행되면서 $K$가 최소 몇 번 달라졌는지 출력한다. $K$를 처음 정하는 것은 $K$가 달라지는 것으로 세지 않는다.
예제 입력 1
7 10 6 5 3 4 2 7 1
예제 출력 1
1
예제 입력 2
7 3 3 6 2 7 5 1 4
예제 출력 2
0
출처
- 문제를 만든 사람: hibye1217
- 문제를 검수한 사람: minjunnick, mujigae, pyb1031, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호