2013-02-07 13:52:45Morris

[ZJ][博弈] d246. Stone Game

內容 :

         

Jack和Jim在玩一種有趣的拿石頭遊戲。一開始時有N堆石頭,各堆有Pi個石頭(i=1..N, 1 <= Pi <= 2*109)。他們輪流拿一些石頭。拿的規則如下:一次僅能選擇一堆石頭,然後拿走最多K個數目的石頭。如此輪流下去,拿到最後一顆石頭的人就是贏家。遊戲開始時Jack先拿,然後才是Jim。現在請你幫助Jack判斷面對一開始的石頭堆,他是否一定能贏。

輸入說明 :

每組測試資料2列,第一列含有整數N,k。第二列有N個整數,代表這N堆石頭各堆石頭的個數。N=0代表輸入結束。

n<=200 ,k<=200

輸出說明 :

對每一組測試資料,如果Jack一定能贏請輸出Yes,否則輸出No。

範例輸入 :help

1 200
100
3 200
1 5 1
4 200
1 1 1 1
3 100
123 123 123
3 100
123 123 1
1 100
101
0

範例輸出 :

Yes
Yes
No
Yes
Yes
No

提示 :

XOR 與 撿石子理論

出處 :

(管理:nanj0178)

跟單堆遊戲有點相關,打一下就過了,我也不懂。

#include <stdio.h>

int main() {
    int n, k;
    while(scanf("%d %d", &n, &k) == 2) {
        int res = 0, p;
        while(n--) {
            scanf("%d", &p);
            res ^= p%(k+1);
        }
        puts(res ? "Yes" : "No");
    }
    return 0;
}