当前位置: 代码迷 >> 综合 >> HDOJ 1517 博弈的理解
  详细解决方案

HDOJ 1517 博弈的理解

热度:85   发布时间:2024-01-20 20:20:21.0

题目大意:

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;
}