#博弈论#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;
}