【PAT甲级 - C++题解】1148 Werewolf - Simple Version

简介: 【PAT甲级 - C++题解】1148 Werewolf - Simple Version

1148 Werewolf - Simple Version


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.


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:

5
-2
+3
-4
+5
+4

Sample Output 1:

1 4

Sample Input 2:

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

Sample Output 2 (the solution is not unique):

1 5

Sample Input 3:

5
-2
-3
-4
-5
-1

Sample Output 3:

No Solution


题意

一局游戏中,有 N 个玩家,其中只有 2 个是狼人,并且 2 个狼人中有且只有 1 狼人说的是假话,全场一共只有 2 人说的是假话。


现在给定每个人用一个整数 x 来代表其发言情况,如果 x 大于 0 ,则该人说 x 是好人;反之如果 x 小于 0 ,则该人说 x 是狼人。


现在需要我们找到这组狼人并输出它们的编号,每个人的编号从 1 到 N ,如果答案不唯一,则输出最小序列解。


思路

由于本题数据量不大,所以我们可以用枚举的方法来做,先枚举这 N 个玩家中哪两个人是狼,再去判断当这两个人是狼的时候,是否满足题目的条件。如果满足则直接输出结果,否则继续往下枚举。


代码

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int q[N];
int n;
//如果说的假话返回1,说的真话返回0
int judge(int u, int i, int j)
{
    int t = q[u];
    //该人说t是好人
    if (t > 0)
    {
        if (t == i || t == j)  return 1;
        return 0;
    }
    //该人说t是狼人
    t = -t;
    if (t == i || t == j)  return 0;
    return 1;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)   cin >> q[i];
    //枚举所有狼人的可能性
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            //只能恰好有一个狼人说假话
            int s = judge(i, i, j) + judge(j, i, j);
            if (s != 1)    continue;
            //只能恰好有两个人说假话
            s = 0;
            for (int u = 1; u <= n; u++)
                s += judge(u, i, j);
            if (s != 2)    continue;
            //满足条件,直接输出答案
            cout << i << " " << j << endl;
            return 0;
        }
    //没有找到一个答案
    puts("No Solution");
    return 0;
}
目录
相关文章
|
C++
【PAT甲级 - C++题解】1040 Longest Symmetric String
【PAT甲级 - C++题解】1040 Longest Symmetric String
296 0
|
算法 C++
【PAT甲级 - C++题解】1044 Shopping in Mars
【PAT甲级 - C++题解】1044 Shopping in Mars
378 0
|
C++
【PAT甲级 - C++题解】1117 Eddington Number
【PAT甲级 - C++题解】1117 Eddington Number
359 0
|
存储 C++ 容器
【PAT甲级 - C++题解】1057 Stack
【PAT甲级 - C++题解】1057 Stack
329 0
|
存储 C++
【PAT甲级 - C++题解】1055 The World‘s Richest
【PAT甲级 - C++题解】1055 The World‘s Richest
253 0
|
C++
【PAT甲级 - C++题解】1051 Pop Sequence
【PAT甲级 - C++题解】1051 Pop Sequence
301 0
|
存储 定位技术 C++
【PAT甲级 - C++题解】1091 Acute Stroke
【PAT甲级 - C++题解】1091 Acute Stroke
250 0
|
存储 人工智能 C++
【PAT甲级 - C++题解】1085 Perfect Sequence
【PAT甲级 - C++题解】1085 Perfect Sequence
299 0
|
C++
【PAT甲级 - C++题解】1046 Shortest Distance
【PAT甲级 - C++题解】1046 Shortest Distance
285 0
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。