博弈-取石子

時間限制：3000 ms  |  記憶體限制：65535 KB

難度：2

<dl></dl>

<dt></dt>

描述

<dd>一天，TT在寝室閑着無聊，和同寝的人玩起了取石子遊戲，而由于條件有限，他/她們是用旺仔小饅頭當作石子。遊戲的規則是這樣的。設有一堆石子，數量為N（1&lt;=N&lt;=1000000），兩個人輪番取出其中的若幹個，每次最多取M個（1&lt;=M&lt;=1000000），最先把石子取完者勝利。我們知道，TT和他/她的室友都十分的聰明，那麼如果是TT先取，他/她會取得遊戲的勝利麼？</dd>

輸入

<dd>第一行是一個正整數n表示有n組測試資料</dd>

輸入有不到1000組資料，每組資料一行，有兩個數N和M,之間用空格分隔。

輸出

<dd>對于每組資料，輸出一行。如果先取的TT可以赢得遊戲，則輸出“Win”，否則輸出“Lose”（引号不用輸出）</dd>

樣例輸入

<dd></dd>

樣例輸出

算法：

最多取m個，則如果總數n%（m+1）為0，則無論先手取了幾個t1，第二個人都取t2，使得t1+t2==m+1即可獲勝

相反 如果n%(m+1)!=0 ,則先手不餘數去掉，之後按上述方案，即可獲勝

代碼：

難度：5

小王喜歡與同僚玩一些小遊戲，今天他們選擇了玩取石子。

遊戲規則如下：共有N堆石子，已知每堆中石子的數量，并且規定好每堆石子最多可以取的石子數（最少取1顆）。

兩個人輪流取子，每次隻能選擇N堆石子中的一堆，取一定數量的石子(最少取一個），并且取的石子數量不能多于該堆石子規定好的最多取子數，等哪個人無法取子時就表示此人輸掉了遊戲。

假設每次都是小王先取石子，并且遊戲雙方都絕對聰明，現在給你石子的堆數、每堆石子的數量和每堆石子規定的單次取子上限，請判斷出小王能否獲勝。

<dd>第一行是一個整數T表示測試資料的組數(T&lt;100)</dd>

每組測試資料的第一行是一個整數N(1&lt;N&lt;100),表示共有N堆石子，随後的N行每行表示一堆石子，這N行中每行有兩個數整數m,n表示該堆石子共有m個石子，該堆石子每次最多取n個。(0&lt;=m,n&lt;=2^31)

<dd>對于每組測試資料，輸出Win表示小王可以獲勝，輸出Lose表示小王必然會敗。</dd>

提示

<dd>注意下面一組測試資料</dd>

2

1 1 

2 2

正确的結果應該是Win

因為小王會先從第二堆石子中取一個石子，使狀态變為

1 1

1 2

這種狀态下，無論對方怎麼取，小王都能獲勝。

巴什博弈和尼姆博弈的雜糅

因為尼姆博弈要求對每一堆石子可以取1-全部，而這道題限制了個數，就成為了巴什博弈。那為什麼可以用尼姆博弈的思想來求解呢？

因為我們可以發現，當我們使用巴什博弈取到最後一次時，得到的n%(m+1)結果肯定&lt;m，這樣就符合了尼姆博弈的要求，進而可以用尼姆博弈的異或運算來求解。

時間限制：1000 ms  |  記憶體限制：1000 KB

難度：6

遊戲規則如下：共有N堆石子，已知每堆中石子的數量，兩個人輪流取子，每次隻能選擇N堆石子中的一堆，取一定數量的石子（最少取一個），取過子之後，還可以将該堆石子中剩下的任意多個石子中随意選取幾個放到其它的任意一堆或幾堆上。等哪個人無法取子時就表示此人輸掉了遊戲。注意，一堆石子沒有子之後，就不能再往此處放石子了。

假設每次都是小王先取石子，并且遊戲雙方都絕對聰明，現在給你石子的堆數、每堆石子的數量，請判斷出小王能否獲勝。

例如：如果最開始有4堆石子，石子個數分别為3 1 4 2，而小王想決定要先拿走第三堆石子中的兩個石子（石子堆狀态變為3 1 2 2），然後他可以使石子堆達到的狀态有以下幾種：

3 1 2 2（不再移動石子）

4 1 1 2（移動到第一堆一個）

3 2 1 2（移動到第二堆一個）

3 1 1 3（移動到第四堆一個）

5 1 0 2（全部移動到第一堆）

3 3 0 2（全部移動到第二堆）

3 1 0 4（全部移動到最後）

<dd>可能有多組測試資料(測試資料組數不超過1000)</dd>

每組測試資料的第一行是一個整數，表示N(1&lt;=N&lt;=10)

第二行是N個整數分别表示該堆石子中石子的數量。（每堆石子數目不超過100）

當輸入的N為0時，表示輸入結束

如果石子能夠兩兩配對，每一對中的兩堆石子的個數相同，那麼就是必敗态，先拿的輸，先拿的将必敗态轉化為必勝态，後拿的可以使自己拿完後仍然能夠使得兩兩配對，且每一對的數目相同。這樣就又将必敗态留給對手。最後可能會變成(1，

1)的情況，這樣先拿的輸，後拿的赢。是以如果n是奇數的話，就不能能出現兩兩配對的狀态那麼肯定是必勝态。

結論是：如果N是奇數先手勝，如果是偶數，那麼判斷石子數量出現的次數是否為偶數，都是偶數那就是後者勝，隻要有一個不是偶數那麼先者勝。

例如4    2 1 3 2這組資料，n是偶數，1出現一次，2出現兩次，3出現一次，不是所有的數出現的次數都是偶數，是以先者勝。

     4    2 1 1 2，n是偶數，1和2都出現兩次，是以先者敗。

時間限制：1000 ms  |  記憶體限制：65535 KB

難度：4

有兩堆石子，數量任意，可以不同。遊戲開始由兩個人輪流取石子。遊戲規定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數量的石子。最後把石子全部取完者為勝者。現在給出初始的兩堆石子的數目，如果輪到你先取，假設雙方都采取最好的政策，問最後你是勝者還是敗者。

<dd>輸入包含若幹行，表示若幹種石子的初始情況，其中每一行包含兩個非負整數a和b，表示兩堆石子的數目，a和b都不大于1,000,000,000。</dd>

<dd>輸出對應也有若幹行，每行包含一個數字1或0，如果最後你是勝者，則為1，反之，則為0。</dd>

威佐夫博奕，已知k=b-a，可求出ak，如果ak==a，則必敗。

himdd最近很想玩遊戲，于是他找到acmj和他一起玩，遊戲是這樣的：有一堆石子,兩個人輪流從其中取走一定的石子,取走最後所有石子的人為赢家,不過得遵循如下規則:

1.第一次取不能取完,至少取1顆.

2.從第二次開始,每個人取的石子數至少為1,至多為對手剛取的石子數的兩倍。

himdd事先想知道自己會不會赢，你能幫幫他嗎？（每次himdd先手）

<dd>有多組測試資料，每組有一個整數n(2&lt;=n&lt;2^64);</dd>

<dd>himdd會赢輸出Yes,否則輸出No;</dd>

斐波那契博弈問題：

當n為Fibonacci數的時候，必敗。

難度：3

最近TopCoder的PIAOYI和HRDV很無聊，于是就想了一個遊戲，遊戲是這樣的：有n堆石子,兩個人輪流從其中某一堆中任意取走一定的石子,最後不能取的為輸家，注意： 每次隻能從一堆取任意個，可以取完這堆，但不能不取。假設PIAOYI先取石子，請你幫他判斷他是否能赢（假設他們取的過程中不發生失誤,他們足夠聰明）。

<dd>第一行輸入n，代表有n組測試資料(n&lt;=10000)</dd>

以下每組測試資料包含兩行：第一行：包含一個整數m，代表本組測試資料有m（m&lt;=1000）堆石子；

：第二行：包含m個整數Ai(Ai&lt;=100)，分别代表第i堆石子的數量。

<dd>若PIAOYI赢輸出“PIAOYI”，否則輸出“HRDV”注意每組結果占一行。。</dd>

難度：1

Yougth和Hrdv玩一個遊戲，拿出n個石子擺成一圈，Yougth和Hrdv分别從其中取石子，誰先取完者勝，每次可以從中取一個或者相鄰兩個，Hrdv先取，輸出勝利着的名字。

<dd>輸入包括多組測試資料。</dd>

每組測試資料一個n，資料保證int範圍内。

<dd>輸出勝利者的名字。</dd>

<dt>描述</dt>

有兩堆石子，數量任意，可以不同。遊戲開始由兩個人輪流取石子。遊戲規定，每次有兩種不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在兩堆中同時取走相同數量的石子。最後把石子全部取完者為勝者。現在給出初始的兩堆石子的數目，如果輪到你先取，假設雙方都采取最好的政策，問最後你是勝者還是敗者。如果你勝，你第1次怎樣取子? 

<dt>輸入</dt>

<dd>輸入包含若幹行，表示若幹種石子的初始情況，其中每一行包含兩個非負整數a和b，表示兩堆石子的數目，a和b都不大于1,000,000。a=b=0退出。</dd>

<dt>輸出</dt>

<dd>輸出也有若幹行，如果最後你是敗者，則為0，反之，輸出1，并輸出使你勝的你第1次取石子後剩下的兩堆石子的數量x,y,x&lt;=y。如果在任意的一堆中取走石子能勝同時在兩堆中同時取走相同數量的石子也能勝，先輸出取走相同數量的石子的情況，假如取一堆的有多種情況，先輸出從石子多的一堆中取的情況，且要求輸出結果保證第二個值不小于第一個值。</dd>

<dt>樣例輸入</dt>

<dt>樣例輸出</dt>

最近TopCoder的Yougth和Hrdv在玩一個遊戲，遊戲是這樣的。

有n堆石子,兩個人輪流從其中某一堆中任意取走一定的石子,最後不能取的為赢家，注意： 每次隻能從一堆取任意個，可以取完這堆，但不能不取。

假設Yougth先取，輸入赢了的人名字、

：第二行：包含m個整數Ai(Ai&lt;=10000)，分别代表第i堆石子的數量。

<dd>若Yougth赢輸出“Yougth”，否則輸出“Hrdv”注意每組結果占一行。。</dd>

不知不覺取石子已經到第十道了。地球上的石子也快要取完了！

開個玩笑，當然還是有很多石子的，取石子的題目也是做不完的，今天又來了一道！

有n堆石子，每一堆的規則如下：

第一堆每次隻能取2的幂次（即：1，2，4，8，16…）；

第二堆隻能取菲波那契數列中的元素（即每次隻能取1，2，3，5，8…等數量，斐波那契數即後面的數是前面兩個數的和）；

第三堆可以取任意多個，最小1個，最多可以把這一堆石子取完；

第四堆隻能取1和偶數個（即：1,2,4,6,8,10...）；

第五堆隻能取奇數個（即：1,3,5,7,9.....）；

好吧，這樣下去太煩人了，六堆及其以後每堆最多取的數量為堆數編号，即第六堆隻能取（1,2,3,4,5,6），第七堆隻能取（1,2,3,4,5,6,7）....

别看規則很多，但Yougth和Hrdv都是聰明人，現在由Yougth先取，比賽規定誰先取完所有石子既為勝者，輸出勝者的名字。

<dd>有多組測試資料，每組測試資料開始有一個n。</dd>

後面有n個數代表每一堆石子的數量，當n為0是表示輸入結束。(所有資料小于1000)

<dd>假如Yougth赢輸出“Yougth”，Hrdv赢輸出“Hrdv”。</dd>

最近ZKC同學在學博弈，學到了一個偉大的博弈問題--威佐夫博弈。

相信大家都學過了吧？沒學過？沒問題。我将要為你講述一下這個偉大的博弈問題。

有兩堆石子，數量任意，可以不同。遊戲開始由兩個人輪流取石子。

遊戲規定，每次有兩種不同的取法：

一是可以在任意的一堆中取走任意多的石子；

二是可以在兩堆中同時取走相同數量的石子。

最後把石子全部取完者為勝者。

我們今天要做的是求前n個必敗态。

什麼是必敗态？比如我們把（a，b）稱為一種狀态，a，b分别為兩堆石子中所剩的數目。如果a=0，b=0，我們說該種狀态為必敗态，因為我不能再進行遊戲，即使是可以進行，那也是必敗的，你知道，遊戲的我們都是非常聰明的。（0,0）（1,2）（3,5）...都是必敗态，我們今天要做的就是求前n個必敗态。不會？好吧！

我再告訴你：假設第n個必敗态為（a，b）a為前n-1個必敗态中沒有出現的最小自然數，b=a+n。這下大家應該明白了吧。好吧，我們的任務就的要前n個必敗态。規定第0個必敗态為（0,0）。

<dd>多組資料。</dd>

輸入為一個數n（0&lt;=n&lt;=100000）。

<dd>按照要求求出前n個必敗态。輸出格式看下面樣例。</dd>