POJ 2348 - Euclid's Game

http://poj.org/problem?id=2348

概要

二人のプレイヤーが2つの整数に関するゲームを行う．

各ターンに，プレイヤーは大きいほうの整数から小さいほうの好きな倍数を引くことができる． ただし，このときに引いた結果が負になってはならない．

引けなくなった方，すなわち片方の整数が 0 になったプレイヤーの負けである．

初期状態の整数の組 (x, y) が与えられるので，先手必勝か後手必勝かを答える．

制約

• 問題文には無いが，x, y は正の整数で符号付き 32-bit 整数値に収まる

解法

以下 x <= y を仮定する．

プレイヤーの勝ち負けを判定する関数を f(x, y) とすると，

f(0, y) = false
f(x, y) = !f(y-x, y)  if y/x == 1
f(x, y) = true        otherwise

となる．

1つ目はゲームのルールから自明で，2つ目も y から x を引くしか選択肢が無いので明らか．

3つ目の y/x = n (>= 2) だった場合を考える．

• もし f(y - n*x, x) == false だった場合，プレイヤーは n*x を引くことで勝つことができる．
• もし f(y - n*x, x) == true だった場合，プレイヤーが (n-1)*x を引くと (x, y-(n-1)*x) という状態になり，ここで相手は x を引くしか手が無いので今度は自分の番が (y-n*x, x) で回ってきて，勝つことができる．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 bool dfs(int x, int y)
 6 {
 7   // x <= y
 8   if (x == 0) {
 9     return false;
10   } else if (y/x == 1) {
11     return !dfs(y-x, x);
12   } else {
13     return true;
14   }
15 }
16 
17 int main()
18 {
19   int x, y;
20   while (scanf("%d %d", &x, &y) && x != 0) {
21     if (x > y) {
22       swap(x, y);
23     }
24     puts(dfs(x, y) ? "Stan wins" : "Ollie wins");
25   }
26   return 0;
27 }