Submission #54100168

---

Source Code Expand

def is_valid_combination(keys, K, test_cases):
    for C, A, R in test_cases:
        valid_key_count = sum(1 for key in A if keys[key])
        if (R == 'o' and valid_key_count < K) or (R == 'x' and valid_key_count >= K):
            return False
    return True

def count_valid_combinations(N, M, K, test_cases):
    valid_combinations = 0
    for combination in range(1 << N):
        keys = [bool(combination & (1 << i)) for i in range(N)]
        if is_valid_combination(keys, K, test_cases):
            valid_combinations += 1
    return valid_combinations

def main():
    N, M, K = map(int, input().split())

    test_cases = []
    for _ in range(M):
        parts = input().split()
        C = int(parts[0])
        A = list(map(lambda x: int(x) - 1, parts[1:C+1]))
        R = parts[C+1]
        test_cases.append((C, A, R))

    result = count_valid_combinations(N, M, K, test_cases)
    print(result)

if __name__ == "__main__":
    main()

Submission Info

Judge Result