Truth-teller and Liar Detection: Determining the Number of Liars in a Group

This problem deals with a group of people where some are liars who always tell lies and others are truth-tellers. Each person makes a statement about the number of liars in the group. The objective is to determine if these statements are contradictory and if not, find the number of liars in the group.

Input: The input consists of multiple test cases. Each test case starts with an integer n, representing the number of people in the group. The next line contains n integers, where the i-th integer represents the number of liars claimed by the i-th person.

Output: For each test case, output a single integer. If the statements are contradictory, output -1. Otherwise, output the number of liars in the group. If there are multiple possible answers, output any one of them.

Example:

Input:

7
2
1 2
2
2 2
2
0 0
1
1
1
0
5
5 5 3 3 5
6
5 3 6 6 3 5

Output:

1
-1
0
-1
0
3
4

Code Explanation:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 10;

int n, a[maxn];

int main() {
    int T; cin >> T;
    while(T--) {
        cin >> n;
        int sum_0 = 0, sum_1 = 0;
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
            if(a[i] == 0) sum_0++;
            if(a[i] == 1) sum_1++;
        }
        if(sum_1 == 0) { // 没有说谎者
            cout << sum_0 << endl;
            continue;
        }
        if(sum_1 > 1) { // 至少有两个说谎者，矛盾
            cout << -1 << endl;
            continue;
        }
        int cnt = 0; // 统计说谎者的数量
        for(int i = 1; i <= n; i++) {
            if(a[i] > 1) cnt++;
        }
        if(cnt == a[sum_1]) cout << cnt << endl;
        else cout << -1 << endl;
    }
    return 0;
}

The code uses the following logic:

1. Initialization:

   • Reads the number of test cases (T).
   • Initializes variables for counting truth-tellers (sum_0), liars (sum_1), and the total number of liars (cnt).

2. Input Processing:

   • Reads the number of people (n) and the number of liars claimed by each person (a[i]) for each test case.
   • Counts the number of people who claim there are 0 liars (sum_0) and 1 liar (sum_1).

3. Contradiction Check:

   • Case 1: No liars claimed: If sum_1 is 0, it means everyone claims there are no liars. In this case, all statements are consistent, and the number of liars is equal to sum_0. The output is sum_0.
   • Case 2: Multiple liars claimed: If sum_1 is greater than 1, it implies there are at least two people claiming there's a liar. This leads to a contradiction, as a liar cannot claim there's another liar. The output is -1.

4. Liar Identification:

   • If sum_1 is 1, it means only one person claims there's a liar. This person must be a truth-teller, and their claim about the number of liars must be true.
   • Count the number of people claiming there are more than 1 liar (cnt).
   • If cnt matches the number of liars claimed by the single person who claimed there's a liar, then this person's claim is consistent, and the output is cnt. Otherwise, the statements are contradictory, and the output is -1.

The code efficiently analyzes the input to identify potential contradictions and outputs the number of liars or -1 if a contradiction exists.