PAT-A 1148 Werewolf - Simple Version (20)

Werewolf（狼人杀） is a game in which the players are partitioned into two parties: the werewolves and the human beings. Suppose that in a game,

• player #1 said: “Player #2 is a werewolf.”;
• player #2 said: “Player #3 is a human.”;
• player #3 said: “Player #4 is a werewolf.”;
• player #4 said: “Player #5 is a human.”; and
• player #5 said: “Player #4 is a human.”.

Given that there were 2 werewolves among them, at least one but not all the werewolves were lying, and there were exactly 2 liars. Can you point out the werewolves?

Now you are asked to solve a harder version of this problem: given that there were N players, with 2 werewolves among them, at least one but not all the werewolves were lying, and there were exactly 2 liars. You are supposed to point out the werewolves.

Problem: PAT-A 1148 Werewolf - Simple Version

Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer N (5 ≤ N ≤ 100). Then N lines follow and the i-th line gives the statement of the i-th player (1 ≤ i ≤ N), which is represented by the index of the player with a positive sign for a human and a negative sign for a werewolf.

Output Specification

If a solution exists, print in a line in ascending order the indices of the two werewolves. The numbers must be separated by exactly one space with no extra spaces at the beginning or the end of the line. If there are more than one solution, you must output the smallest solution sequence – that is, for two sequences A=a[1],…,a[M] and B=b[1],…,b[M], if there exists 0 ≤ k < M such that a[i] = b[i] (i ≤ k) and a[k+1]<b[k+1], then A is said to be smaller than B. In case there is no solution, simply print No Solution.

Sample Input 1

1
2
3
4
5
6

5
-2
+3
-4
+5
+4

Sample Output 1

1

1 4

Sample Input 2

1
2
3
4
5
6
7

6
+6
+3
+1
-5
-2
+4

Sample Output 2

1

1 5

Sample Input 3

1
2
3
4
5
6

5
-2
-3
-4
-5
-1

Sample Output 3

1

No Solution

Analysis

题目划重点：

• N 个玩家中有 2 个狼人
• 至少 1 个狼人说谎
• 不是所有狼人都说谎
• 有 2 个玩家说谎

  也就是说，说谎的 2 个玩家中 1 个狼人 1 个人类。题目要求输出 2 个狼人的序号，因此枚举所有可能的 2 个狼人的组合，检查该组合下的说谎玩家数及身份，如果恰为 2 个玩家说谎且 1 个狼人 1 个人类，即为所求解。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> vec(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> vec[i];
    }
    // 枚举所有可能的狼人组合
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {

            // sign记录身份，liar保存说谎者
            vector<int> sign(N + 1, 1), liar;

            // 假设 i, j为狼人
            sign[i] = sign[j] = -1;

            // 自己说的与事实不符，记为说谎者
            for (int k = 1; k <= N; k++) {
                if (sign[abs(vec[k])] * vec[k] < 0) {
                    liar.push_back(k);
                }
            }

            // 说谎者数量为 2，且 1 狼人 1 人类，则 i, j为狼人成立
            if (liar.size() == 2 && sign[liar[0]] * sign[liar[1]] < 0) {
                cout << i << " " << j << endl;
                return 0;
            }
        }
    }
    cout << "No Solution" << endl;
}

Tsukkomi

  没有读清题就开始写了，半路才发现说谎的玩家中1个狼人1个人类。想着能不能用什么巧妙的方法得出结果，无奈太笨。网上搜了搜大佬的解法才知道直接暴力枚举就 vans 了。