巴什博奕的变形。
只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取p个,最多取q个。最后取光者得输。
显然,如果n=r*(p+q)+s , 即s = n%(p+q).# n%(p+q) == 0
先手一定赢,假设先手第一次拿q个,接着每次不管后手拿多少个,假设后手拿k个,先手都可以拿p+q-k
个,所以最后一定剩下p个给后手,所以先手必胜。
# n%(p+q) != 0
1.(1< s <= p)那么由于一次最多只能取q个,所以,无论先手拿走多少个,假设拿了k个, 后手都能够一
次拿走p+q-k个物品,最后剩下s个给先手,所以先手必输。
2.(p < s < q+p)先手第一次取x(1<s-x<=p)个,以后每次若后手取k个,先手则取(p+q-k)个,那么
最后必剩下1<s-x<=p个给后手,所以先手必胜。
#include#include #include #include #include using namespace std;int main() { int n,p,q; while(~scanf("%d%d%d",&n,&p,&q)){ if(n%(p+q)&&p >= n%(p+q)) printf("LOST\n"); else printf("WIN\n"); } return 0;}