레이팅 미적용설명
\(N\)개의 계단이 있다. 계단은 아래에서 위로 \(1\)번부터 \(N\)번까지 번호가 매겨져 있으며, \(0\)번 계단은 '바닥'이다. \(i\)번 계단에는 \(a_i\)개의 동전이 놓여 있다. 한 번의 차례에 어떤 계단 \(i\)(\(1 \le i \le N\))를 골라, 그 계단에 있는 동전 중 \(1\)개 이상을 바로 아래 계단 \(i-1\)로 옮긴다(\(1\)번 계단에서 옮긴 동전은 바닥으로 떨어져 게임에서 사라진다). 더 이상 옮길 동전이 없는 사람이 진다.
선공이 이기면 선공, 후공이 이기면 후공을 출력하라. (계단 Nim)
제약
\(1 \le N \le 100{,}000\)
\(0 \le a_i \le 10^9\)
입력 형식
첫 줄에 계단 수 \(N\).
둘째 줄에 \(a_1, \dots, a_N\) (1번 계단부터).
출력 형식
선공 또는 후공을 출력한다.
예제 1
입력
3
1 2 3
출력
선공설명
계단 3개, 동전 [1,2,3]. 홀수 위치(1,3)의 동전 XOR \(=1 \oplus 3 = 2 \ne 0\) → 선공.
예제 2
입력
4
0 5 0 5
출력
후공설명
[0,5,0,5]. 홀수 위치(1,3)는 0,0 → XOR 0 → 후공.
문제 시리즈
문제 정보
riseoj 작성
출처 Original
태그