고양이 게임

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

요약
2A+1칸 게임판 중앙에서 건덕이가 1칸, 건구스가 2칸씩 번갈아 로봇을 옮길 때 누가 이기는지 판정한다.
난이도

보통10점 중 4점

유형
게임 이론, 수학, 시뮬레이션
정답자
아직 제출이 없습니다

문제

양의 정수 AA가 주어질 때, 건덕이와 건구스는 이를 이용해 고양이 게임을 하려 한다. 게임판은 2A+12A+1개의 칸으로 이루어져 있고, 모든 칸은 가로로 일렬로 이어져 있다. 처음에 정중앙인 A+1A+1번째 칸에 고양이 로봇이 있다.

건덕이와 건구스가 차례대로 아래의 행동을 반복한다.

  • 건덕이는 고양이 로봇을 왼쪽이나 오른쪽으로 11칸 이동시킨다.
  • 건구스는 고양이 로봇을 왼쪽이나 오른쪽으로 22칸 이동시킨다.

고양이 로봇을 게임판 밖으로 이동시킬 수 없고, 한 번 놓였던 칸으로도 이동시킬 수 없다. 시작 칸인 A+1A+1번째 칸은 고양이 로봇이 놓였던 칸으로 생각한다.

둘 다 최선을 다해서 승부를 겨루며, 만약 고양이 로봇을 이동시킬 수 없다면 해당 플레이어가 패배하고, 상대방이 승리한다.

양의 정수 AA가 주어질 때, 건덕이와 건구스 중 누가 승리하는지 구해보자.

입력

정수 AA가 주어진다. (1≤A≤109)(1\leq A\leq 10^9)

출력

건덕이가 이긴다면 duck을, 건구스가 이긴다면 goose를 출력한다.

예제2

  1. 예제 1

    입력
    3
    
    예상 출력
    duck
    
  2. 예제 2

    입력
    8
    
    예상 출력
    goose