빼기 게임
골드 I의견: 0
알리와 베리가 돌 \(N\)개로 빼기 게임을 한다. 두 플레이어는 번갈아 가며(알리 먼저) 다음 행동을 한다: 집합 \(S\)에 포함된 수 \(k\)를 선택해 돌을 정확히 \(k\)개 가져간다. 단, 남은 돌의 수보다 많이 가져갈 수 없다.
자신의 차례에 아무 행동도 할 수 없는(가져갈 수 있는 적합한 \(k\)가 없는) 플레이어가 진다. 두 플레이어 모두 최선의 전략을 쓴다고 할 때, 누가 이기는지 출력하여라.
- \(0 \le N \le 10^9\)
- \(1 \le |S| \le 20\)
- \(1 \le s_i \le 20\) (집합의 모든 원소는 서로 다르다)
- Grundy 수열의 주기는 \(|S| \cdot \max(S)\) 이내에서 시작된다.
첫째 줄에 초기 돌의 수 \(N\)과 집합의 크기 \(|S|\)가 공백으로 구분되어 주어진다.
둘째 줄에 집합 \(S\)의 원소 \(|S|\)개가 공백으로 구분되어 주어진다.
첫 번째 플레이어가 이기면 First, 두 번째 플레이어가 이기면 Second를 출력한다.
7 2
1 2
First
빼기 집합 \(S = \{1, 2\}\)일 때 Grundy 값은 주기 \(3\)이다: \(g(0)=0, g(1)=1, g(2)=2, g(3)=0, g(4)=1, \dots\) \(g(7) = g(1) = 1 \neq 0\)이므로 첫 번째 플레이어가 이긴다.
6 2
1 2
Second
\(g(6) = g(0) = 0\)이므로 두 번째 플레이어가 이긴다. 어떤 수를 빼도 첫 번째 플레이어가 이기는 위치가 남는다.
riseoj 작성
출처 Original
평가 및 의견
빼기 게임
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
빼기 게임