지루한 카드 게임
시간 제한1초메모리 제한128 MB
정해진 규칙으로 카드를 나누고 다시 모으는 과정을 반복해서 1~5번 카드를 처음으로 모두 갖는 플레이어와 게임 번호를 찾거나 무한 반복을 판정합니다.
문제
닐 스티븐슨의 소설 크립토노미콘에는 트럼프 카드 한 벌을 기반으로 하는 암호 알고리즘이 등장하며, 암호의 안전성을 위해서는 카드를 제대로 섞는 것이 매우 중요하다고 강조한다. 무작위성이 왜 중요한지 보이기 위해, 여기서는 카드를 전혀 섞지 않아 결과를 완전히 예측할 수 있는 카드 게임을 살펴본다.
이 게임은 포커를 단순하게 바꾼 것으로, 모든 카드가 모두에게 공개되어 있고 참가자들은 게임 진행에 전혀 영향을 줄 수 없다. 꽤 지루하지 않은가?
한 세션은 하나 이상의 게임으로 이루어지며 명이 참가한다. 참가자들은 한 줄로 앉아 왼쪽부터 오른쪽으로 번을 부여받는다. 카드 더미에는 의 번호가 매겨진 정확히 장의 카드가 있다.
각 게임은 세 번의 라운드로 카드를 나누며 시작한다.
- 1라운드: 왼쪽에서 오른쪽 순서로 각 참가자에게 두 장씩 나눠 준다. 1번 참가자가 맨 위 두 장을, 2번 참가자가 그다음 두 장을 받는 식으로 번 참가자까지 진행한다.
- 2라운드: 같은 과정을 한 번 더 반복하여 모든 참가자가 두 장씩 더 받는다.
- 3라운드: 모든 참가자가 마지막으로 한 장씩 더 받는다.
따라서 각 참가자는 다섯 장의 카드를 갖게 된다. 가장 작은 번호의 다섯 장(, 순서는 상관없다)을 모두 갖게 된 참가자가 세션 전체의 승자가 된다.
아무도 이기지 못하면 카드를 모아 새 게임을 시작한다. 카드는 오른쪽에서 왼쪽으로 참가자 순서대로 걷으며, 한 참가자의 카드는 항상 나눠 받은 순서의 역순으로 한 장씩 걷는다. 걷은 카드는 더미 맨 위에 올려놓고 그다음 카드를 그 위에 올리는 식으로 쌓는다. 그 결과 새로 만들어진 더미의 위쪽에는 1번 참가자의 카드가 오며, 맨 위 여섯 장은 직전 더미에서 번째에 있던 카드들이 된다.
예를 들어 참가자가 두 명이면 처음 더미에는 열 장의 카드 가 있다. 1라운드에서 1번 참가자는 와 를, 2번 참가자는 와 를 받는다. 이어서 와 는 1번 참가자에게, 와 는 2번 참가자에게 가고, 마지막으로 는 1번 참가자에게, 는 2번 참가자에게 간다. 카드를 걷을 때는 먼저 2번 참가자의 카드가 순서로, 이어서 1번 참가자의 카드가 순서로 걷힌다. 각 카드를 이전 카드 위에 쌓으므로, 한 게임이 끝난 뒤 더미는 위에서 아래로 가 된다.
한 세션의 결과를 알려 주는, 그리하여 참가자들의 게임 결과를 미리 알려 줄 수 있는 프로그램을 작성하라.
입력
입력에는 여러 개의 세션이 들어 있다. 각 세션은 두 줄로 주어진다. 첫 줄에는 을 만족하는 정수 이 있다. 둘째 줄에는 카드 번호 이 더미의 위에서 아래 순서로 한 칸의 공백으로 구분되어 나열되며, 각 번호는 정확히 한 번씩 나타난다. 마지막 세션 뒤에는 하나만 있는 줄이 온다.
출력
각 세션마다 정확히 한 줄을 출력한다. 아무도 이기지 못하면 Neverending game.을 출력하고, 그렇지 않으면 Player P wins game number G.를 출력한다. 여기서 는 이긴 참가자의 번호, 는 처음으로 승부가 난 게임의 번호이다(게임은 1번부터 센다). 는 을 넘을 수 있지만 항상 보다 작다.