解題區/解題區 - UVa

UVa 1566 - John

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

撿石子遊戲，但是相反地拿走最後一個的人輸。

(通常 Nim 遊戲都是無法進行操作的人輸)

Sample Input

1
2
3
4
5
2
3
3 5 1
1
1

Sample Output

1
2
John
Brother

Solution

上網搜索一下 Sprague Grundy - Jia Zhihao，簡單地說曾經有個大陸人在選訓隊講這個，所以不太算是定理名稱。

有興趣的人可以上網搜尋，主要細分四種狀態，是否每一堆大小都為 1，堆數的奇偶數。剛好有兩個必勝狀態、兩個必輸狀態，彼此之間會相互轉移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Anti-SG, Sprague Grundy - Jia Zhihao
#include <stdio.h> 
int main() {
    int testcase, cases = 0;
    int n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int sg = 0, s1 = 1;
        int x;
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            sg ^= x;
            s1 &= x <= 1;
        }
        if (s1)
            printf("%s\n", sg == 0 ? "John" : "Brother");
        else
            printf("%s\n", sg ? "John" : "Brother");
    }
    return 0;
}