계단 님
골드 III의견: 0
알리와 베리가 계단 님 게임을 한다. \(N\)개의 계단이 있고 \(i\)번 계단에 돌이 \(a_i\)개 있다. 계단 아래에는 땅(0번)이 있다.
두 플레이어는 번갈아 가며(알리 먼저) 다음 행동을 한다: 임의의 한 계단 \(k\) (\(1 \le k \le N\))를 골라 그 계단에서 \(1\)개 이상의 돌을 한 계단 아래(\(k-1\)번)로 옮긴다. (0번 땅으로 옮겨진 돌은 게임에서 제외된다.)
자신의 차례에 아무 행동도 할 수 없는(모든 계단이 비어 있는) 플레이어가 진다. 두 플레이어 모두 최선의 전략을 쓸 때 누가 이기는지 출력하여라.
- \(1 \le N \le 200\,000\)
- \(0 \le a_i \le 10^9\)
첫째 줄에 계단의 수 \(N\)이 주어진다.
둘째 줄에 각 계단의 돌의 수 \(a_1, a_2, \dots, a_N\)이 공백으로 구분되어 주어진다.
첫 번째 플레이어가 이기면 First, 두 번째 플레이어가 이기면 Second를 출력한다.
3
3 1 2
First
홀수 번째 계단(1번, 3번)의 돌 수는 \(3\)과 \(2\)이다. \(3 \oplus 2 = 1 \neq 0\)이므로 첫 번째 플레이어가 이긴다.
3
2 3 2
Second
홀수 번째 계단(1번, 3번)의 돌 수는 \(2\)와 \(2\)이다. \(2 \oplus 2 = 0\)이므로 두 번째 플레이어가 이긴다.
riseoj 작성
출처 Original
평가 및 의견
계단 님
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
계단 님