중복 없는 님 게임

시간 제한2초메모리 제한512 MB

요약
각 더미에서 같은 개수의 돌을 두 번 이상 제거할 수 없는 변형 님 게임에서, 두 사람이 최선으로 둘 때 승자를 판정한다.
난이도

어려움10점 중 9점

유형
게임 이론, 동적 계획법, 비트 연산, 조합론
정답자
아직 제출이 없습니다

문제

구사과와 큐브러버가 님 게임을 하려고 한다. 님 게임은 돌 더미 NN개를 이용하며, ii번째 돌 더미에 있는 돌의 개수는 AiA_i개이다. 두 사람은 턴을 번갈아 가지면서 게임을 진행한다. 각 턴은 돌 더미를 하나 고르고, 그 돌 더미에서 돌을 1개 이상 제거하는 것으로 이루어져 있다.

게임은 구사과가 먼저 시작하고, 자신의 턴이 돌아왔을 때 돌을 제거할 수 없는 사람이 게임을 진다.

이 게임을 너무 많이 했기 때문에, 오늘은 새로운 규칙을 하나 추가해서 하려고 한다.

새로 추가한 규칙은 한 돌 더미에서 같은 개수의 돌을 또 제거할 수 없다는 것이다. 예를 들어, 한 돌 더미에서 돌을 4개 가져갔으면, 이후에는 그 돌 더미에서 돌을 4개 가져갈 수는 없다. 이 규칙은 두 사람에게 모두 적용되고, 돌 더미마다 독립적으로 적용된다.

두 사람이 게임을 최적의 방법으로 했을 때, 누가 이기는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 돌 더미의 개수 N(1≤N≤106)N(1 \le N \le 10^6)이 주어진다. 둘째 줄에는 돌 더미에 있는 돌의 개수 A1,A2,…,AN(1≤Ai≤60)A_1, A_2, \dots, A_N(1 \le A_i \le 60)이 주어진다.

출력

구사과가 게임을 이기는 경우에는 "koosaga", 큐브러버가 이기는 경우에는 "cubelover"를 출력한다.

예제2

  1. 예제 1

    입력
    1
    5
    
    예상 출력
    koosaga
    
  2. 예제 2

    입력
    2
    1 2
    
    예상 출력
    cubelover