카드 게임

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

요약
두 플레이어는 차례로 카드 하나와 그보다 작은 값을 가진 카드를 모두 제거합니다. 최적의 플레이에서 승자를 결정합니다.
난이도

어려움10점 중 8점

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

문제

구사과와 큐브러버가 카드 게임을 하려고 한다. 카드 게임은 정수가 적혀 있는 카드 NN개를 일렬로 나열한 상태에서 시작되며, ii번째 카드에 적혀 있는 수는 AiA_i이다.

게임은 턴을 번갈아 가면서 진행되고, 구사과가 먼저 게임을 시작한다. 각 턴은 다음과 같이 이루어진다.

  • 카드를 하나 고르고 제거한다. 이때 고른 카드에 적힌 수보다 작은 수가 적혀 있는 카드도 모두 제거한다.
  • 즉, ii번째 카드를 고른 경우에는 ii번째 카드와 Aj<AiA_j < A_i를 만족하는 모든 jj번째 카드도 제거한다.

카드가 모두 제거되면 게임이 끝나며, 더 이상 제거할 카드가 없는 사람이 게임을 지게 된다. 두 사람이 최적의 방법으로 게임을 진행했을 때, 이기는 사람이 누구인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 카드의 수 NN이 주어진다. 둘째 줄에는 카드에 적힌 수 AiA_i가 주어진다.

출력

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

제한

  • 1≤N≤1051 \le N \le 10^5
  • 1≤Ai≤1051 \le A_i \le 10^5

힌트

예제 1의 경우에 구사과가 7을 고르면 모든 카드가 제거되기 때문에, 큐브러버가 이길 수 없다. 예제 2의 경우에는 어떤 카드를 제거해도 카드 한 장이 남는다. 따라서, 큐브러버가 이긴다.

예제2

  1. 예제 1

    입력
    3
    4 5 7
    
    예상 출력
    koosaga
    
  2. 예제 2

    입력
    2
    1 1
    
    예상 출력
    cubelover