31541번 - 1차원 돌 게임 1 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 127 | 52 | 42 | 42.000% |
문제
이 문제는 1차원 돌 게임 2와 굵은 글씨로 적힌 부분만 다릅니다.
동우와 재우는 $1\times n$ 모양의 직선형 격자판에서 처음에 한 칸에 한 개씩 돌을 올려 둔 상태로 게임을 진행하려 한다.
게임은 동우부터 시작해 턴을 번갈아 가면서 돌을 가져간다. 즉, 동우는 홀수 번째 턴에, 재우는 짝수 번째 턴에 진행한다.
- 첫 번째 턴에는 $1$개의 칸을 골라 그곳에 놓인 돌을 가져간다.
- 두 번째 턴부터는 직전 턴에 상대방이 가져간 돌의 개수가 $x$개라면, 돌이 놓여 있는 연속한 $x+1$개의 칸을 골라 그 영역에 놓인 모든 돌을 가져간다.
- 돌을 가져갈 때마다, 돌을 가져간 칸(들)을 기준으로 남은 돌들이 두 부분으로 나누어진다면, 놓인 돌의 개수가 더 적은 부분에 놓인 돌을 모두 버린다. 두 부분에 놓인 돌의 개수가 같다면 한 부분을 선택해 놓인 돌을 모두 버린다. 두 부분으로 나누어지지 않고 한 부분만 있는 경우 버리지 않는다.
- 자신의 턴에 조건에 맞게 돌을 가져가지 못한다면 그 사람이 패배하며, 상대방이 승리한다.
둘 다 승리하기 위해 최선의 플레이를 한다면 누가 이기는지 출력하시오.
입력
첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\le T \le 10^6)$
각 테스트 케이스별로 한 줄에 하나씩 초기의 돌의 개수 $n$이 주어진다. $(1\le n\le 10^{18})$
같은 $n$이 여러 번 주어지지 않는다.
출력
각 테스트 케이스에 대해 동우가 이기면 kidw0124를, 재우가 이기면 eoaud0108을 한 줄에 하나씩 출력한다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 28 | $n\le 20$ |
| 2 | 34 | $n\le 1\,000$ |
| 3 | 133 | $n\le 500\,000$ |
| 4 | 155 | 추가적인 제한 조건 없음 |
예제 입력 1
3 1 4 8
예제 출력 1
kidw0124 eoaud0108 kidw0124
$n=8$인 경우 동우는 첫 번째 턴에 가장 마지막($8$번째) 칸에 놓인 돌을 가져가면 승리할 수 있다.
두 번째 턴에 재우는 남은 $7$칸에 놓인 돌들 중 이웃한 $2$개를 골라 가져가는데, 다음과 같은 경우가 가능하다. 좌우 대칭인 상황은 하나만 생각하자.
- $1$, $2$번 혹은 $6$, $7$번 칸에 놓인 돌을 가져갈 경우
- $2$, $3$번 혹은 $5$, $6$번 칸에 놓인 돌을 가져갈 경우
- $3$, $4$번 혹은 $4$, $5$번 칸에 놓인 돌을 가져갈 경우
모든 경우에 대해 동우는 세 번째 턴에 $3$개의 돌을 가져갈 수 있으며, 재우는 네 번째 턴을 진행할 수 없다.
출처
University > 고려대학교 > MatKor Cup > 제4회 고려대학교 MatKor Cup: 2024 Winter/Spring I번
- 문제를 만든 사람: alex04, eoaud0108, kidw0124, sshs29hanul
- 문제를 번역한 사람: tikiliki0417
- 문제를 검수한 사람: changhw, finimage, kevinlys00, tlsdydaud1, utilforever, w8385, yijw0930
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호