d347: 00847 - A Multiplication Game

2021-06-06 15:10:54 +0800 CST Tags: game, self-thinking-proof

出處：https://zerojudge.tw/ShowProblem?problemid=d347
提交：https://zerojudge.tw/Submissions?problemid=d347&account=allllllan123456

問題：兩人在玩一個乘法遊戲，每人每回合分別對一個正整數 p 乘上一個 2 到 9 的正整數並更新回 p，而遊戲開始前的 p 為 1，那誰先讓 p 大於等於目標正整數 n，誰就獲勝。現在隨便給定一個 n，請判斷是先手獲勝還是後手獲勝？

解法：本題的答案會以 18 倍作為一個循環，暫且羅列些許區間如下：
(先手勝) $n\in(1,\ 9]$
(後手勝) $n\in(9,\ 9\cdot 2]$
(先手勝) $n\in(9\cdot2,\ 9\cdot2\cdot9]$
(後手勝) $n\in(9\cdot2\cdot9,\ 9\cdot2\cdot9\cdot2]$
(先手勝) $n\in(9\cdot2\cdot9\cdot2,\ 9\cdot2\cdot9\cdot2\cdot9]$
(後手勝) $n\in(9\cdot2\cdot9\cdot2\cdot9,\ 9\cdot2\cdot9\cdot2\cdot9\cdot2]$
…
所以我們只要判斷 n 屬於哪個區間即可，程式的實作上並不困難，有趣的是它的正確性證明。

證明：
第一個區間是 base case，不解釋。從第二個區間開始，我們想正式地推論，當 $(18^k, 18^k\cdot9]$ 屬於先手勝的區間，可以推得下一個階段的 $(18^k\cdot9, 18^{k+1}]$ 是屬於後手勝的區間，要證明這件事，只要說明先手在第一步無論選擇什麼數字 $p\in[2,9]$，剩下還沒有乘上的倍數 $\lceil n/p\rceil$ 都一定會落在後手 (也就是不考慮 $p$ 前提下的先手) 的地盤即可，又因為 $\forall n\in(18^k\cdot9, 18^k\cdot18],\ \forall p\in[2,9]$，恆有 $\lceil n/p\rceil\in$$(18^k, 18^k\cdot9]$，此結論亦得證。接著我們也想正式地推論，當 $(18^k\cdot9, 18^{k+1}]$ 屬於後手勝的區間，則下一個階段的 $(18^{k+1}, 18^{k+1}\cdot9]$ 必定屬於先手勝的區間，要證明這件事，只要說明先手在第一步能選擇一個特定的數字 $p\in[2,9]$，使得剩下還沒有乘上的倍數 $\lceil n/p\rceil$ 會落在先手 (也就是不考慮 $p$ 前提下的後手) 的地盤即可，又因為 $\forall n\in(18^{k+1}, 18^{k+1}\cdot9],\ \exists p\in[2,9]$ 使得 $\lceil n/p\rceil\in(18^k\cdot9, 18^{k+1}]$，此結論亦得證。上面兩個結論有了，就能把誰獲勝的區間一層一層地往下推進，得到全部的結論。

 1#include <bits/stdc++.h>
 2using namespace std;
 3
 4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
 5    long long n;
 6    while (cin >> n) {
 7        long long ub = 1, mul = 2;
 8        while (n > ub)
 9            mul = 18 / mul,
10            ub *= mul;
11        if (mul == 9) cout << "Stan wins.\n";
12        else cout << "Ollie wins.\n";
13    }
14    return 0;
15}