HDU 2897 邂逅明下

2014-11-24 10:13:18 · 作者: · 浏览: 1


题意:一堆石子n个,A,B两人轮流从中取,每次取的石子必须在区间[p,q]内,若剩下的石子少于p个,

取石者须全部取完。最后取石子的者输。给出n,p,q,问先取者是否有必胜策略?

思路:巴什博弈变形

证明:假设先手为A,后手为B,初始n个,除最后一次每次取的石子个数必须

在区间[p,q]内,则:

1.若当前石子共有n = (p+q)*k个,则A必胜,必胜策略为:

A第一次取q个,以后每次若B取m个,A取(p+q-m)个,如此最后必剩下p个给B,A胜

2.若n = (p+q)*k+r,(1

每次取石子活动中,若A取m个,则B取(p+q-m)个,那么最后必剩下r个给A,

此时r<=p,A只能一次取完,B胜

3.若n = (p+q)*k+r,(p

A第一次取t(1

那么最后必剩下1

[cpp]
#include
int main()
{
int n,p,q,r;
while(scanf("%d%d%d",&n,&p,&q)!=EOF)
{
r=n%(p+q);
if(r<=p&&r>0)
printf("LOST\n");
else printf("WIN\n");
}
return 0;
}