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

Solution (Python):



n = int(input())
mtx = []

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

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

count = 0
for sample in range(2**n):
    judge = True
    for i in range(n):
        if not sample & (1 << i):
            continue
        else:
            for j in mtx[i]:
                if ((sample >> (j[0] - 1)) & 1) ^ j[1]:
                    judge = False
                    break
            if not judge:
                break
    if judge:
        count = max(count, counter(sample))
    
print(count)

Solution (Python):



n = int(input())
info = []
for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        info.append([i, x-1, y])

ans = 0
for i in range(2 ** n):
    bit = [0] * n
    for j in range(n):
        if ((i >> j) & 1):
            bit[j] = 1

    flag = True
    
    for idx, j in enumerate(bit):
        if j == 1:
            for k in [x for x in info if x[0] == idx]:
                
                if bit[k[1]] != k[2]:
                    flag = False
    if flag:
        ans = max(ans, sum(bit))
    
print(ans)

Solution (Python):
n=int(input())
d=[[-1 for j in range(n)] for i in range(n)]
ans=0
for i in range(n):
    for j in range(int(input())):
        x,y=map(int,input().split())
        d[i][x-1]=y


for x in range(2**n):
    s=bin(x)[2:].zfill(n)
    sgn=1
    for i in range(n):
        if int(s[i])==1:
            for j in range(n):
                if d[i][j]!=-1 and d[i][j]!=int(s[j]):
                    sgn=0

                    break

        if sgn==0: break
    if sgn==1:
        tmp=sum(int(s[k]) for k in range(n))
        ans=max(ans,tmp)

print(ans)

Solution (Python):
from itertools import combinations

n = int(input())
lst = []
for i in range(n):
  lst.append([0] * n)
  a = int(input())
  for j in range(a):
    x, y = map(int, input().split())
    lst[i][x-1] = y * 2 - 1

for ans in range(n, 0, -1):
  for x in combinations(range(n), ans):
    for y in x:
      for i, z in enumerate(lst[y]):
        if (z == 1 and i not in x) or (z == -1 and i in x):
          break
      else:
        continue
      break
    else:
      break
  else:
    continue
  print(ans)
  break
else:
  print(0)

Solution (Python):
n = int(input())
v = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        v[i].append(list(map(int, input().split())))

ans = 0
for i in range(2**n):
    s = format(i, "b").zfill(n)
    flag = 1
    for j in range(len(s)):
        if s[j] == "1":
            for k in range(len(v[j])):
                if v[j][k][1] == 1 and s[v[j][k][0]-1] == "0":
                    flag = 0
                    break
                if v[j][k][1] == 0 and s[v[j][k][0]-1] == "1":
                    flag = 0
                    break
    """    else:
            for k in range(len(v[j])):
                if v[j][k][1] == 1 and s[v[j][k][0]-1] == "1":
                    flag = 0
                    break
                if v[j][k][1] == 0 and s[v[j][k][0]-1] == "0":
                    flag = 0
                    break"""
    if flag == 1:
        ans = max(ans, s.count("1"))

print(ans)

Solution (Python):
n=int(input())
a=[]
d=[]
for i in range(n):
  c=[]
  b=int(input())
  d.append(b)
  for j in range(b):
    c.append(list(map(int,input().split())))
  a.append(c)


count=0
for i in range(2**n):
  x=[0]*n
  pre=0
  for j in range(n):
    if ((i>>j)&1):
      x[n-1-j]=1 
      for l in range(d[j]):
        if ((i>>(a[j][l][0]-1))&1)!=a[j][l][1]:
          pre+=1
  if pre!=0:
    count=count
  else:
    count=max(count,x.count(1))
print(count)

Solution (Python):

import itertools
import numpy as np
 
N = int(input())
info = []
for i in range(N):
    A = int(input())
    for _ in range(A):
        x,y = map(int,input().split())
        info.append((i,x-1,y))
A = np.array(list(itertools.product([0,1],repeat=N)), np.bool)
for i,x,y in info:
    bl = (~A[:,i]) | (A[:,x] == bool(y))
    A = A[bl]
    
answer = A.sum(axis = 1).max()
print(answer)

Solution (Python):
import copy


n = int(input())
def makebin(n):

  ans = []
  for i in reversed(range(2 ** n)):
    tmp = bin(i)
    ans.append(tmp[2:].zfill(n))
  return ans
binData = makebin(n)



data = {}
for i in range(n):
  a = int(input())
  alist = []
  for j in range(a):
    
    x,y = list(map(int,input().split()))
    alist.append((x,y))
  
  data[i] = alist[:]




answer = []
flag = 1
for i in binData: 
  
  memo = []
  for k in range(n):
    memo.append(i[k])
  flag = 1 
  
  for j in range(n):
    
    
    s = i[j]
    t = memo[j]
    
    if i[j] == '1':
      
      memo[j] = '1'
      
      
      
      for test in data[j]:
        
        if (memo[test[0]-1] == '1' and test[1] == 0 ) or \
          (memo[test[0]-1] == '0' and test[1] == 1):
          flag = 0
          memo = ['0'] * n
          break

        else:
          memo[test[0]-1] = str(test[1])
      if flag == 0:
        break
    
  if j == n-1:
    answer.append(memo.count('1'))
print(max(answer))

Solution (Python):
n = int(input())

xy = []
a_list = []

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



num = 2**n
hito = []
flag = True

for i in reversed(range(num)):
    
    hito = []
    tmp = i
    while tmp != 0:
        if tmp % 2 == 1:
            hito.append(1)
        else:
            hito.append(0)
        tmp //= 2
    """
    if len(hito) == 2:
        hito.append(0)
    elif len(hito) == 1:
        hito.append(0)
        hito.append(0)
    elif len(hito) == 0:
        hito.append(0)
        hito.append(0)
        hito.append(0)
    """
    if len(hito) != n:
        for j in range(n-len(hito)):
            hito.append(0)
    
    hito = hito[::-1]
    
    
    number = 0
    flag = True
    
    
    for j in range(n):
        
        for k in range(a_list[j]):
            
            if hito[j] == 1:
                
                if hito[xy[number][0]-1] != xy[number][1]:
                    flag = False
            number += 1
    if flag == True:
        print(sum(hito))
        exit()
        
print(0)
exit()

Solution (Python):
from itertools import combinations

n = int(input())
statements = []

for p in range(n):
    statement = []
    for s in range(int(input())):
        statement.append(list(map(int, input().split())))
    statements.append(statement)
    

def check_statements(honesty, statements):
    for h in range(len(honesty)):
        if honesty[h] == 1:
            for s in statements[h]:
                a, b = s
                if honesty[a-1] != b:
                    return False
    return True


def main():
    for h in range(n, 0, -1):
        for i in list(combinations(range(n), h)):
            p = [0 for _ in range(n)]
            for j in i:
                p[j] = 1
            if check_statements(p, statements):
                return h
    return 0

print(main())

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    aa = [[0] * n for _ in range(n)]
    for i in range(n):
        t = I()
        ta = [LI() for _ in range(t)]
        for x,y in ta:
            if y == 0:
                aa[i][x-1] = -1
            else:
                aa[i][x-1] = 1

    r = 0
    for i in range(2**n):
        f = [(i & 2**j) > 0 for j in range(n)]
        ok = True
        for j in range(n):
            if not f[j]:
                continue
            for k in range(n):
                if aa[j][k] == 0:
                    continue
                if aa[j][k] == 1:
                    if not f[k]:
                        ok = False
                else:
                    if f[k]:
                        ok = False
            if not ok:
                break

        if ok:
            t = len([_ for _ in f if _])
            if r < t:
                r =t

    return r


print(main())

Solution (Python):
import itertools
N = int(input())
item = []
for i in range(N):
    A = int(input())
    s = []
    for ii in range(A):
        x, y = map(int, input().split())
        s.append((x, y))
    item.append(s)

Ps = itertools.product([0, 1], repeat=N)
ans = 0
for P in Ps:
    right = True
    for i, p in enumerate(P):
        if p == 1:
            for x, y in item[i]:
                if (y == 1 and P[x - 1] == 0) or (y == 0 and P[x - 1] == 1):
                    right = False
    if right:
        ans = max(ans, sum(P))

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    said = [[]] * n
    for i in range(n):
        said[i] = [list(map(int, input().split())) for _ in range(int(input()))]

    ans = 0
    n_bit = '0' + str(n) + 'b'
    for i in range(2 ** n):
        i_bin = format(i, n_bit)
        i_bin_c = i_bin.count('1')
        if i_bin_c <= ans:
            continue

        isTrue = True
        for j in range(n):
            if i_bin[j] == '0':
                continue
            for k in said[j]:
                if int(i_bin[k[0]-1]) != k[1]:
                    isTrue = False
                    break
            if not isTrue:
                break
        if isTrue:
            ans = i_bin_c
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

N = int(raw_input())
A = []
B = []
for n in range(N):
    A_i = int(raw_input())
    honest_i = set()
    unkind_i = set()
    for i in range(A_i):
        x, y =  map(int, raw_input().split())
        if y == 0:
            unkind_i.add(x-1)
        else:
            honest_i.add(x-1)
    A.append(unkind_i)
    B.append(honest_i)

def check(cand, A, B):
    honest = {i for i,v in enumerate(cand) if v == 1}
    unkind = {i for i,v in enumerate(cand) if v == 0}
    for h in honest:
        if len(honest.intersection(A[h])) != 0:
            return False
        if len(unkind.intersection(B[h])) != 0:
            return False
    return True

best = 0
import itertools
for cand in itertools.product([0,1], repeat=N):
    if check(cand, A, B):
        count = cand.count(1)
        best = max(best, count)

print best

Solution (Python):
import bisect
import heapq
import math
from copy import copy
import sys
from queue import Queue, LifoQueue, PriorityQueue
from collections import defaultdict
from operator import itemgetter

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())

    d = defaultdict(list)
    for i in range(N):
        A = int(readline())
        for _ in range(A):
            x, y = map(int, readline().split())                
            d[i].append((x-1, y))
            
    ret = 0
    for i in range(2 ** N):
        contradiction = False
        for j in range(N):
            for x, y in d[j]:
                
                if (i >> j) & 1:
                    if (i >> x) & 1:
                        if y == 0:
                            contradiction = True
                            break
                    else:
                        if y == 1:
                            contradiction = True
                            break

        if contradiction:
            continue
        else:
            ret = max(bin(i).count("1"), ret)

    print(ret)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
data = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        data[i].append(list(map(int,input().split())))

ans = 0
for i in range(1<<n):
    use = []
    for bit in range(n):
        if i&(1<<bit):
            use.append(bit+1)

    judge = True
    for j in use:
        for x,y in data[j-1]:
            if x in use and y == 0:
                judge = False
                break
            if x not in use and y == 1:
                judge = False
                break

    if judge:
        ans = max(ans,len(use))

print(ans)

Solution (Python):
import itertools

N = int(input())
A = [0] * N
xy_list = [0] * N
for i in range(N):
    A[i] = int(input())
    xy = [0] * A[i]
    for j in range(A[i]):
        xy[j] = tuple(int(x) for x in input().split())
    xy_list[i] = xy

m = 0
for p in itertools.product([0, 1], repeat=N):
    for i in range(N):
        if p[i] == 0:
            continue
        for j in range(A[i]):
            x, y = xy_list[i][j]
            if p[x - 1] != y:
                break
        else:
            continue
        break
    else:
        s = sum(p)
        if s > m:
            m = s
print(m)

Solution (Python):
N = int(input())

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

result = 0
for i in range(1, 2 ** N):
    consistent = True
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        for x, y in evidences[j]:
            if (i >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print(result)

Solution (Python):
N = int(input())
g = [[-1]*N for i in range(N)] 

for i in range(N):
    A = int(input())
    for j in range(A):
        a,x = map(int, input().split())
        a -= 1
        g[i][a] = x
ans = 0
for i in range(1 << N):
    d=[0]*N
    for j in range(N):
        if (i>>j & 1):
            d[j] = 1
    ok = True
    for j in range(N):
        if d[j]: 
            for k in range(N):
                if g[j][k] == -1: continue
                if g[j][k] != d[k]: ok = False 
    if ok:
        ans = max(ans, bin(i).count("1"))
print(ans)

Solution (Python):
import itertools
import numpy as np
 
N = int(input())
info = []
for i in range(N):
    A = int(input())
    for _ in range(A):
        x,y = map(int,input().split())
        info.append((i,x-1,y))
A = np.array(list(itertools.product([0,1],repeat=N)), np.bool)
for i,x,y in info:
    bl = (~A[:,i]) | (A[:,x] == bool(y))
    A = A[bl]
    
answer = A.sum(axis = 1).max()
print(answer)

Solution (Python):
def checker(bbit,listN,N):
    i = 0
    j = 0
    ng = False
    
    
    
    while N > i :
        j=0
        checkFig = 3
        ibit = 1 << i
        while N > j :
            cbit = 1 << j
            if bbit & cbit == 0 :
                
                pass
            elif listN[j][i] == 3 :
                
                pass
            elif (listN[j][i] == 0) and (bbit & ibit != 0):
                ng = True
                break
            elif (listN[j][i] == 1) and (bbit & ibit == 0):
                ng = True
                break
            elif checkFig == 3 :
                
                checkFig = listN[j][i]
            elif checkFig != listN[j][i] :
                ng = True
                
                break
            j += 1
        if ng :
            
            break
        else :
            i +=1
    return (not ng)


def main():
    N = int(input())
    listA = [[3 for j in range(N)] for k in range(N)]
    n = 0
    while N > n :
        a = int(input())
        i = 0
        while a > i:
           x,y  = map(int,input().split())
           listA[n][x-1] = y
           i += 1
        n += 1
        
    honestBit = pow(2, N)-1
    honest = 0
    
    while honestBit > 0:
        ok = checker(honestBit,listA,N)
        if ok :
            okbit = honestBit
            oknum = 0
            while okbit > 0 :
                oknum += (okbit % 2) 
                okbit = okbit >> 1
            if oknum > honest :
                honest = oknum 
        honestBit -= 1
    print(honest)
    

main()

Solution (Python):
N = int(input())
A = [None]*N
x = [[None]*N for _ in range(N)]
y = [[None]*N for _ in range(N)]

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

ans =0
for num in range(2**N):
    
    flag = 1 
    
    
    for i in range(N):
        
        if (num>>i & 1)==1:
            
            
            for j in range(N):
                
                if x[i][j] != None and y[i][j]!=(num>>(x[i][j]-1) & 1):
                    flag = 0
                elif x[i][j] == None:
                    break
        if flag ==0:
            break
    if flag ==1:
        ans = max(ans,bin(num).count("1"))
print(ans)

Solution (Python):
N = int(input())
A = [None]*N
x = [[None]*N for _ in range(N)]
y = [[None]*N for _ in range(N)]

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

ans =0
for num in range(2**N):
    
    flag = 1 
    
    
    for i in range(N):
        
        if (num>>i & 1)==1:
            
            
            for j in range(N):
                
                if x[i][j] != None and y[i][j]!=(num>>(x[i][j]-1) & 1):
                    flag = 0
        if flag ==0:
            break
    if flag ==1:
        ans = max(ans,bin(num).count("1"))
print(ans)

Solution (Python):
N = int(input())
testimony = [[] for _ in range(N)]

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


def judge(bit: int) -> bool:
    for i in range(N):
        if not (bit & (1 << i)):
            continue

        for x, y in testimony[i]:
            if ((bit >> x) & 1) ^ y:
                return False

    return True


def main() -> None:
    res = 0
    for bit in range(1 << N):
        count = 0
        if judge(bit):
            for i in range(N):
                if bit & 1 << i:
                    count += 1
            res = max(res, count)

    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
numbers = list(map(int, input().split()))
n = numbers[0]

v = []

for i in range(n):
    numbers = list(map(int, input().split()))
    a = numbers[0]
    
    w = []
    
    for j in range(a):
        z = list(map(int, input().split()))
        w.append(z)
        
    v.append(w)
    
rezultat = 0

max_steps = 2 ** n

for i in range(max_steps):
    w = [-1] * n
    
    for j in range(n):
        if i >> j & 1:
            w[j] = 1
        else:
            w[j] = 0
    
    ok = 1
    
    for j in range(n):
        if ok == 0:
            break
        for a, b in v[j]:
            if w[j] == 1:
                a = a - 1
                if w[a] != b:
                    ok = 0
                    break
                
    if ok:
        rezultat = rezultat if rezultat > sum(w) else sum(w)
        
print(rezultat)

Solution (Python):
n = int(input())
g = [[] for i in range(n)]
for i in range(n):
    m = int(input())
    for j in range(m):
        g[i].append([int(x) for x in input().split()])
res = 0
for i in range(2 ** n):
    bit = i
    hypothesis = []
    for j in range(n):
        hypothesis.append(bit % 2)
        bit //= 2
    bit = i
    k = 0
    flag = True
    while bit > 0:
        if bit % 2 == 1:
            for s in g[k]:
                if hypothesis[s[0] - 1] != s[1]:
                    flag = False
        bit >>= 1
        k += 1
    if flag:
        if sum(hypothesis) > res:
            res = sum(hypothesis)
print(res)

Solution (Python):



def main():
    n = int(input())
    
    graph = [[-1 for _ in range(n)] for _ in range(n)]

    for i in range(n):
        ai = int(input())

        for _ in range(ai):
            xi, yi = map(int, input().split())
            
            xi -= 1
            graph[i][xi] = yi

    ans = 0

    
    
    
    
    
    

    
    

    
    
    for bit in range(1 << n):
        d = [0 for _ in range(n)]

        for j in range(n):
            
            
            if (bit >> j) & 1:
                d[j] = 1

        is_ok = True

        
        
        for j in range(n):
            if d[j] == 1:
                for k in range(n):
                    
                    if graph[j][k] == -1:
                        continue

                    
                    if graph[j][k] != d[k]:
                        is_ok = False

        
        if is_ok:
            ans = max(ans, sum(d))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    n = int(input())
    graph = [[-1 for _ in range(n)] for _ in range(n)]

    for i in range(n):
        ai = int(input())

        for _ in range(ai):
            xi, yi = map(int, input().split())
            xi -= 1
            graph[i][xi] = yi

    ans = 0

    
    for bit in range(1 << n):
        d = [0 for _ in range(n)]

        for j in range(n):
            if (bit >> j) & 1:
                d[j] = 1

        is_ok = True

        for j in range(n):
            if d[j] == 1:
                for k in range(n):
                    if graph[j][k] == -1:
                        continue

                    if graph[j][k] != d[k]:
                        is_ok = False

        if is_ok:
            ans = max(ans, sum(d))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
syougen={}
for i in range(n):
    a=int(input())
    syougen[i+1]=[[],[]]

    for j in range(a):
        x,y=map(int,input().split())
        if y==1:
            syougen[i+1][0].append(x)
        else:
            syougen[i+1][1].append(x)

result=0

for i in range(2**n):
    sei=set([])
    ayamari=set([])

    for j in range(n):
        if((i>>j)&1):
            sei=sei|(set(syougen[j+1][0]))|set([j+1])
            ayamari=ayamari|(set(syougen[j+1][1]))

    if sei.isdisjoint(ayamari):
        flag="true"
        cnt=0
        for j in range(n):
            if((i>>j)&1):
                cnt+=1
                if j+1 not in sei:
                    flag="fales"
                    
        if flag=="true" and cnt==len(sei):
            result=max(result,len(sei))
print(result)

Solution (Python):
import sys
import itertools
input = sys.stdin.readline

N = int(input())
A = [0]*N
evidences = []
for i in range(N):
    A[i] = int(input())
    e = [[int(i) for i in input().split()] for i in range(A[i])] 
    evidences.append(e)

combs = list(itertools.product(range(2), repeat=N))
table = [2]*N
maxtrue = 0


for comb in combs:
    c = list(comb)
    for i in range(N):
        if c[i] == 0:
            continue
        for evids in evidences[i]:
            if c[evids[0]-1] == evids[1]:
                continue
            else:
                break
        else:
            continue
        break
    else:
        
        if maxtrue < c.count(1):
            maxtrue = c.count(1)
print(maxtrue)

Solution (Python):
N = int(input())
syougen = [[] for _ in range(N)]
for _ in range(N):
    kosuu = int(input())
    for i in range(kosuu):
        syougen[_].append([int(x) for x in input().split(" ")])
num = 0
for i in range(2 ** N):
    bit = i
    hypothesis = []
    for _ in range(N):
        hypothesis.append(bit % 2)
        bit //= 2
    bit = i
    k = 0
    flag = True
    while bit > 0:
        if bit % 2 == 1:
            for s in syougen[k]:
                if hypothesis[s[0] - 1] != s[1]:
                    flag = False
        bit >>= 1
        k += 1
    if flag:
        if sum(hypothesis) > num:
            num = sum(hypothesis)
print(num)

Solution (Python):
n = int(input())
g = [[-1 for _ in range(n)] for _ in range(n)]

for i in range(n):
  a = int(input())
  for j in range(a):
    x,y = map(int, input().split())
    g[i][x-1] = y

ans = 0
for i in range(1 << n):
  d = [0] * n
  for j in range(n):
    if (i >> j & 1):
      d[j] = 1
  
  ok = True
  for j in range(n):
    if (d[j] == 1):
      for k in range(len(g[j])):
        if (g[j][k] == -1):
          continue
        elif (g[j][k] != d[k]):
          ok = False
  
  if (ok):
    ans = max(ans, sum(d))

print (ans)

Solution (Python):


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

ans = 0
for i in range(1 << N):
    d = list((i >> j) & 1 for j in range(N))
    ok = True
    for j in range(N):
        if d[j]:
            for k in range(N):
                if g[j][k] == -1:
                    continue
                if g[j][k] != d[k]:
                    ok = False
    if ok:
        ans = max(ans, sum(d))

print(ans)

Solution (Python):
N = int(input())

g = [[-1]*N for i in range(N)]

for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = [int(n) for n in input().split(' ')]
        g[i][x-1] = y

ans = 0
for i in range(1<<N):
    d = [0]*N
    for j in range(N):
        if i>>j&1:
            d[j]=1
    ok = True
    for j in range(N):
        if d[j]:
            for k in range(N):
                if g[j][k] == -1:
                    continue
                if g[j][k] != d[k]:
                    ok=False
    if ok:
        ans = max(ans, bin(i).count("1"))

print(ans)

Solution (Python):
n = int(input())
x_arr = [[] for i in range(n)]
y_arr = [[] for i in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    x,y = map(int,input().split())
    x_arr[i].append(x-1)
    y_arr[i].append(y)

ans = 0

for i in range(2**n):
  ok = 1
  count = 0
  for j in range(n):
    if not ((i >> j) & 1):
      continue
    else:
      count += 1
      for k in range(len(x_arr[j])):
        if y_arr[j][k] == 0 and ((i >> x_arr[j][k]) & 1):
          ok = 0
        if y_arr[j][k] == 1 and (not ((i >> x_arr[j][k]) & 1)):
          ok = 0
  if ok:
    ans = max(ans,count)
    
print(ans)

Solution (Python):
n = int(input())
xys = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    xys[i] = [list(map(int, input().split())) for _ in range(a)]

max_honest = 0
for i in range(2 ** n):
    bin_i = format(i, '015b')[::-1]
    ok = True

    for j in range(n):
        for x, y in xys[j]:
            if bin_i[j] == "1" and y != int(bin_i[x - 1]):
                ok = False
                break
        else:
            continue
        break

    if ok:
        honest = sum(int(x) for x in bin_i)
        max_honest = max(max_honest, honest)

print(max_honest)

Solution (Python):
import heapq as h
import math
import numpy as np
import copy
import itertools
import sys
 


n = int(input())
g = [[-1 for _ in range(n)] for _ in range(n)]

for i in range(n):
    a_cn = int(input())
    for j in range(a_cn):
        x,y = map(int, input().split())
        if y == 1:
            g[i][x-1] = 1
        elif y == 0:
            g[i][x-1] = 0


ans2 = 0
for i in range(2**n):
    cnt = 0
    bag = [0] * n 
    for j in range(n):
        if ((i >> j) & 1):
            bag[j] = 1
    ok = True
    for ix, v in enumerate(bag):
        if v == 1:
            for jx, jv in enumerate(g[ix]):
                if jv == 1:
                    if bag[jx] != 1:
                        ok = False
                elif jv == 0:
                    if bag[jx] != 0:
                        ok = False
    if ok == True:
        ans = sum(bag)
    else:
        ans = 0
    ans2 = max(ans2,ans)
print(ans2)

Solution (Python):
import sys
from itertools import islice
read = map(int, sys.stdin.read().split())

N = next(read)
candidates = [format(i, 'b').zfill(N) for i in range(2 ** N)]
A = [0] * N
xy = [[] for _ in range(N)]
for i in range(N):
    A[i] = next(read)
    xy[i].extend(list(islice(read, A[i] * 2)))

answer = 0

for candidate in candidates:
    tmp = 0
    truth = set()
    false = set()
    for k in range(N):
        if candidate[k] == '1':
            if k in false:
                break
            truth.add(k)
            for i, j in zip(*[iter(xy[k])] * 2):
                i -= 1
                if j == 1:
                    if i in false:
                        break
                    truth.add(i)
                else:
                    if i in truth:
                        break
                    false.add(i)
            else:
                continue
            break
        else:
            if k in truth:
                break
            false.add(k)
    else:
        if len(truth) > answer:
            answer = len(truth)

print(answer)

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

for i in range(2**N):
  f=1
  h=[]
  u=[]
  for j in range(N):
    if (i>>j)&1:
      h.append(j)
    else:
      u.append(j)
  for k in h:
    for l in I[k]:
      if l[1]==1 and l[0] in u:
        f=0
        break
      elif l[1]==0 and l[0] in h:
        f=0
        break
  if f==1:
    a=max(a,len(h))
print(a)