题目大意:
Stan与Ollie两人博弈,Stan先手。
两人对当前数(初始为1)进行乘操作,乘数为[2,9];给定N,当某人第一次使得操作数大于等于N时,为胜利者。
由博弈原理:
设x为取到的值。
则x>=N时为必败态。
任何能转化为必败态的都是必胜态,所以[ceil(N/9),N-1]为必胜点。
只能转化为必胜态的都是必败态,所以[(ceil(N/9)/2),ceil(N/9)-1]为必败点。
当区间左端到达1时,就可以判断了。
#include<iostream> #include<cmath> using namespace std; int main() { __int64 N; while( scanf("%I64d",&N)!=EOF ) { __int64 a=(__int64)ceil(N/9.0); __int64 b=N-1; while( true ) { N=(__int64)ceil(N/9.0); if( N==1 ) { printf( "Stan wins.\n" ); break; } N=(__int64)ceil(N/2.0); if( N==1 ) { printf( "Ollie wins.\n" ); break; } } } return 0; }