题意:一堆石子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;
}