Overview

Given \(N\) terminals, find the minimum number of infected terminals that is consistent with all scan results.

Analysis

In this problem, each terminal has a binary state: “infected” or “not infected.” In such cases, we want to consider trying all possible patterns. Since the number of terminals \(N\) is at most \(16\), even if we represent the infection state of all terminals as a bit string, there are only \(2^{16} = 65536\) possibilities, which is small enough to allow exhaustive search.

Each scan returns “whether a given set contains an infected terminal,” so for a given infection pattern, we can verify whether it satisfies the conditions by checking each scan result one by one for consistency.

The straightforward approach of trying all patterns and checking each one against all scans is computationally feasible. Since the constraints are loose, no more complex algorithm is needed.

Algorithm

1. Manage the infection status of each terminal using a bitmask, and try all patterns from \(0\) to \(2^N - 1\).
2. Construct the set of infected terminals corresponding to each pattern (e.g., if bit \(i\) is set, terminal \(i+1\) is infected).
3. Check whether each scan result is consistent with the pattern:
   • If the scan target contains an infected terminal, the result should be \(1\).
   • If it does not, the result should be \(0\).
4. If there is no contradiction, record the number of infected terminals for that pattern and update the minimum.
5. After examining all patterns, output the minimum number of infected terminals.

Complexity

• Time complexity: \(O(2^N \cdot M \cdot N)\)
  • For each of the \(2^N\) patterns, check \(M\) scans, and for each scan, process up to \(N\) terminals.
• Space complexity: \(O(M + N)\)
  • Space needed to store the scan information and the set of infected terminals.

Implementation Notes

• Terminal numbers are 1-indexed, so be careful when mapping to bit positions (e.g., use i + 1).

• The check for each scan can be written simply by using set intersection (common elements).

• By using a set, you can efficiently determine whether a scan’s target contains an infected terminal.

  Source Code

def main():
    N, M = map(int, input().split())
    scans = []
    for _ in range(M):
        line = list(map(int, input().split()))
        K = line[0]
        S = line[1:K+1]
        R = line[K+1]
        scans.append((S, R))
    
    min_infected = N + 1
    
    # 全ての感染パターンを試す (2^N通り)
    for mask in range(1 << N):
        infected = set()
        for i in range(N):
            if mask & (1 << i):
                infected.add(i + 1)  # 端末番号は1-indexed
        
        # スキャン結果と矛盾がないかチェック
        valid = True
        for S, R in scans:
            intersect = infected & set(S)
            has_infected = len(intersect) > 0
            result = 1 if has_infected else 0
            if result != R:
                valid = False
                break
        
        if valid:
            min_infected = min(min_infected, len(infected))
    
    print(min_infected)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.