ZeroJudge 解題筆記：m581. 狼人殺 (Werewolves)

作者：王一哲
日期：2025年5月29日



ZeroJudge 題目連結：m581. 狼人殺 (Werewolves)

解題想法

不斷讀取要淘汰的人編號，直到讀到 0、無解或是沒有狼人為止。特別容易出錯的地方在於，如果無解，仍然需要讀完測資，不能直接 break。

Python 程式碼

使用時間約為 20 ms，記憶體約為 3.3 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # n 個人
    arr = [-2] + list(map(int, input().split()))  # 每個人的身份，配合編號開頭多一項，-2 為已淘汰
    werewolves = sum([a == -1 for a in arr])  # 狼人數量
    solve = True  # 是否有解
    while True:  # 不斷讀取要淘汰的人
        k = int(input())  # 要淘汰的人編號
        if k == 0: break  # 讀到 0 中止迴圈
        elif arr[k] == -2:  # 如果 k 號已淘汰
            solve = False  # 無解，但是要讀完資料，不能 break
        else:
            if arr[k] == -1: werewolves -= 1  # 如果 k 號是狼人，數量減 1
            arr[k] = -2  # k 號淘汰
    if not solve: print("Wrong")  # 無解，印出 Wrong
    elif werewolves == 0: print("Townsfolk")  # 好人陣營獲勝
    else: print("Werewolves")  # 狼人陣營獲勝

C++ 程式碼

使用時間約為 2 ms，記憶體約為 80 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n;  // n 個人
    while(scanf("%d", &n) != EOF) {
        int arr[n+1];  // 每個人的身份，配合編號開頭多一項，-2 為已淘汰
        arr[0] = -2;
        int werewolves = 0;  // 狼人數量
        for(int i=1; i<=n; i++) {
            int a; scanf("%d", &a);
            arr[i] = a;
            if (a == -1) werewolves++;
        }
        bool solve = true;  // 是否有解
        while(true) {  // 不斷讀取要淘汰的人
            int k; scanf("%d", &k);  // 要淘汰的人編號
            if (k == 0) {
                break;  // 讀到 0 中止迴圈
            } else if (arr[k] == -2) {  // 如果 k 號已淘汰
                solve = false;  // 無解，但是要讀完資料，不能 break
            } else {
                if (arr[k] == -1) werewolves--;  // 如果 k 號是狼人，數量減 1
                arr[k] = -2;  // k 號淘汰
            }
        }
        if (!solve) printf("Wrong\n");  // 無解，印出 Wrong
        else if (werewolves == 0) printf("Townsfolk\n");  // 好人陣營獲勝
        else printf("Werewolves\n");  // 狼人陣營獲勝
    }
    return 0;
}