石を取る(二)

2045 ワード

石を取る(二)
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
5
説明
王さんは同僚と小さなゲームをするのが好きで、今日彼らは石を取ることを選んだ.
游びのルールは以下の通りです:共にN堆石があって、1堆の中の石の数量を知っていて、しかも1堆石ごとに最も多く取ることができる石の数(少なくとも1粒を取る)を决めました.
2人は交代で子を取り、毎回N山の石の中の1山しか選択できず、一定数の石(少なくとも1つ)を取り、その石の数がこの山の石が規定した最大数より多くはならないなど、誰が子を取れないかを示すと、この人はゲームに負けたことを示します.
毎回王さんが先に石を取って、ゲームの双方が絶対に頭がいいと仮定して、今あなたに石の山の数、石の山の数と石の山ごとに規定された単回の取子の上限をあげて、王さんが勝つかどうかを判断してください.
入力
1行目は整数Tであり、テストデータのグループ数を表す(T<100)
各試験データの最初の行は整数N(1しゅつりょく
各グループのテストデータに対して、出力Winは王さんが勝つことができることを示し、出力Loseは王さんが必ず負けることを示した.
サンプル入力
2
1
1000 1
2
1 1
1 1

サンプル出力
Lose
Lose

ヒント
次のテストデータのセットに注意してください.
2
1 1 
2 2
正しい結果はWin
王さんはまず第二の石から石を取って、状態を
1 1
1 2
この状態では、いくら相手が取っても、王さんは勝つことができます.
ソース
クラシックテーマ
アップロード者
張雲聡
考え方:
この問題はバッシュゲームとニムゲームの混ざり合いである.ニムゲームは石の山ごとに1-すべてを取ることができることを要求しているので、この問題は数を制限して、バッシュゲームになった.バッシュゲームを用いて最後のゲームを取ったとき,得られたn%(m+1)の結果はコード:
[cpp]  view plain copy
#include   
  
int main()  
{  
    int t;  
    scanf("%d", &t);  
    while(t --){  
        int ans = 0;  
        int k, n, m;  
        scanf("%d", &k);  
        while(k --){  
            scanf("%d%d", &n, &m);  
            int Bashi = n % (1 + m);  
            ans ^= Bashi;  
        }  
  
        if(ans)  
            printf("Win");  
        else  
            printf("Lose");  
    }