题目大意:
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;
}