독이 든 초콜릿
골드 IV의견: 0
알리와 베리가 \(M \times N\) 격자 모양의 초콜릿 판으로 게임을 한다. 초콜릿 판의 좌하단을 \((1, 1)\), 우상단을 \((M, N)\)으로 표시한다.
두 플레이어는 번갈아 가며(알리 먼저) 다음 세 가지 중 하나를 선택한다:
1. 오른쪽에서 \(k\)열 (\(k \ge 1\))을 제거한다.
2. 위쪽에서 \(k\)행 (\(k \ge 1\))을 제거한다.
3. 오른쪽에서 \(k\)열, 위쪽에서 \(k\)행을 동시에 제거한다. (\(k \ge 1\))
단, \((1, 1)\)의 조각은 독이 들어 있으므로 결코 제거해서는 안 된다. 즉 초콜릿 판은 항상 \((1,1)\)을 포함한 사각형 형태를 유지한다.
초콜릿 판의 크기가 \(1 \times 1\)이 되어 자신의 차례에 아무것도 제거할 수 없게 된 플레이어가 진다 (\((1,1)\)만 남은 상태).
두 플레이어 모두 최선의 전략을 쓴다고 할 때, 누가 이기는지 출력하여라.
- \(1 \le M, N \le 10^9\)
한 줄에 초콜릿 판의 행 수 \(M\)과 열 수 \(N\)이 공백으로 구분되어 주어진다.
첫 번째 플레이어가 이기면 First, 두 번째 플레이어가 이기면 Second를 출력한다.
1 2
First
\((1, 2)\)은 W-position의 P 위치(\((\lfloor\phi\cdot1\rfloor,\lfloor\phi^2\cdot1\rfloor) = (1, 2)\))이므로 두 번째 플레이어가 이긴다.
2 2
First
\((2, 2)\)은 P-position이 아니므로 첫 번째 플레이어가 이긴다. 예를 들어 열을 하나 제거해 \((2, 1)\)로 만들면 이것도 P-position이 아니지만, \((1, 2) \to (1, 1)\)... 실제로는 대각선으로 \((1, 1)\)을 만들 수 있고, \((1, 1)\)에서 첫 번째 플레이어가 지면 \((2,2)\)에서 현재 플레이어가 이긴다.
riseoj 작성
출처 Original
평가 및 의견
독이 든 초콜릿
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
독이 든 초콜릿