#博弈论#Poj 2505 A multiplication game

题目

给你一个整数(n),你从1开始乘,乘2-9之间的任意一个数。

最先得到大于等于(n)的数的人胜利。Stan先手Ollie后手。

那么,请问给你一个数(n),Stan和Ollie都足够聪明,那么请问谁将获得胜利了?


分析

先从小数据入手,当(n=1~9)时先手必胜,(n=10~18)时先手必败,
归纳一下,只要先手让后手进入(10~18),先手必胜,否则先手必败
既然乘上(2~9),那么在(n=19~162)时先手必胜,(n=163~324)先手必败,
归纳一下,令(n)不断对18向上取整(也可以直接用double),
(n)缩小至(1~9)先手必胜,否则先手必败


代码

#include <cstdio>
#define rr register
using namespace std;
signed main(){
	rr double n;
	while (scanf("%lf",&n)==1){
		while (n>18) n/=18;
		puts(n>9?"Ollie wins.":"Stan wins.");
	}
	return 0;
}
原文地址:https://www.cnblogs.com/Spare-No-Effort/p/14623470.html