1148 Werewolf - Simple Version (20 分)

2019-05-20

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.

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 Ais 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:

1	No Solution

作者: CHEN, Yue

单位: 浙江大学

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

题目大意

一群人在玩狼人杀，其中有两个狼人。然后所有人发言，其中一个平民一个狼人说谎了，求哪两个是狼人。

分析

算是比较新颖的题目，只能暴力解决。使用say保存各人说的话，player记录身份，1为平民，-1为狼人。遍历狼人位置，其他位置上的都是平民。然后判断该局面是否合法。规则如下：

k从1至n，如果say[k]<0，但是player中abs(say[k])位置上是1，说明第k个人说谎了。再根据player[k]判断这个是狼人还是平民。如果say[k]>0，但是player[say[k]]<0，同样说谎。如果说谎的平民和狼人各1人，那么输出i，j

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>

using namespace std;
int n,flag;
vector<int> say;
int liewolf,lienormal;
int main() {
    cin>>n;
    say.resize(n+1);
    for(int i=1;i<=n;i++)
        cin>>say[i];
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            lienormal=0;
            liewolf=0;
            vector<int> player(n+1,1);
            player[i]=-1;
            player[j]=-1;
            for(int k=1;k<=n;k++){
                //第k个人说谎
                if(say[k]<0&&player[abs(say[k])]==1){
                    if(player[k]>0)//判断说谎者身份
                        lienormal++;
                    else
                        liewolf++;
                }
                if(say[k]>0&&player[say[k]]==-1){//说谎
                    if(player[k]<0)//判断身份
                        liewolf++;
                    else
                        lienormal++;
                }
            }
            if(lienormal==1&&liewolf==1){
                cout<<i<<" "<<j<<endl;
                return 0;
            }
        }
    }
    cout<<"No Solution"<<endl;
    return 0;
}