시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 67 | 27 | 8 | 30.769% |
준혁이와 영우가 서로소 게임을 하려고 한다.
서로소 게임은 칠판에 $N$개의 수가 써져 있는 상태로 시작한다. 두 사람은 서로 턴을 번갈아가면서 게임을 진행한다.
각 사람의 턴이 되면 칠판에 있는 수 하나를 골라서, 고른 수는 지우고 두 개의 자연수를 새로 적어야 한다. 이 두 수는 서로소가 아니어야 하며, 합하여 지운 수가 되어야 한다. 예를 들어 8을 지운 뒤 2와 6를 쓸 수 있다. 그러나 3과 5는 합하여 8이지만 서로소이기 때문에 적을 수 없다.
더 이상 턴을 진행할 수 없는 사람이 게임에서 지게 된다.
그런데 준혁이는 여러 개의 수 중 어떤 것을 골라야 유리할 지 고민에 빠지기 시작했다. 준혁이를 기다릴 수 없었던 영우는, 수를 고를 때 고를 수 있는 수 중 가장 작은 수를 고르자는 규칙을 추가하였다. 예를 들어 칠판에 4, 8, 9가 적혀있다면, 4를 골라 턴을 진행하는 것이 가능하기 때문에 8이나 9를 골라서는 안된다.
게임은 준혁이가 먼저 시작한다. 두 사람 모두 최적의 방법으로 게임을 진행할 때, 누가 이길지 구해보자.
첫째 줄에 처음에 써져 있는 수의 개수 $N$이 주어진다. ($1\leq N \leq 10^4$)
둘째 줄에 $N$개의 수 $a_1, a_2,\ldots ,a_n$이 공백을 사이에 두고 주어진다. ($1\leq a_i \leq 10^9$)
첫째 줄에 준혁이가 이기면 "6
", 영우가 이기면 "52
"를 출력한다. (따옴표 제외)
1 4
6
2 8 10
52
4 20 21 11 27
6
첫 번째 예제에서, 준혁이가 4를 지우고 2, 2를 적으면 이긴다.
University > 고려대학교 > 2021 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 1 E번