계단 님
플래티넘 IV의견: 0
\(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번 계단부터).
선공 또는 후공을 출력한다.
3
1 2 3
선공계단 3개, 동전 [1,2,3]. 홀수 위치(1,3)의 동전 XOR \(=1 \oplus 3 = 2 \ne 0\) → 선공.
4
0 5 0 5
후공[0,5,0,5]. 홀수 위치(1,3)는 0,0 → XOR 0 → 후공.
riseoj 작성
출처 Original
평가 및 의견
계단 님
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
계단 님