지루한 카드 게임

시간 제한1초메모리 제한128 MB

요약
정해진 규칙으로 카드를 나누고 다시 모으는 과정을 반복해서 1~5번 카드를 처음으로 모두 갖는 플레이어와 게임 번호를 찾거나 무한 반복을 판정합니다.
난이도

보통10점 중 7점

유형
시뮬레이션, 수학, 구현
정답자
아직 제출이 없습니다

문제

닐 스티븐슨의 소설 크립토노미콘에는 트럼프 카드 한 벌을 기반으로 하는 암호 알고리즘이 등장하며, 암호의 안전성을 위해서는 카드를 제대로 섞는 것이 매우 중요하다고 강조한다. 무작위성이 왜 중요한지 보이기 위해, 여기서는 카드를 전혀 섞지 않아 결과를 완전히 예측할 수 있는 카드 게임을 살펴본다.

이 게임은 포커를 단순하게 바꾼 것으로, 모든 카드가 모두에게 공개되어 있고 참가자들은 게임 진행에 전혀 영향을 줄 수 없다. 꽤 지루하지 않은가?

한 세션은 하나 이상의 게임으로 이루어지며 NN명이 참가한다. 참가자들은 한 줄로 앉아 왼쪽부터 오른쪽으로 1,2,…,N1, 2, \ldots, N번을 부여받는다. 카드 더미에는 1,2,…,5N1, 2, \ldots, 5N의 번호가 매겨진 정확히 5N5N장의 카드가 있다.

각 게임은 세 번의 라운드로 카드를 나누며 시작한다.

  • 1라운드: 왼쪽에서 오른쪽 순서로 각 참가자에게 두 장씩 나눠 준다. 1번 참가자가 맨 위 두 장을, 2번 참가자가 그다음 두 장을 받는 식으로 NN번 참가자까지 진행한다.
  • 2라운드: 같은 과정을 한 번 더 반복하여 모든 참가자가 두 장씩 더 받는다.
  • 3라운드: 모든 참가자가 마지막으로 한 장씩 더 받는다.

따라서 각 참가자는 다섯 장의 카드를 갖게 된다. 가장 작은 번호의 다섯 장(1,2,3,4,51, 2, 3, 4, 5, 순서는 상관없다)을 모두 갖게 된 참가자가 세션 전체의 승자가 된다.

아무도 이기지 못하면 카드를 모아 새 게임을 시작한다. 카드는 오른쪽에서 왼쪽으로 참가자 순서대로 걷으며, 한 참가자의 카드는 항상 나눠 받은 순서의 역순으로 한 장씩 걷는다. 걷은 카드는 더미 맨 위에 올려놓고 그다음 카드를 그 위에 올리는 식으로 쌓는다. 그 결과 새로 만들어진 더미의 위쪽에는 1번 참가자의 카드가 오며, 맨 위 여섯 장은 직전 더미에서 1,2,2N+1,2N+2,4N+1,31, 2, 2N+1, 2N+2, 4N+1, 3번째에 있던 카드들이 된다.

예를 들어 참가자가 두 명이면 처음 더미에는 열 장의 카드 A,B,C,D,E,F,G,H,I,JA, B, C, D, E, F, G, H, I, J가 있다. 1라운드에서 1번 참가자는 AA와 BB를, 2번 참가자는 CC와 DD를 받는다. 이어서 EE와 FF는 1번 참가자에게, GG와 HH는 2번 참가자에게 가고, 마지막으로 II는 1번 참가자에게, JJ는 2번 참가자에게 간다. 카드를 걷을 때는 먼저 2번 참가자의 카드가 J,H,G,D,CJ, H, G, D, C 순서로, 이어서 1번 참가자의 카드가 I,F,E,B,AI, F, E, B, A 순서로 걷힌다. 각 카드를 이전 카드 위에 쌓으므로, 한 게임이 끝난 뒤 더미는 위에서 아래로 A,B,E,F,I,C,D,G,H,JA, B, E, F, I, C, D, G, H, J가 된다.

한 세션의 결과를 알려 주는, 그리하여 참가자들의 게임 결과를 미리 알려 줄 수 있는 프로그램을 작성하라.

입력

입력에는 여러 개의 세션이 들어 있다. 각 세션은 두 줄로 주어진다. 첫 줄에는 1≤N≤10001 \le N \le 1000을 만족하는 정수 NN이 있다. 둘째 줄에는 카드 번호 1,2,…,5N1, 2, \ldots, 5N이 더미의 위에서 아래 순서로 한 칸의 공백으로 구분되어 나열되며, 각 번호는 정확히 한 번씩 나타난다. 마지막 세션 뒤에는 00 하나만 있는 줄이 온다.

출력

각 세션마다 정확히 한 줄을 출력한다. 아무도 이기지 못하면 Neverending game.을 출력하고, 그렇지 않으면 Player P wins game number G.를 출력한다. 여기서 PP는 이긴 참가자의 번호, GG는 처음으로 승부가 난 게임의 번호이다(게임은 1번부터 센다). GG는 2322^{32}을 넘을 수 있지만 항상 2632^{63}보다 작다.

예제7

  1. 예제 1

    입력
    2
    2 3 9 7 4 8 5 1 10 6
    2
    2 6 9 7 4 8 5 1 10 3
    5
    16 12 18 11 20 15 19 24 8 6 25 1 7 22 14 2 3 10 13 17 4 5 21 9 23
    0
    
    예상 출력
    Player 1 wins game number 3.
    Neverending game.
    Player 2 wins game number 153.
    
  2. 예제 2

    입력
    1
    1 2 3 4 5
    0
    
    예상 출력
    Player 1 wins game number 1.
    
  3. 예제 3

    입력
    1
    5 4 3 2 1
    0
    
    예상 출력
    Player 1 wins game number 1.
    
  4. 예제 4

    입력
    2
    2 3 9 7 4 8 5 1 10 6
    0
    
    예상 출력
    Player 1 wins game number 3.
    
  5. 예제 5

    입력
    2
    2 6 9 7 4 8 5 1 10 3
    0
    
    예상 출력
    Neverending game.
    
  6. 예제 6

    입력
    3
    15 7 5 1 13 11 3 12 10 4 14 2 8 6 9
    0
    
    예상 출력
    Player 2 wins game number 6.
    
  7. 예제 7

    입력
    4
    12 14 19 13 10 7 11 17 9 20 6 18 8 15 16 4 3 2 1 5
    0
    
    예상 출력
    Player 4 wins game number 28.