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):
def int_to_list(bit, n):
    l = []
    for i in range(n):
     if bit & (1 << i):
         l.append(i)
    return l

def solve():
    N = int(input())
    
    l = [[] for _ in range(N)]
    for i in range(N):
        for _ in range(int(input())):
            p, q = map(int, input().split())
            l[i].append((p-1, q))

    ans = 0
    for i in range(1 << N):
        partial = int_to_list(i, N)

        f = True
        for j in range(N):
            if j not in partial: continue
            for p, q in l[j]:
                if q == 0 and p in partial:
                    f = False
                if q == 1 and not p in partial:
                    f = False
        if f:
            ans = max(ans, len(partial))
            
    return ans

print(solve())

Solution (Python):
n = int(input())
witness = [[] for _ in range(n)]
for i in range(n):
    ai = int(input())
    for _ in range(ai):
        x, y = map(int, input().split())
        witness[i].append((x - 1, y))
ans = 0
for i in range(2 ** n):
    f = [False] * n
    flag = False
    for j in range(n):
        if i >> j & 1:
            f[j] = True
    for j in range(n):
        if f[j]:
            for x, y in witness[j]:
                if f[x] and y == 0 or not f[x] and y == 1:
                    flag = True
                    break

        if flag:
            break
        if j == n - 1:
            ans = max(ans, f.count(True))
print(ans)

Solution (Python):
import re
n=int(input())
A=[]
for i in range(n):
    B=["."]*n
    for j in range(int(input())):
        x,y=map(int,input().split())
        B[x-1]=str(y)
    A.append("".join(B))

ans=0
for i in range(2**n):
    num=format(i, "b").zfill(n)
    flag,cnt=1,0
    for j,k in enumerate(num):
        result=re.fullmatch(r"".join(A[j]),num)
        if result is not None and k=="1":
            cnt +=1
        elif (result is not None and k=="0") or (result is None and k=="1"):
            flag=0
            break
    if flag:ans=max(ans,cnt)
print(ans)

Solution (Python):
n=int(input())
mark=dict()
for i in range(n):
    A=int(input())
    temp_list=[tuple(map(int,input().split())) for i in range(A)]
    mark[i+1]=temp_list




ans=0
for i in range(2**n):
    honest_remark=[]
    mujun=[]
    cnt=0
    for j in range(n):
        
        if (i>>j)&1:
            cnt+=1
            for k in mark[j+1]:
                honest_remark.append(k)
            mujun.append((j+1,0))
        else:
            mujun.append((j+1,1))

    
    
    honest_remark=set(honest_remark)
    mujun=set(mujun)
    temp=honest_remark&mujun
    if len(temp)==0:
        ans=max(ans,cnt)

print(ans)

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

ans = 0
for p in range(1<<N):
    h = []
    judge = True
    for i in range(N):
        h.append(p&1)
        p>>=1
    for i in range(N):
        for x, y in xy[i]:
            if h[i] and y != h[x]:
                judge = False
                break
        if not judge: break
    if not judge: continue
    ans = max(ans,sum(h))

print(ans)

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


ans = 0
for i in range(2**n):
    temp = 0
    for j in range(n):
        if (i >> j) & 1:
            temp += 1
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            for k in range(n):
                
                if  L[j][k] == 1 and ((i >> k) & 1) == 0:
                    flag =  False
                elif L[j][k] == 0 and ((i >> k) & 1) != 0:
                    flag = False
                else:
                    pass
    if flag:
        ans = max(ans, temp)
print(ans)

Solution (Python):
from itertools import combinations
n = int(input())
a = []
xy = [] 
for i in range(n):
    a.append(int(input()))
    xy.append([])
    for _ in range(a[i]):
        xy[i].append([int(i) for i in input().split()])
ans = 0
for i in range(n + 1): 
    b = list(combinations(list(range(n)), i))
    for j in range(len(b)): 
        flag = False
        
        for k in b[j]: 
            for l in range(a[k]): 
                if (xy[k][l][0] - 1 in b[j] and xy[k][l][1] != 1) or ((not xy[k][l][0] - 1 in b[j]) and xy[k][l][1] == 1):
                    flag = True
                    break
                
            if flag:
                break
        if not flag:
            
            ans = i
print(ans)

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

ans = 0
for i in range(2**N):
    
    state = [0] * N
    for j in range(N):
        state[j] = (i >> j) & 1
    
    
    flag = True
    for j in range(N):
        if state[j] == 0:
            continue
        for x,y in edge[j]:
            if state[x] == y:
                continue
            flag = False
            break
        if not flag:
            break
    if not flag:
        continue

    ans = max(ans, state.count(1))

print(ans)

Solution (Python):
from itertools import product
N = int(input())
said = [[-1] * (N+1) for _ in range(N+1)]

for a in range(N):
    K = int(input())
    for _ in range(K):
        x, y = map(int, input().split())
        said[a][x - 1] = y

ans = 0
for cand in product(range(2), repeat=N):
    isOK = True

    for i, c in enumerate(cand):
        if not c:
            continue
        A = said[i]
        for j in range(N):
            if i == j or A[j] == -1:
                continue
            if cand[j] != A[j]:
                isOK = False
                break

    if isOK:
        ans = max(ans, sum(cand))

print(ans)

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

ans=0
for c in range(2**n):
    b=bin(c)[2:]
    B=[0]*n
    for i in range(len(b)):
        B[-i-1]=int(b[-i-1])
    a=0
    for i in range(n):
        if B[i]==1:
            for j in range(n):
                if B[j]+Y[i][j]==1:
                    a=1
                    break
        if a>0:
            break
    if a==0:
        ans=max(ans,sum(B))
print(ans)

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

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

MAX = 0
for i in range(2 ** n):
    for index, t in enumerate(testimonies):
        if (i >> index) & 1:
            contradict = False
            for x, y in t:
                if (i >> (x - 1)) % 2 == y:
                    continue
                else:
                    contradict = True
                    break
            if contradict:
                break
    else:
        honest = 0
        while i:
            i = i & (i - 1)
            honest += 1
        MAX = max(MAX, honest)
print(MAX)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

N = int(input())
evid = [[] for _ in range(N)]

for i in range(N):
  a = int(input())
  for _ in range(a):
    x, y = map(int, input().split())
    evid[i].append((x-1,y))
    
ans = 0
for bit in range(1<<N):
  cnt = 0
  ok = True
  for i in range(N):
    if not bit>>i & 1:
      continue
    for x, y in evid[i]:
      if y==1 and not bit>>x & 1:
        ok = False
        break
      if y==0 and  bit>>x & 1:
        ok = False
        break
    if ok:
      cnt += 1
    else:
      break
  else:
    ans = max(ans, cnt)
print(ans)

Solution (Python):
import re
n=int(input())
A=[]
for i in range(n):
    word=["."]*n
    for j in range(int(input())):
        x,y=map(int,input().split())
        word[x-1]=str(y)
    A.append(word)

ans=0
for i in range(2**n):
    num=format(i, "b").zfill(n)
    flag,cnt=1,0
    for j,k in enumerate(num):
        search=re.search(r"".join(A[j]),num)
        if search!=None and k=="1":
            cnt +=1
        elif (search==None and k=="1") or (search!=None and k=="0"):
            flag=0
            break
    if flag:ans=max(ans,cnt)
print(ans)

Solution (Python):
import re
n=int(input())
A=[]
for i in range(n):
    B=["."]*n
    for x,y in [list(map(int,input().split())) for k in range(int(input()))]:
        B[x-1]=str(y)
    A.append("".join(B))

ans=0
for i in range(2**n):
    num=format(i,"b").zfill(n)
    cnt,flag=0,1
    for k,j in enumerate(num):
        result=re.search(r"".join(A[k]),num)
        if result!=None and j=="1":
            cnt +=1
        elif (result!=None and j=="0") or (result==None and j=="1"):
            flag=0
            break
    if flag:ans=max(ans,cnt)
print(ans)

Solution (Python):
import re
n=int(input())
A=[]
for i in range(n):
    B=["."]*n
    for x,y in [list(map(int,input().split())) for k in range(int(input()))]:
        B[x-1]=str(y)
    A.append("".join(B))
ans=0
for i in range(2**n):
    num=format(i,"b").zfill(n)
    cnt,flag=0,1
    for k,j in enumerate(num):
        result=re.search(r"".join(A[k]),num)
        if result is not None and j=="1":
            cnt +=1
        elif (result is not None and j=="0") or (result is None and j=="1"):
            flag=0
            break
    if flag:ans=max(ans,cnt)
print(ans)

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

def count_honest(bits):
    honest = [(bits >> i) & 1 for i in range(n)]
    for i in range(n):
        if not honest[i]:
            continue
        for k, v in d[i].items():
            if honest[k] != v:
                return 0
    return sum(honest)


print(max([count_honest(i) for i in range(2**n)]))

Solution (Python):
n = int(input())
ms = []
say = []
for i in range(n):
    m = int(input())
    ms.append(m)
    say.append([])
    for j in range(m):
        p,q = list(map(int, input().split()))
        say[i].append([p,q])




def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

ans = 0
for i in range(2**n):
    flag = 1
    nowbit = bitlist(i,n)
    for j in range(n):
        for k in range(ms[j]):
            if nowbit[j]==1:
                if say[j][k][1] != nowbit[say[j][k][0]-1]:
                    flag = 0
    if flag == 1:
        ans = max(ans, sum(nowbit))

print(ans)

Solution (Python):
n = int(input())
ms = []
say = []
for i in range(n):
    m = int(input())
    ms.append(m)
    say.append([])
    for j in range(m):
        p,q = list(map(int, input().split()))
        say[i].append([p,q])




def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

ans = 0
for i in range(2**n):
    flag = 1
    nowbit = bitlist(i,n)
    for j in range(n):
        for k in range(ms[j]):
            if nowbit[j]==1:
                if say[j][k][1] != nowbit[say[j][k][0]-1]:
                    flag = 0
    if flag == 1:
        ans = max(ans, sum(nowbit))

print(ans)

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

A_ary = []
for _ in range(N):
  A = int(input())
  ans_ary = []
  for _ in range(A):
    x, y = map(int, input().split())
    ans_ary.append([x, y])
  A_ary.append(ans_ary)

counts = []
for n in range(2 ** N):
  
  contExists = False
  for i, a in enumerate(A_ary):
    if not((n >> i) & 1):
      continue
    for xy in a:
      shift_num = xy[0] - 1
      if (((n >> shift_num) & 1) != xy[1]):
        contExists = True
        break

    if (contExists == True):
      break
  
  if (contExists == True):
    continue
  else:
    counts.append(bin(n).count("1"))

print(max(counts))

Solution (Python):
n = int(input())
lst = []

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

def check(mask,lst):
    cnt = 0
    for i in range(n):
        if mask & (1<<i):
            cnt += 1
            for (p,TF) in lst[i]:
                if mask&(1<<p) != TF<<p:
                    return 0
    return cnt
    
ans = 0
for mask in range(1<<n):
    c = check(mask,lst)
    ans = max(ans,c)    
print(ans)

Solution (Python):
import itertools

n=int(input())
a=[[] for i in range(n)]


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


ls=tuple(range(1,n+1))
res=0
for i in range(1,n+1):
    for s in list(itertools.combinations(ls,i)):
        c=list(s)
        my_bool=True
        for j in c:
            for k in range(len(a[j-1])):
                if a[j-1][k][1]==0:
                    if a[j-1][k][0] in c:
                        my_bool=False
                        break
                else:
                    if not a[j-1][k][0] in c:
                        my_bool=False
                        break
            if not my_bool:
                break
        if my_bool:
            
            res=max(res,len(c))
print(res)

Solution (Python):




def main():
    N = int(input())
    XY = [[] for _ in range(N)]
    for i in range(N):
        A = int(input())
        XY[i] = [list(map(int, input().split())) for _ in range(A)]

    max_H = 0
    for i in range(2**N):
        bin = format(i, '015b')[::-1]
        ok = True

        for j in range(N):
            for x, y in XY[j]:
                if bin[j] == '1' and y != int(bin[x - 1]):
                    ok = False
                    break
                else:
                    continue
                break
        if ok:
            H = sum(int(x) for x in bin)
            max_H = max(max_H, H)
    print(max_H)


if __name__ == "__main__":
    main()

Solution (Python):



def put(a, k, v):
    if k in a:
        if a[k] != v:
            return False
    else:
        a[k] = v
    return True


def check(n, t, i):
    a = {}
    m = 0
    for j in range(n):
        honest = i >> j & 1
        m += honest
        if not put(a, j+1, honest):
            return 0
        if honest:
            for (k, h) in t[j+1].items():
                if not put(a, k, h if honest else 1 - h):
                    return 0
    return m


def solve(n, t):
    print(max([check(n, t, i) for i in range(1 << n)]))


def main():
    t = {}
    n = int(input())
    for i in range(n):
        a = int(input())
        t[i+1] = {}
        for j in (range(a)):
            x, y = map(int, input().split())
            t[i+1][x] = y
    solve(n, t)


if __name__ == '__main__':
    main()

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

honest = []
for i in range(n):
    a = int(input())
    honest.append({})
    for j in range(a):
        x,y = map(int, input().split())
        honest[i][x-1] = y
ans = 0
for i in range(1<<n):
    tmp = 0
    hon = 0
    for j in range(n):
        if 1<<j & i == 0:
            continue
        for k,v in honest[j].items():
            if (1<<k & i) != v<<k:
                break
        else:
            tmp += 1
            hon |= 1<<j
    if hon == i and tmp > ans:
        
        ans = tmp
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n=ii()
a=[]
x=[]
y=[]

for i in range(n):
    a0=ii()
    a.append(a0)
    xtemp=[]
    ytemp=[]
    for j in range(a0):
        x0,y0=mii()
        x0-=1
        xtemp.append(x0)
        ytemp.append(y0)
    x.append(xtemp)
    y.append(ytemp)

ans=0
for i in product([0,1], repeat=n):
    arr=list(deepcopy(i))


    
    temp=0
    for j in range(n):
        
        if i[j]==1:
            for k in range(a[j]):
                if i[x[j][k]]!=y[j][k]:
                    temp=1

    if temp==0:
        ans=max(ans,sum(arr))
    
print(ans)

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

testimony_list = [[] for _ in range(N)]
for i in range(N):
    Ai = int(input())
    for j in range(Ai):
        x, y = map(int, input().split(' '))
        testimony_list[i].append((x, y))

def judge(bit):
    for i in range(N):
        if not (bit & (1<<i)):
            continue
        for x, y in testimony_list[i]:
            if y == 1 and not (bit & (1<<(x-1))):
                return False
            if y == 0 and (bit & 1<<(x-1)):
                return False
    return True

max_num = 0
for bit in range(1<<N):
    res = judge(bit)
    if res == True:
        num = 0
        for i in bin(bit)[2:][::-1]:
            if int(i) == 1:
                num += 1
        max_num = max(max_num, num)
print(max_num)

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

testimony_list = [[] for _ in range(N)]
for i in range(N):
    Ai = int(input())
    for j in range(Ai):
        x, y = map(int, input().split(' '))
        testimony_list[i].append((x, y))

def judge(bit):
    for i in range(N):
        if not (bit & (1<<i)):
            continue
        for x, y in testimony_list[i]:
            if y == 1 and not (bit & (1<<(x-1))):
                return False
            if y == 0 and (bit & 1<<(x-1)):
                return False
    return True

max_num = 0
for bit in range(1<<N):
    res = judge(bit)
    if res == True:
        num = 0
        for i in bin(bit)[2:][::-1]:
            if int(i) == 1:
                num += 1
        max_num = max(max_num, num)
print(max_num)

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

ans = 0
for i in range(2**N):
    real = []
    flg = True
    for j in range(N):
        if ((i >> j) & 1):
             real.append(j)
    for hito in real:
        for x, y in syougen[hito]:
            if (y == 0 and x in real) or (y == 1 and x not in real):
                flg = False
                break
    if flg:
        ans = max(ans, len(real))
print(ans)

Solution (Python):
n = int(input())
say = []
a = []
ans = 0
for i in range(n):
    ai = int(input())
    a.append(ai)
    say.append([])
    for j in range(ai):
        xi, yi = map(int, input().split())
        say[i].append((xi, yi))
for i in range(2**n):
    trueman = []
    mujun = False
    for j in map(int, list("0"*(n - len(bin(i)[2:])) + bin(i)[2:])):
        trueman.append(j)
    for j in range(n):
        if trueman[j] == True:
            for k in range(a[j]):
                if say[j][k][1] == 1:
                    if trueman[say[j][k][0]-1] == 0:
                        mujun = True
                if say[j][k][1] == 0:
                    if trueman[say[j][k][0]-1] == 1:
                        mujun = True
    if not mujun:
        ans = max(ans, sum(trueman))
print(ans)

Solution (Python):
n=int(input())
L=[]
ans=0
for i in range(n):
   a=int(input())
   D=[]
   for j in range(a):
      x,y=map(int,input().split())
      D.append((x,y))
   L.append(D)
for i in range(2**n):
   B=[0]*n
   for j in range(n):
      if i>>j&1:
         B[j]=1
   if sum(B)!=0:
      flag=True
      for k in range(n):
         if B[k]==1:
            for m in range(len(L[k])):
               if B[L[k][m][0]-1]!=L[k][m][1]:
                  flag=False
      if flag==True:
         ans=max(ans,sum(B))
print(ans)

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

























def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007


def main():
	N = inputInt()
	A = []
	for i in range(N):
		tmp = inputInt()
		tmpSet = []
		for j in range(tmp):
			x,y = inputMap()
			tmpSet.append((x,y))
		A.append(tmpSet)

	ans = 0
	for i in range(1,2**N):
		cnts = -1
		ii = i
		syouziki = []
		flg = True
		for j in range(1,N+1):
			target = ii % 2
			ii = ii // 2
			cnts += 1
			if target == 1:
				syouziki.append(cnts)

		for j in syouziki:
			for k in A[j]:
				x,y = k
				x = x-1
				if y == 1:
					if x in syouziki:
						pass
					else:
						flg = False
						break
				else:
					if x in syouziki:
						flg = False
						break
					else:
						pass
			if flg == False:
				break
		if flg == True:
			tmp = len(syouziki)
			if tmp > ans:
				ans = tmp

	print(ans)










def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

Solution (Python):
def judge(bit):
    for i in range(N):
        if not (bit & (1<<i)):
            continue

        for xy in v[i]:
            x = xy[0]
            y = xy[1]

            if y==1 and not(bit & (1<<x)):
                return False

            if y==0 and (bit & (1<<x)):
                return False
    return True

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

res = 0
for bit in range(1<<N):
    if judge(bit):
        conut = 0
        for i in range(N):
            if bit & (1<<i):
                conut += 1
        res = max(res, conut)
print(res)

Solution (Python):








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

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

        table.append(ary)

    def check(bit):
        for i in range(N):
            if (bit & (1 << i)) == 0:
                continue
            for x, y in table[i]:
                if y == 1 and bit & (1 << x) == 0:
                    return False
                if y == 0 and bit & (1 << x) != 0:
                    return False
        return True

    def search(i, bit):
        if i == N:
            if not check(bit):
                return 0
            return sum(1 for i in range(N) if (bit & (1 << i)) != 0)

        count1 = search(i + 1, bit)
        count2 = search(i + 1, bit | (1 << i))
        return max(count1, count2)

    count = search(0, 0)
    print(count)


main()

Solution (Python):


n=int(input())
xy=[[] for i in range(n)]

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

bit=[]
ans=0
def bit_search(bit):
    global ans
    if len(bit)==n:
        for i in range(n):
            jugh=bit[i]
            if jugh==1:
                for j in xy[i]:
                    x,y=j
                    if bit[x-1]==0:
                        if y==1:
                            return 
                    else:
                        if y==0:
                            return 
        ans=max(ans,sum(bit))
    else:
       
        bit_search(bit+[0])
        bit_search(bit+[1])
bit_search(bit)
print(ans)

Solution (Python):
from itertools import product

n = int(input())
x = []
y = []
for i in range(n):
    xx = []
    yy = []
    for i in range(int(input())):
        arr = [int(i) for i in input().split()]
        xx.append(arr[0])
        yy.append(arr[1])
    x.append(xx)
    y.append(yy)

max_honest = 0
for honest in product([0,1], repeat=n):
    if sum(honest) < max_honest:
        continue
    for i, h in enumerate(honest):
        if h:
            for xx, yy in zip(x[i], y[i]):
                if honest[xx-1] != yy:
                    break
            else:
                continue
            break
    else:
        max_honest = sum(honest)

print(max_honest)

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

def func(x):
  res = []
  for i in range(n):
    res.append(x%2)
    x //= 2
  return res

test = {}
for i in range(n):
  A = int(input())
  test[i+1] = []
  for a in range(A):
    x,y = map(int,input().split())
    test[i+1].append((x,y))

ans = 0
for i in range(2**n):
  people = func(i)
  for i in range(n):
    if people[i]:
      for x,y in test[i+1]:
        if people[x-1] == y:
          continue
        else:
          break
      else:
        continue
      break
  else:
    ans = max(sum(people),ans)
print(ans)

Solution (Python):







def iter_p_adic(p, length):
    '''
    連続して増加するp進数をリストとして返す。lengthはリストの長さ
    return
    ----------
    所望のp進数リストを次々返してくれるiterator
    '''
    from itertools import product
    tmp = [range(p)] * length
    return product(*tmp)


import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


N = read_a_int()
objection = []
for _ in range(N):
    a = read_a_int()
    hatugenn = read_tuple(a)
    objection.append(hatugenn)


def is_ok(katei):
    
    syoujiki = set()  
    for i, k in enumerate(katei):
        if k == 1:
            syoujiki.add(i)
    for s in syoujiki:
        
        for x, y in objection[s]:
            x -= 1  
            if y == 0:
                if x in syoujiki:
                    return False  
            else:
                if x not in syoujiki:
                    return False  
    return True


ans = 0
for katei in iter_p_adic(2, N):
    
    if is_ok(katei):
        ans = max(ans, sum(katei))
print(ans)

Solution (Python):
def count(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n >>= 1
    return cnt


N = int(input())

shogen = [[] for _ in range(N)]

for i in range(N):
    a = int(input())
    for _ in range(a):
        shogen[i].append(list(map(int, input().split())))
ans = 0
for i in range(1 << N):
    ok = True
    for j in range(N):
        if not (i & (1 << j)):
            continue
        for s in shogen[j]:
            if ((i >> (s[0] - 1)) & 1) ^ s[1]:
                ok = False
    if ok:
        ans = max(ans, count(i))
print(ans)

Solution (Python):
def count(n):
    if n == 0:
        return 0
    return count(n >> 1) + (n & 1)


N = int(input())

shogen = [[] for _ in range(N)]

for i in range(N):
    a = int(input())
    for _ in range(a):
        shogen[i].append(list(map(int, input().split())))
ans = 0
for i in range(1 << N):
    ok = True
    for j in range(N):
        if not (i & (1 << j)):
            continue
        for s in shogen[j]:
            if ((i >> (s[0] - 1)) & 1) ^ s[1]:
                ok = False
    if ok:
        ans = max(ans, count(i))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
def inputS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines  

N  = int(input())
XY = [[] for _ in range(N)] 

for i in range(N):
  A = int(input())
  for _ in range(A):
    ind, bl = map(int, input().split())
    XY[i].append((ind-1, bl))

ans = 0
for bit in range(1<<N):
  cnt = 0
  ok = True
  for i in range(N):
    
    if not bit >> i & 1:
      continue
    
    for x, y in XY[i]:
      
      
      if bit >> x & 1 ^ y:
        ok = False
        break
    if ok:
      cnt += 1
    else:
      break
  else:
    ans = max(ans, cnt)
print(ans)