시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 178 | 118 | 94 | 61.039% |
구사과와 큐브러버가 님 게임을 하려고 한다. 님 게임은 돌 더미 N개를 이용하며, i번째 돌 더미에 있는 돌의 개수는 Ai개이다. 두 사람은 턴을 번걸아 가지면서, 게임을 진행한다. 각 턴은 돌 더미를 하나 고르고, 그 돌 더미에서 돌을 1개 이상 제거하는 것으로 이루어져 있다.
게임은 구사과가 먼저 시작한고, 자신의 턴이 돌아왔을 때 돌을 제거할 수 없는 사람이 게임을 진다.
이 게임은 너무 많이 했기 때문에, 오늘은 새로운 규칙을 하나 추가해서 하려고 한다.
새로 추가한 규칙은 한 돌 더미에서 같은 개수의 돌을 또 제거할 수 없다는 것이다. 예를 들어, 한 돌 더미에서 돌을 4개 가져갔으면, 이후에는 그 돌 더미에서 돌을 4개 가져갈 수는 없다. 이 규칙은 두 사람에게 모두 적용되고, 돌 더미마다 독립적으로 적용된다.
두 사람이 게임을 최적의 방법으로 했을 때, 누가 이기는지 구하는 프로그램을 작성하시오.
첫째 줄에 돌 더미의 개수 N(1 ≤ N ≤ 106)이 주어진다. 둘째 줄에는 돌 더미에 있는 돌의 개수 A1, A2, .., AN(1 ≤ Ai ≤ 60)이 주어진다.
구사과가 게임을 이기는 경우에는 "koosaga", 큐브러버가 이기는 경우에는 "cubelover"를 출력한다.
1 5
koosaga
구사과가 첫 턴에 돌을 모두 가져가면 된다.
2 1 2
cubelover
첫 턴에서 구사과가 할 수 있는 선택은 총 세 가지가 있다.
위의 세 가지 방법 모두 큐브러버가 이긴다.