Problem:


Score : 300 points

Problem Statement

There are N people numbered 1 to N. Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.

Person i gives A_i testimonies. The j-th testimony by Person i is represented by two integers x_{ij} and y_{ij}. If y_{ij} = 1, the testimony says Person x_{ij} is honest; if y_{ij} = 0, it says Person x_{ij} is unkind.

How many honest persons can be among those N people at most?

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}

Output

Print the maximum possible number of honest persons among the N people.

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.

Sample Input 2

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

Sample Output 2

0

Assuming that one or more of them are honest immediately leads to a contradiction.

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



Sample input:
3
1
2 1
1
1 1
1
2 0


Sample output:
2

Submission status: Accepted

Solution code:
from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd

def lcm(n,m):
    return int(n*m/gcd(n,m))

import re
import array
import copy
import functools
import operator

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace

from queue import PriorityQueue as pq

def reduce(p, q):
    common = fractions.gcd(p, q)
    return (p//common , q//common )
# from itertools import accumulate
# from collections import deque

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

import random

def check(index_person, x_true_or_false, bin_str):
    return (bin_str[index_person] == x_true_or_false)


def main():
    n = int(input().strip())
    ll_xy = [[] for _ in range(n)]
    for i in range(n):
        a = int(input().strip())
        for j in range(a):
            l = list(map(int, input().strip().split()))
            l[0]-=1
            ll_xy[i].append(l)

    cnt=0
    ans=0
    for i in range(2 ** n):     # 場合ループ
        bin_str = list(map(int,(format(i,'b').zfill(n))))
        # eprint("bin_str ",end=": ")
        # eprint(bin_str)
        failure_flag=0
        for j in range(n):      # 人ループ
            if bin_str[j]==1:   # その人を「真実の人」だと仮定している場合
                a=len(ll_xy[j])
                for k in range(a):  # 証言ループ
                    p=ll_xy[j][k][0]
                    if ll_xy[j][k][1] == 0:
                        if check(p,0,bin_str):
                            pass
                        else:
                            failure_flag=1

                    elif ll_xy[j][k][1] == 1:
                        if check(p,1,bin_str):
                            pass
                        else:
                            failure_flag=1
        if failure_flag==0:
            cnt+=1
            ans_temp=0
            for x in bin_str:
                if x==1:
                    ans_temp+=1
            ans=max(ans_temp,ans)
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
xy = []
for i in range(N):
    A = int(input())
    xy.append([])
    for j in range(A):
        xy[i].append(tuple(map(int, input().split())))

ans = 0

for i in range(2 ** N):
    h = [0] * N

    for j in range(N):
        if (i >> j) & 1:
            h[j] = 1
    
    flag = False
    for i in range(N):
        if h[i] == 1:
            for x, y in xy[i]:
                if h[x-1] != y:
                    flag = True
                    break
            if flag:
                break
    
    if not flag:
        ans = max(ans, sum(h))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Xs = []
Ys = []
A = []
for i in range(N):
    a = int(input())
    A.append(a)
    X = []
    Y = []
    for j in range(a):
        x, y = map(int, input().split())
        X.append(x-1)
        Y.append(y)
    Xs.append(X)
    Ys.append(Y)
ans = 0

for i in range(2 ** N):
    flag = True
    l = 0
    for j in range(N):
        if i >> j & 1 == 1:
            l += 1
            for k in range(A[j]):
                if Ys[j][k] + (i >> Xs[j][k] & 1) == 1:
                    flag = False
    if flag:
        ans = max(ans, l)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def is_testimony_correct(hypothesis, testimony):
    # 証言の対象者が仮説上、正直者となっているかを検証。
    for target, is_honest in testimony.items():
        if int(hypothesis[target]) == is_honest:
            continue
        return False
    return True


def is_hypothesis_correct(hypothesis, testimony_dict):
    for witness_num, testimony in testimony_dict.items():
        # 仮説上の正直者の証言だけ検証する
        if hypothesis[witness_num] == "1":
            # 証言を検証
            if is_testimony_correct(hypothesis, testimony):
                continue
            else:
                # 証言に誤りがある場合、Falseで抜ける
                return False
    return True


def main():
    N = int(input())
    testimony_dict = defaultdict(dict)

    # 証人ごとに証言をdictで保存
    for witness_num in range(N):
        for _ in range(int(input())):
            target, is_honest = list(map(int, input().split()))
            testimony_dict[witness_num][target - 1] = is_honest

    # 仮説を検証  e.g.'010010' 正直者が2人 (witness_num =1, 4)
    max_count = 0
    for i in range(1, 2**N):
        # 仮説を01で表現
        hypothesis = format(i, 'b').zfill(N)
        # 仮説が正しい場合のみ、正直者の数でmax_countを更新
        if is_hypothesis_correct(hypothesis, testimony_dict):
            max_count = max(max_count, hypothesis.count(str("1")))
    print(max_count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
l = []
for i in range(n):
    a = int(input())
    for j in range(a):
        a1, a2 = map(int, input().split())
        l.append([i, a1-1, a2])
ans = 0
for i in range(1 << n):
    uso = False
    # print(i)
    for ll in l:
        # ll[0]が正直なのかをチェック]
        # print(ll)
        if i >> ll[0] & 1:  # 正直
            if ((i >> ll[1]) & 1) == ll[2]:
                pass
            else:
                uso = True
                break
        # else:  # 嘘
        #    if ((i >> ll[1]) & 1) == ll[2]:
        #        uso = True
        #        break
    if uso == False:
        # print(bin(i))
        ans = max(ans, len(str(bin(i)).replace('0b', "").replace('0', "")))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = [[] for _ in range(n)]
for i in range(n):
    m = int(input())
    for j in range(m):
        A[i].append(tuple(map(int, input().split())))
ans = 0

for bits in range(2 ** n):
    l = [0] * n
    for i in range(n):
        l[i] = (bits >> i) % 2

    fail = False
    for i in range(n):
        if fail: break
        if l[i] == 0: continue
        for x, y in A[i]:
            if y != l[x-1]:
                fail = True
                break
    else:
        if not fail:
            ans = max(ans, sum(l))

print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(input())
A = []
x = []
y = []

for i in range(N):
    a1 = int(input())
    A.append(a1)
    x1 = []
    y1 = []
    for j in range(a1):        
        x2, y2 = map(int,input().split())
        x1.append(x2)
        y1.append(y2)
    x.append(x1)
    y.append(y1)

ans = []
c = 0
for i in range(1 << N):
    c = 0
    s = 0
    for j in range(N):
        if (i >> j) & 1 == 1:
            for k in range(A[j]):
                if (i >> (x[j][k] - 1)) & 1 != y[j][k]:
                    s = 1
                    break
        if s == 1:
            break
    if s != 1:
        for j in range(N):
            if (i >> j) & 1 == 1:
                c += 1
        ans.append(c)
        
print(max(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    A = [[set(), set()] for _ in range(N)]
    for i in range(N):
        m = int(input())
        for j in range(m):
            x, y = map(int, input().split())
            A[i][y].add(x)

    ans = 0
    for i in range(1 << N):
        h = set()
        u = set()
        for j in range(N):
            if (i >> j) & 1:
                h.add(j+1)
            else:
                u.add(j+1)
        b = True
        for j in range(N):
            if (i >> j) & 1:
                h |= A[j][1]
                u |= A[j][0]
                if u & A[j][1] or h & A[j][0]:
                    b = False
        if b:
            ans = max(ans, bin(i).count("1"))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def is_testimony_correct(hypothesis, testimony):
    # 証言の対象者が仮説上、正直者となっているかを検証。
    for target, is_honest in testimony.items():
        if int(hypothesis[target]) == is_honest:
            continue
        return False
    return True


def is_hypothesis_correct(hypothesis, testimony_dict):
    for witness_num, testimony in testimony_dict.items():
        # 仮説上の正直者の証言だけ検証する
        if hypothesis[witness_num] == "1":
            # 証言を検証
            if is_testimony_correct(hypothesis, testimony):
                continue
            else:
                # 証言に誤りがある場合、Falseで抜ける
                return False
    return True


def main():
    N = int(input())
    testimony_dict = defaultdict(dict)

    # 証人ごとに証言をdictで保存
    for witness_num in range(N):
        for j in range(int(input())):
            target, is_honest = list(map(int, input().split()))
            testimony_dict[witness_num][target - 1] = is_honest

    # 仮説を検証  e.g.'010010' 正直者が2人 (witness_num =1, 4)
    max_count = 0
    for i in range(1, 2**N):
        # 仮説を01で表現
        hypothesis = format(i, 'b').zfill(N)
        # 仮説が正しい場合のみ、正直者の数でmax_countを更新
        if is_hypothesis_correct(hypothesis, testimony_dict):
            max_count = max(max_count, hypothesis.count(str("1")))
    print(max_count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
xys = [[tuple(map(int, input().split())) for j in range(int(input()))] \
       for i in range(n)]

C = set()
for i in range(2 ** n):
    flag = True
    for j in range(n):
        if((i >> j) & 1):
            flag &= all((i >> (x-1)) & 1 == y for x, y in xys[j])
    if flag:
        C.add(i)

print(max([sum([int(bit == '1') for bit in str(bin(c))]) for c in C]))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = (int(i) for i in input().split())
            G[i].append((x-1, y))
            # 人iは人xのことをyと言っている
    ans = 0
    for bit in range(1 << N):
        cur = 0
        good = True  # 矛盾がない
        for i in range(N):
            if bit & (1 << i):
                # 人iは正直者
                # 人iが言う人xの真偽に矛盾があればgood = False
                # 正直者iが嘘をついたらFalse
                cur += 1
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 0:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
                        break
        # print(bit, ":", good)
        if good:
            ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = [0]*n
x = [[] for i in range(n)]
y = [[] for i in range(n)]
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        tmp1,tmp2 = list(map(int,input().split()))
        x[i].append(tmp1-1)
        y[i].append(tmp2)

ans = 0
honest = [0]*n
cnt=0
for i in range(2**n): #bit全探索
    for j in range(n):
        if((i>>j)&1):
            honest[j] = 1
            cnt+=1
        else:
            honest[j] = 0
            
    f = True
    for k in range(n):
        if honest[k]!=1:
            continue
        for l in range(a[k]):
            if y[k][l]!=honest[x[k][l]]:
                f = False
                break
    if f:
        ans = max(ans,cnt)
    cnt=0

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
Asgs = list()

def get_sgs(an):
    sgs = [list(map(int, input().split())) for i in range(an)]
    return sgs


for i in range(n):
    an = int(input())
    Asgs.append(get_sgs(an))

bits = list()
for i in range(2**n):
    bits.append(list(map(int, list(bin(i)[2::].zfill(n)))))


cnt = 0
ps = list()
is_break = False
# print(bits)
# print(Asgs)

for i in range(2**n):
    for j in range(n):
        # j人目の意見
        #j 人目の意見k米
        for k in range(len(Asgs[j])):
            # 正しいとされた人が　とある人を正しいとしているが とある人が正しくないとされている場合
            if bits[i][j] == 1 and Asgs[j][k][1] == 1 and bits[i][Asgs[j][k][0]-1] == 0:
                #矛盾しているので
                bits[i] = [0]*n
            elif bits[i][j] == 1 and Asgs[j][k][1] == 0 and bits[i][Asgs[j][k][0]-1] == 1:
                bits[i] = [0]*n
                
    if bits[i] == [1,1,1]:
        print(i,j,k)
        print('ghogegegaega')
    ps.append(sum(bits[i]))
    

print(max(ps))
#print(ps)
#print(Asgs)

Submission status: Accepted

Solution code:
from itertools import product
N=int(input())
XYs = []
for i in range(N):
    A = int(input())
    XYs.append([tuple(map(int, input().split())) for _ in range(A)])

n=0
for ts in product([1,0], repeat=N):
    for i, t in enumerate(ts):
        if t:
            if not all(ts[x-1] == y for x, y in XYs[i]):
                break
    else:
        n=max(n,sum(ts))
print(n)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = [[] * N for i in range(N)]
    ans = 0

    for i in range(N):
        A = int(input())
        for j in range(A):
            x, y = map(int, input().split())
            S[i].append([x-1, y])

    P = [0]*N
    
    for i in range(2**N):
        for j in range(N):
            if P[j] == 0:
                P[j] = 1
                break
            else:
                P[j] = 0
        
        if sum(P) <= ans:
            continue
        flag = 0
        for p in range(len(P)):
            if P[p] == 1:
                for s in S[p]:
                    if s[1]!= P[s[0]]:
                        flag = 1
        if flag == 1:
            continue
        else:
            ans = sum(P)
        
    print(ans)


 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
wi = [[] for i in range(N)]
for i in range(N):
    wi[i].append([i,1])
    for j in range(int(input())):
        x,y = map(int,input().split())
        wi[i].append([x-1,y])
ans = 0
for i in range(2**N):
    flag = False
    hoge = 0
    witnes = [0]*N
    for j in range(N):
        if i>>j & 1 == 1:
            hoge += 1
            for x,y in wi[j]:
                if i >> x & 1 != y:
                    flag = True
                    break
        if flag:
            break
    if not flag:
        ans = max(ans,hoge)
print(ans)

Submission status: Accepted

Solution code:

def main():
    N = int(input())
    S = [[] * N for i in range(N)]
    ans = 0

    for i in range(N):
        A = int(input())
        for j in range(A):
            x, y = map(int, input().split())
            S[i].append([x-1, y])

    P = [0]*N
    
    for i in range(2**N):
        for j in range(N):
            if P[j] == 0:
                P[j] = 1
                break
            else:
                P[j] = 0
        
        if sum(P) <= ans:
            continue
        flag = 0
        for p in range(len(P)):
            if P[p] == 1:
                for s in S[p]:
                    if s[1]!= P[s[0]]:
                        flag = 1
        if flag == 1:
            continue
        else:
            ans = sum(P)
        
    print(ans)


 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
import itertools

n = int(input())

per_dict = collections.defaultdict(list)
for i in range(n):
  a = int(input())
  for j in range(a):
    x, y = map(int, input().split())
    per_dict[i + 1].append([x,y]) 

for i in range(n, -1, -1):
  flag = True
  for honests in itertools.combinations(range(1, n + 1), i):
    flag = True
    for h in honests:
      for x, y in per_dict[h]:
        if y == 1 and x not in honests:
          flag = False 
        if y == 0 and x in honests:
          flag = False
    if flag == True:
      break
  if flag == True:
    break
print(i)

Submission status: Accepted

Solution code:
N = int(input())
list = [list() for _ in range(N)]
if N == 1:
  print(1)
  exit()

for i in range(N):
  a = int(input())
  for j in range(a):
    x,y = map(int,input().split())
    list[i].append([x,y])

ans = 0
for i in range(2**N):
    flg = False
    do = [0] * N
    for j in range(N):
      if ((i >> j) & 1):
        do[j] = 1
    P = [-1] * N
    for n in range(N):
      if flg:break
      for p in list[n]:
        if P[p[0]-1] == -1:
          if do[n] == 1:
            P[p[0]-1] = p[1]
            if P[p[0]-1] != do[p[0]-1]:
              flg = True
          #else:
          #  if p[1] == 1:
          #    P[p[0]-1] = 0
          #  else:
          #    P[p[0]-1] = 1
        else:
          if do[n] == 1 and P[p[0]-1] != p[1]:
            flg = True
    if flg:
      continue
    ans = max(ans,sum(do))
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = (int(i) for i in input().split())
            G[i].append((x-1, y))
            # 人iは人xのことをyと言っている
    ans = 0
    for bit in range(1 << N):
        cur = 0
        good = True  # 矛盾がない
        for i in range(N):
            if bit & (1 << i):
                # 人iは正直者
                cur += 1
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 0:
                        good = False
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
        # print(bit, ":", good)
        if good:
            ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = [0 for i in range(N)]
xy = [[] for i in range(N)]
value = [[] for i in range(N)]
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        x,y = LI()
        x -= 1
        xy[i].append([x,y])

def make2digits(n):
    digits = [0 for i in range(N)]
    i = 0
    while n > 0:
        digits[i] = n % 2
        n = n // 2
        i += 1
    return digits

def check(digits, xy):
    for i in range(N):
        if digits[i] == 1:
            for signal in xy[i]:
                if digits[signal[0]] == signal[1]:
                    pass
                else:
                    return False
    return True
ans = -1
for i in range(2**N):
    digits = make2digits(i)
    if check(digits, xy):
        ans = max(ans, sum(digits))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
B = [[] for i in range(N)]
C = []
for i in range(N):
  M = int(input())
  C.append(M)
  for j in range(M):
    B[i].append([int(s) for s in input().split()])
    
ans = 0
for i in range(2**N):
    array = bin(i)[2:]
    n = len(array)
    array = "0"*(N-n) + array  #give 0 in oreder to the length will be N
    array = [int(k) for k in list(array)]
    
    #check if the array is feasible or not, if feasible count the number of "1"
    flag = True
    for j in range(N):
        a = array[j]
        if a==1:
            for e,f in B[j]:
                if f != array[e-1]:
                    flag = False
    if flag==True:
        ans = max(ans, sum(array))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

A = []
for i in range(N):
    M = int(input())
    T = {}
    for _ in range(M):
        x, y = map(int, input().split())
        T[x - 1] = y
    A.append(T)

def solve(state):
    memo = {i: (state >> i & 1) for i in range(N)}
    for i, a in enumerate(A):
        for x, y in a.items():
            if state >> i & 1:
                if x in memo and memo[x] != y:
                    return False
                memo[x] = y
    return True

ans = 0
for i in range(2 ** N):
    if solve(i):
        ans = max(ans, bin(i).count("1"))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
    Ai = int(input())
    for _ in range(Ai):
        x, y = map(int, input().split())
        A[i].append((x - 1, y))


def countBit(x):
    if x == 0:
        return 0
    else:
        return countBit(x >> 1) + (x & 1)


res = 0
for bits in range(2 ** N):
    bits_ = bin(bits)
    consistency = True
    for i, testimony in enumerate(A):
        if not ((bits >> i) & 1):
            continue
        for t in testimony:
            if ((bits >> t[0]) & 1) ^ t[1]:
                consistency = False

    if consistency:
        res = max(res, countBit(bits))

print(res)

Submission status: Accepted

Solution code:
import itertools

N = int(input())

xy_list = [{} for i in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = list(map(int, input().split()))
        xy_list[x-1][str(i)] = y

max_n_honest = 0
for n_honest in range(1, N + 1):
    for is_honest in itertools.combinations(range(N), n_honest):
        aaa = True
        for h_idx in range(N):
            target_is_honest = int(h_idx in is_honest)
            testimony = xy_list[h_idx]
            for honest_idx in is_honest:
                if str(honest_idx) in testimony:
                    if testimony[str(honest_idx)] != target_is_honest:
                        aaa = False
                        break
        if not aaa:
            continue
        n_honest = len(is_honest)

        if n_honest > max_n_honest:
            max_n_honest = n_honest

print(max_n_honest)

Submission status: Accepted

Solution code:
import sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n_a = I()
As = [0]
for i in range(n_a):
    n_t = I()
    Ts = []
    for j in range(n_t):
        Ts.append(Is())
    As.append(Ts)

cand = []
def dfs(i,st):
    if i < n_a:
        dfs(i+1,st+[i+1])
        dfs(i+1,st)
    elif i == n_a:
        flag = True
        tf = [None] * (n_a + 1)
        for j in range(1,n_a+1):
            if j in st:
                tf[j] = 1
            else:
                tf[j] = 0
        for j in range(1,n_a+1):
            if j not in st:
                continue
            for e in As[j]:
                x,y = e
                if tf[x] != y:
                    #print("false",i,tf,st)
                    flag = False
        if flag:
            #print("true",i,tf,st)
            cand.append(tf)
dfs(0,[])
ans = 0
for e in cand:
    ans = max(ans,e.count(1))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

testimony_dict = {}
for i in range(n):
    a = int(input())
    testimony_dict[i + 1] = []
    for j in range(a):
        xy = input().split(' ')
        testimony_dict[i + 1].append(xy)

max_valid_bin = ''
for i in range(2 ** n - 1, 0, -1):
    is_valid = True
    bin_i = format(i, '0{}b'.format(n))
    for j in range(1, len(bin_i) + 1):
        if bin_i[j - 1] == '1':
            for xy_list in testimony_dict[j]:
                if bin_i[int(xy_list[0]) - 1] != xy_list[1]:
                    is_valid = False
    if is_valid:
        max_valid_bin = bin_i
        break

print(len([i for i in max_valid_bin if i == '1']))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N = int(input())
M = []
for i in range(N):
    A = int(input())
    XY = []
    for j in range(A):
        X, Y = map(int, input().split())
        XY.append([X, Y])
    M.append(XY)

# 残り嘘つき人数を渡して全パターンを列挙する
def check(n, l):
    # 残り0なら以降を全部正直者にして判定
    if n == 0:
        l += [1] * (N - len(l))
        return judge(l)
    # 残りと未確定人数が同じなら全部嘘つきにして判定
    if n == N - len(l):
        l += [0] * (N - len(l))
        return judge(l)

    # iが正直者1
    if check(n, l + [1]):
        return True
    # iが嘘つき0
    if check(n - 1, l + [0]):
        return True

    return False

# 矛盾がないかチェックする
def judge(l):
    for i in range(len(M)):
        # 嘘つきなら無視する
        if l[i] == 0:
            continue
        # 正しいかチェック
        ii = M[i]
        for j in range(len(ii)):
            jj = ii[j]
            if l[jj[0] - 1] != jj[1]:
                return False
    return True

# 嘘つき人数を増やしながら調べる
for i in range(N + 1):
    if check(i, []):
        print(N - i)
        break;

Submission status: Accepted

Solution code:
import sys
inputs = sys.stdin.readlines()

n = int(inputs[0])
A = []
B = []

i = 1
for _ in range(n):
    a = int(inputs[i])
    i += 1
    A.append(a)
    B.append([tuple(map(int, inputs[j].split())) for j in range(i, i+a)])
    i += a

C = set()
for i in range(2 ** n):
    flag = True
    for j in range(n):
        if((i >> j) & 1):
            flag &= all((i >> (x-1)) & 1 == y for x, y in B[j])
    if flag:
        C.add(i)

print(max([sum([int(bit == '1') for bit in str(bin(c))]) for c in C]))

Submission status: Accepted

Solution code:
n = int(input())
xy=[[] for _ in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        xy[i].append(list(map(int,input().split())))
len_xy=len(xy)
ans=0
for i in range(2**n):
    num=str(bin(i))[2:]
    num=list(num.zfill(n))
    flag=True
    for j in range(n):
        if num[j]=='1':
            for x,y in xy[j]:
                if num[x-1]!=str(y):
                    flag=False
    if flag:
        ans=max(ans,num.count('1'))
print(ans)

Submission status: Accepted

Solution code:
ans=0
n=int(input())
comments={}
for i in range(n):
    num=int(input())
    comment=[]
    for j in range(num):
        comment.append(list(map(int,input().split(" "))))
    comments[i]=comment

for i in range(2**n):
    evidences={}
    people=list(str(format(i,'b').zfill(n)))
    conflict=False
    for idx,person in enumerate(people):
        if person=='1':
            for comment in comments[idx]:
                evidences.setdefault(comment[0],[]).append(comment[1])
    for key,value in evidences.items():
        personality = int(people[key-1])
        if value.count(personality) != len(value):
            conflict=True
            break
    if not conflict:
        ans=people.count('1')
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

sayTable = []
for i in range(n):
	a = int(input())
	
	sayArray = []
	for j in range(a):
		x, y = [int(v) for v in input().split()]
		sayArray.append((x-1, y+1))
	sayTable.append(sayArray)

def countHonest(honest):
	count = 0
	for v in honest:
		if v == 2:
			count += 1
	return count

def checkHonest(sayArray, honest):
	for x, y in sayArray:
		if honest[x] == 0:
				continue
		if y == 2 and honest[x] != 2:
			return False
	return True

def checkHonestAll(sayTable, honest):
	for i in range(n):
		h = honest[i]
		if h != 2:
			continue
		sayArray = sayTable[i]
		for x, y in sayArray:
			if y != honest[x]:
				return False
	return True

def setHonest(sayArray, honest):
	for x, y in sayArray:
		honest[x] = y

def search(sayTable, honest, i):
	if i >= n:
		if checkHonestAll(sayTable, honest):
			return countHonest(honest)
		else:
			return 0

	count = 0
	h = honest[i]
	sayArray = sayTable[i]
	if (h == 0 or h == 2) and checkHonest(sayArray, honest):
		copyHonest = honest[:]
		setHonest(sayArray, copyHonest)
		copyHonest[i] = 2
		c = search(sayTable, copyHonest, i+1)
		if count < c:
			count = c

	honest[i] = 1
	c = search(sayTable, honest, i+1)
	if count < c:
		count = c
	return count

print(search(sayTable, [0] * n, 0))

Submission status: Accepted

Solution code:
import itertools

def check(honest_people):
	ans = True
	for i in honest_people:
		for x, y in shogen[i]:
			if (y == 1 and x not in honest_people) or (y == 0 and x in honest_people):
				ans = False
	return ans

if __name__ == "__main__":
	N = int(input())
	shogen = []
	for i in range(N):
		A = int(input())
		shogen_i = []
		for i in range(A):
			x, y = map(int, input().split())
			shogen_i.append((x - 1, y))
		shogen.append(shogen_i)

	seq = [i for i in range(N)]
	for i in range(0, N + 1):
		comb = list(itertools.combinations(seq, i))
		for honest_people in comb:
			if check(list(honest_people)):
				ans = i
	print(ans)

Submission status: Accepted

Solution code:
N=int(input().strip())
A=[0]*N
xy=[]
for i in range(N):
    A[i]= int(input().strip())
    xy.append([list(map(int, input().split())) for j in range(A[i])])

def count_ones_by_minus(num):
    count = 0
    while num:
        num &= num -1
        count += 1
    return count

ans=0
for k in range(2**N):# combination
    ok=True
    for i in range(N): # people
        # lst=[0]*N # everyone dishonest
        if k>>i & 1: # check lowest bit
            for j in range(A[i]): # opinion
                if xy[i][j][1] != k >> (xy[i][j][0]-1) &1:
                    ok=False
    # print(bin(k),bin(lst_h))
    if ok:
        ans=max(ans,count_ones_by_minus(k))
    # print(ans)

print(ans)

Submission status: Accepted

Solution code:
A = [0 for _ in range(20)]
X = [[0 for _ in range(20)] for _ in range(20)]
Y = [[0 for _ in range(20)] for _ in range(20)]

def counter(x):
    if x == 0:
        return 0
    else:
        return counter(x >> 1) + (x & 1)

n = int(input())

for i in range(1, n+1):
    A[i] = int(input())
    for j in range(1, A[i]+1):
        X[i][j], Y[i][j] = map(int, input().split())


ans = 0
for bits in range(1, (1 << n)):
    ok = True
    for i in range(1, n+1):
        if not (bits & (1 << (i-1))):
            continue
        for j in range(1, A[i]+1):
            if(((bits >> (X[i][j]-1)) & 1) ^ Y[i][j]): ok = False
    if(ok): ans = max(ans, counter(bits))

print(ans)