고양이 게임
시간 제한1초메모리 제한1024 MB
2A+1칸 게임판 중앙에서 건덕이가 1칸, 건구스가 2칸씩 번갈아 로봇을 옮길 때 누가 이기는지 판정한다.
문제
양의 정수 가 주어질 때, 건덕이와 건구스는 이를 이용해 고양이 게임을 하려 한다. 게임판은 개의 칸으로 이루어져 있고, 모든 칸은 가로로 일렬로 이어져 있다. 처음에 정중앙인 번째 칸에 고양이 로봇이 있다.
건덕이와 건구스가 차례대로 아래의 행동을 반복한다.
- 건덕이는 고양이 로봇을 왼쪽이나 오른쪽으로 칸 이동시킨다.
- 건구스는 고양이 로봇을 왼쪽이나 오른쪽으로 칸 이동시킨다.
고양이 로봇을 게임판 밖으로 이동시킬 수 없고, 한 번 놓였던 칸으로도 이동시킬 수 없다. 시작 칸인 번째 칸은 고양이 로봇이 놓였던 칸으로 생각한다.
둘 다 최선을 다해서 승부를 겨루며, 만약 고양이 로봇을 이동시킬 수 없다면 해당 플레이어가 패배하고, 상대방이 승리한다.
양의 정수 가 주어질 때, 건덕이와 건구스 중 누가 승리하는지 구해보자.
입력
정수 가 주어진다.
출력
건덕이가 이긴다면 duck을, 건구스가 이긴다면 goose를 출력한다.