PAT Basic 1089. 狼人杀-简单版

1. 题目描述：

以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1 号玩家说：“2 号是狼人”，2 号玩家说：“3 号是好人”，3 号玩家说：“4 号是狼人”，4 号玩家说：“5 号是好人”，5 号玩家说：“4 号是好人”。已知这 5 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？

本题是这个问题的升级版：已知 \(N\) 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家？

2. 输入格式：

输入在第一行中给出一个正整数 \(N\)（\(5≤N≤100\)）。随后 \(N\) 行，第 \(i\) 行给出第 \(i\) 号玩家说的话（\(1≤i≤N\)），即一个玩家编号，用正号表示好人，负号表示狼人。

3. 输出格式：

如果有解，在一行中按递增顺序输出 2 个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最小序列解 —— 即对于两个序列 \(A=a[1],...,a[M]\) 和 \(B=b[1],...,b[M]\)，若存在 \(0≤k<M\) 使得 \(a[i]=b[i]\) （\(i≤k\)），且 \(a[k+1]<b[k+1]\)，则称序列 \(A\) 小于序列 \(B\)。若无解则输出 No Solution。

4. 输入样例：

5
-2
+3
-4
+5
+4

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

5
-2
-3
-4
-5
-1

5. 输出样例：

1 4

1 5 (解不唯一)

No Solution

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

一开始想着能找出规律，但这种智力题真做不明白。。。还是顺序遍历每种狼人的可能进行判断和输出，这样也能满足最小序列解的要求。编写子函数isSolution()进行逻辑判断，根据题目要求有且只有1个好人和1个狼人在撒谎。

My Code:

#include <stdio.h>

#define MAX_PLAYER (100+1)

int isSolution(const int *words, int playerCount, int wolf1, int wolf2);

int main(void)
{
    int playerCount = 0;
    int words[MAX_PLAYER] = {0};
    int i=0, j=0; // iterator
    //int wolfLieCount=0, goodLieCount=0;
    
    scanf("%d", &playerCount);
    //printf("%d\n", playerCount);
    
    for(i=1; i<=playerCount; ++i)
    {
        scanf("%d", &words[i]);
        //printf("%d\n", words[i]);
    }
    
    for(i=1; i<playerCount; ++i)
    {
        for(j=i+1; j<=playerCount; ++j)
        {
            if(isSolution(words, playerCount, i, j))
            {
                printf("%d %d\n", i, j);
                return 0;
                //break; // only exit one loop
            }
        }
    }
    
    if(i==playerCount) // no solution
    {
        printf("No Solution\n");
    }
    
    return 0;
}

int isSolution(const int *words, int playerCount, int wolf1, int wolf2) // 1 means is a solution, 0 means not.
{
    int wolfLieCount=0, goodLieCount=0;
    int i=1; // iterator
    
    for(i=1; i<=playerCount; ++i)
    {
        if(i==wolf1 || i==wolf2) // wolf talk
        {
            if(words[i]>0 && (words[i] == wolf1 || words[i] == wolf2)) // lie a wolf is good
            {
                ++wolfLieCount;
                //printf("wolf++: %d\n", i);
            }
            else if(words[i]<0 && (-words[i] != wolf1 && -words[i] != wolf2)) // lie a good is wolf
            {
                ++wolfLieCount;
                //printf("wolf++: %d\n", i);
            }
        }
        else // good talk
        {
            if(words[i]>0 && (words[i] == wolf1 || words[i] == wolf2)) // lie a wolf is good
            {
                ++goodLieCount;
                //printf("good++: %d\n", i);
            }
            else if(words[i]<0 && (-words[i] != wolf1 && -words[i] != wolf2)) // lie a good is wolf
            {
                ++goodLieCount;
                //printf("good++: %d\n", i);
            }
        }
    }
    
    //printf("wolfLie: %d, goodLie: %d\n", wolfLieCount, goodLieCount);
    
    if(wolfLieCount==1 && goodLieCount==1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}