숫자 게임
시간 제한1초메모리 제한128 MB
2부터 20까지의 수 중 아직 금지되지 않은 수들이 주어질 때, 상대를 패배 위치에 빠뜨리는 모든 필승 수를 오름차순으로 구한다.
문제
크리스티아네와 마티아스가 새로운 게임인 숫자 게임을 합니다. 규칙은 다음과 같습니다. 두 사람은 번갈아 가며 이상의 정수를 하나씩 고릅니다. 고를 수 있는 수는 아래 규칙에 의해 제한됩니다.
- R1. 두 사람 중 누군가가 이미 고른 수, 또는 그 수의 배수는 고를 수 없습니다. (수 가 어떤 양의 정수 에 대해 로 쓰일 수 있으면, 는 의 배수입니다.)
- R2. 그러한 배수 두 개의 합도 고를 수 없습니다.
- R3. 편의를 위해 보다 큰 수도 고를 수 없습니다.
더 이상 어떤 수도 고를 수 없는 사람이 게임에서 집니다.
예를 들어 마티아스가 먼저 를 골랐다고 합시다. 그러면 크리스티아네는 를 더 이상 고를 수 없습니다. 그녀가 을 골랐다고 하면, 이제 도 제외되고, 나아가 , , , 와 같은 수도 고를 수 없게 됩니다. 결국 남는 수는 와 뿐입니다. 마티아스가 를 고르면 도 금지되므로, 크리스티아네는 고를 수 있는 수가 없어 지게 됩니다.
규칙 R3 덕분에 게임은 반드시 유한하게 끝나며 이기는 전략을 찾을 수 있습니다. 하나의 게임 상황(아직 금지되지 않은 수들의 목록)이 주어지면, 모든 이기는 수를 출력하세요. 이기는 수란, 그 수를 고른 뒤 상대가 어떻게 두더라도 자신이 승리를 강제할 수 있는 수입니다. 형식적으로 정의하면 다음과 같습니다.
- 지는 위치란 (1) 모든 수가 금지되었거나, (2) 이기는 수가 존재하지 않는 위치입니다.
- 이기는 위치란 이기는 수가 존재하는 위치입니다.
- 이기는 수란 그 수를 고른 뒤의 위치가 지는 위치가 되는 수입니다.
입력
첫째 줄에 시나리오의 개수가 주어집니다.
각 시나리오는 하나의 게임 상황을 나타냅니다. 먼저 아직 고를 수 있는 수의 개수 ()가 한 줄에 주어집니다. 다음 줄에는 아직 고를 수 있는 개의 수가 공백 하나로 구분되어 주어집니다.
입력으로 주어지는 모든 게임 상황은 실제로 숫자 게임에서 나타날 수 있는 상황입니다(예를 들어 이 목록에 없다면 도 없습니다).
출력
각 시나리오에 대해 먼저 Scenario #i: 형식의 줄을 출력합니다. 여기서 는 부터 시작하는 시나리오 번호입니다. 다음 줄에는, 현재 위치에 이기는 수가 없으면 There is no winning move.를 출력하고, 그렇지 않으면 The winning moves are: w1 w2 ... wk. 를 출력합니다. 이때 는 모든 이기는 수를 오름차순으로 나열한 것이며 공백 하나로 구분합니다. 서로 다른 시나리오의 출력 사이는 빈 줄 하나로 구분합니다.