题目回顾

题目描述

PDF

翻译

斯坦和奥利玩的是一个整数 \(p\) 乘以 \(2\) 到 \(9\) 中的一个数字的乘法游戏。斯坦总是从 \(p\) \(=\) \(1\) 开始，做乘法，然后奥利乘以这个数字，然后斯坦也如此。游戏开始前，他们画一个整数 \(n\)，获胜者是第一个达到 \(p\ge n\) 的人。那么他们谁是获胜者？

输入格式：

多组数据，每行包含一个数n。

输出格式：

每行输出Stan和Ollie谁将获得胜利，如果Stan胜利，输出"Stan wins."否则输出"Ollie wins."(注意有个句号)

样例输入

162
17
34012226

样例输出

Stan wins.
Ollie wins.
Stan wins.

提示

\(1\) \(<\) \(n\) \(<\) \(4294967295\)

思路

这道题一看就是博弈论，那么我们先来看度娘来了解一下什么是博弈论：

博弈论，又称为对策论（Game Theory）、赛局理论等，既是现代数学的一个新分支，也是运筹学的一个重要学科。

博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。生物学家使用博弈理论来理解和预测进化论的某些结果。

博弈论已经成为经济学的标准分析工具之一。在金融学、证券学、生物学、经济学、国际关系、计算机科学、政治学、军事战略和其他很多学科都有广泛的应用。

双方都想取胜，要让对方必败就得让对方，到一个必败的点（也就是自己的必胜点），对方就会必败，而必败的点可以从最后反推回来。
设当前的数到了 \(m\)，那么先手的必胜点在 \(n > m\ge \frac{n}{9}\) 这个区间里，反观后手，后手的必胜点在 \(\frac{n}{9} > m \ge \frac{n}{18}\) 这个区间里。很容易发现，若我们把 \(n\) 一直除以 \(18\) 直到 \(n \leq 18\) 时为止，可以缩小这个不等式的范围，最后若 \(n>9\) 则后手赢，否则先手赢。

Tips：\(n\) 一定要开成小数类型的变量，否则会向下取整，不准确。

\(AC\) \(Code\)

#include <bits/stdc++.h>
using namespace std;
int main()
{
	for(double n; cin >> n;)
	{
		while(n > 18) n /= 18;
		if(n > 9) puts("Ollie wins.");
		else puts("Stan wins.");
	}
	return 0;
}