POJ 2505 - A multiplication game

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

概要

初期状態 p = 1 から始めて，二人のプレイヤーが交互に2以上9以下の数を掛けていくゲームをする． 最初に p >= n としたプレイヤーを勝者とするとき，与えられた n に対して先手必勝か後手必勝か答える．

制約

• 1 < n < 4294967295

解法

まず n を固定して考えると

• n/9 <= p < n のとき，9 を掛けると p * 9 >= n で勝者となるので，この状態は winning である
• n/18 <= p < n/9 のとき，2 <= m <= 9 のどんな m を掛けても n/9 <= p * m < n で↑の状態に遷移してしまうため losing である
• n/972 <= p < n/18 のとき，うまく掛ける数を選べば↑の状態に遷移できるので winning である
• ...

であるため，

• 1 < n <= 9 のときは先手必勝
• 9 < n <= 18 のときは後手必勝
• 18 < n <= 972 のときは先手必勝
• ...
• 2^k * 9^k < n <= 2^k 9^k+1 のときは先手必勝
• 2^k * 9^k+1 < n <= 2^k+1 * 9^k+1 のときは後手必勝

と判定できる．

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   long long n;
 7   while (scanf("%lld", &n) != EOF) {
 8     long long p = 1;
 9     for (;;) {
10       p *= 9;
11       if (p >= n) {
12         puts("Stan wins.");
13         break;
14       }
15       p *= 2;
16       if (p >= n) {
17         puts("Ollie wins.");
18         break;
19       }
20     }
21   }
22   return 0;
23 }