시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB105503043.478%

문제

A와 B가 약수 지우기 게임을 한다. 약수 지우기 게임은 두 사람이 즐기는 게임이다.

칠판에 여러 개의 자연수가 적혀 있다. 각 사람은 자신의 턴에 칠판에 적힌 자연수 하나를 지우고, 그 자연수의 약수 중 칠판에 남아 있는 수들을 모두 지운다. 예를 들어, 칠판에 2,3,4,5,6이 적혀 있을 때, 6을 지우면, 그 약수인 2와 3 역시 지워야 한다. 자신의 턴에 숫자를 지우지 않을 수는 없다. 마지막 숫자를 지우는 사람이 승리한다.

A와 B가 최적의 방법으로 게임을 하며, A가 게임을 먼저 시작할 때, 이기는 사람을 출력하고 싶겠지만, 문제를 어렵게 만들기 위한 출제자의 악랄한 의도에 따라, 게임을 변형하여 A가 처음에 지우는 수를 랜덤으로 정하기로 했다. 그러므로 A가 처음에 어떤 수를 가져가게 되는가에 따라 이기는 사람과, B가 이기기 위한 전략이 달라질 수 있다. 처음 지우는 수를 제외하고는 A와 B는 최적의 방법으로 게임을 한다.

각 경우에 대해 B가 이기기 위한 전략을 출력하면 된다.

입력

첫째 줄에 N이 주어진다. N은 30보다 작은 자연수이다.

둘째 줄에 칠판에 적힌 N개의 자연수 Xi(<30)가 공백을 사이에 두고 오름차순으로 주어진다.

출력

N개의 줄에, (Xi)를 출력하고, A가 처음에 Xi를 지웠을 경우 B가 이기기 위해 지워야 하는 수를 공백을 사이에 두고 오름차순으로 모두 출력한다. 만약 B가 이길 수 없다면 A를 출력한다. 예제 출력을 참고하라.

예제 입력 1

6
1 2 3 4 5 6

예제 출력 1

(1) 5 6
(2) 6
(3) 4 6
(4) 3
(5) A
(6) A

예제 입력 2

6
2 3 4 5 6 7

예제 출력 2

(2) 3
(3) 2
(4) 6
(5) 6 7
(6) 4 5 7
(7) 5 6

예제 입력 3

4
2 3 4 6

예제 출력 3

(2) 3
(3) 2
(4) 6
(6) 4

힌트

첫 번째 예제의 경우, A는 처음에 6과 3,2,1을 지운다. 칠판에 남은 수는 4,5로, B가 어떤 하나를 지우더라도 A는 나머지 하나를 지워 이길 수 있다. 또한, A가 처음에 5와 1을 지우면, 남은 수는 2,3,4,6으로, 2에는 3, 3에는 2, 4에는 6, 6에는 4를 지워 이길 수 있다.

세 번째 예제의 경우, A가 2를 지운 경우 B가 3을 지우고, A가 3을 지운 경우 B가 2를 지우면 남은 수는 4,6으로 B의 승리이다. A가 4를 지운 경우 B가 6을 지우고, A가 6을 지운 경우 B가 4를 지우면 모든 수를 지워 B의 승리이다. 각각의 경우에서 B가 다른 수를 지운다면 이길 수 없다.

출처

  • 문제를 만든 사람: cozyyg