숫자 게임

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

요약
2부터 20까지의 수 중 아직 금지되지 않은 수들이 주어질 때, 상대를 패배 위치에 빠뜨리는 모든 필승 수를 오름차순으로 구한다.
난이도

보통10점 중 7점

유형
게임 이론, 백트래킹, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

크리스티아네와 마티아스가 새로운 게임인 숫자 게임을 합니다. 규칙은 다음과 같습니다. 두 사람은 번갈아 가며 22 이상의 정수를 하나씩 고릅니다. 고를 수 있는 수는 아래 규칙에 의해 제한됩니다.

  • R1. 두 사람 중 누군가가 이미 고른 수, 또는 그 수의 배수는 고를 수 없습니다. (수 zz가 어떤 양의 정수 xx에 대해 z=y⋅xz = y \cdot x로 쓰일 수 있으면, zz는 yy의 배수입니다.)
  • R2. 그러한 배수 두 개의 합도 고를 수 없습니다.
  • R3. 편의를 위해 2020보다 큰 수도 고를 수 없습니다.

더 이상 어떤 수도 고를 수 없는 사람이 게임에서 집니다.

예를 들어 마티아스가 먼저 44를 골랐다고 합시다. 그러면 크리스티아네는 4,8,12,…4, 8, 12, \dots를 더 이상 고를 수 없습니다. 그녀가 33을 골랐다고 하면, 이제 3,6,9,…3, 6, 9, \dots도 제외되고, 나아가 7=3+47 = 3 + 4, 10=2⋅3+410 = 2\cdot 3 + 4, 11=3+2⋅411 = 3 + 2\cdot 4, 13=3⋅3+4,…13 = 3\cdot 3 + 4, \dots와 같은 수도 고를 수 없게 됩니다. 결국 남는 수는 22와 55뿐입니다. 마티아스가 22를 고르면 5=2+35 = 2 + 3도 금지되므로, 크리스티아네는 고를 수 있는 수가 없어 지게 됩니다.

규칙 R3 덕분에 게임은 반드시 유한하게 끝나며 이기는 전략을 찾을 수 있습니다. 하나의 게임 상황(아직 금지되지 않은 수들의 목록)이 주어지면, 모든 이기는 수를 출력하세요. 이기는 수란, 그 수를 고른 뒤 상대가 어떻게 두더라도 자신이 승리를 강제할 수 있는 수입니다. 형식적으로 정의하면 다음과 같습니다.

  • 지는 위치란 (1) 모든 수가 금지되었거나, (2) 이기는 수가 존재하지 않는 위치입니다.
  • 이기는 위치란 이기는 수가 존재하는 위치입니다.
  • 이기는 수란 그 수를 고른 뒤의 위치가 지는 위치가 되는 수입니다.

입력

첫째 줄에 시나리오의 개수가 주어집니다.

각 시나리오는 하나의 게임 상황을 나타냅니다. 먼저 아직 고를 수 있는 수의 개수 aa (0≤a<200 \le a < 20)가 한 줄에 주어집니다. 다음 줄에는 아직 고를 수 있는 aa개의 수가 공백 하나로 구분되어 주어집니다.

입력으로 주어지는 모든 게임 상황은 실제로 숫자 게임에서 나타날 수 있는 상황입니다(예를 들어 33이 목록에 없다면 66도 없습니다).

출력

각 시나리오에 대해 먼저 Scenario #i: 형식의 줄을 출력합니다. 여기서 ii는 11부터 시작하는 시나리오 번호입니다. 다음 줄에는, 현재 위치에 이기는 수가 없으면 There is no winning move.를 출력하고, 그렇지 않으면 The winning moves are: w1 w2 ... wk. 를 출력합니다. 이때 w1,w2,…,wkw_1, w_2, \dots, w_k는 모든 이기는 수를 오름차순으로 나열한 것이며 공백 하나로 구분합니다. 서로 다른 시나리오의 출력 사이는 빈 줄 하나로 구분합니다.

예제1

  1. 예제 1

    입력
    2
    1
    2
    2
    2 3
    
    예상 출력
    Scenario #1:
    The winning moves are: 2.
    
    Scenario #2:
    There is no winning move.