HDU 2897 邂逅明下

题意：一堆石子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<r<=p),则B必胜，必胜策略为：

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

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

3.若n = (p+q)*k+r,(p<r<p+q),则A必胜，必胜策略为：

A第一次取t(1<r-t<=p)个，以后每次若B取m个，A取（p+q-m）个，

那么最后必剩下1<r-t<=p个给B,A胜

[cpp]
<span style="font-size:18px;color:#006600;"><strong>#include<stdio.h>
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;
}</strong></span>

补充：软件开发 , C++ ,