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:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=[[] for i in range(n)]
for i in range(n):
    a=I()
    for j in range(a):
        lis[i].append(LI())
#print(lis)
ans=[]
for x in product([0,1],repeat=n):
    count=0
    flag=True
    for j in range(n):
        if x[j]==1:
            count+=1
            for k in range(len(lis[j])):
                if x[lis[j][k][0]-1]!=lis[j][k][1]:
                    flag=False
    if flag==True:
        ans.append(count)
print(max(ans))

Submission status: Accepted

Solution code:
n = int(input())

g = [[] 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
        g[i].append((x, y))

ans = 0
for i in range(2**n):
    temp = [-1]*n
    for j in range(n):
        if (i >> j) & 1:
            temp[j] = 1
        else:
            temp[j] = 0
    flag = True
    for j in range(n):
        if temp[j] == 1:
            for x, y in g[j]:
                if temp[x] != y:
                    flag = False
    if flag:
        ans = max(ans, sum(temp))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect

sys.setrecursionlimit(10**6)
def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]

N = z()
A = [0]*N
X = {}
Y = {}
for i in range(N):
    A[i] = z()
    X[i] = [0]*A[i]
    Y[i] = [0]*A[i]
    for j in range(A[i]):
        x, y = zz()
        X[i][j] = x-1
        Y[i][j] = y
ans = 0
for bits in itertools.product([0, 1], repeat=N):
    # print("================")
    # print(bits)
    false_flg = False
    for i, b in enumerate(bits):
        if (b == 1):
            # print('i=', i)
            for x, y in zip(X[i], Y[i]):
                # print(x, y)
                if (bits[x] != y):
                    # print(False)
                    false_flg = True
                if false_flg:
                    break
            if false_flg:
                break
    if false_flg:
        continue
    else:
        ans = max(ans, sum(bits))
print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())

H = []
for n in range(N):
    A = int(input())
    tmp = []
    for a in range(A):
        tmp.append(list(map(int, input().split())))
    H.append(tmp)
ans = 0 
for pro in itertools.product([0, 1], repeat=N):
    flag = 0
    for p in range(len(pro)):
        if pro[p] != 0:
            for h in H[p]:
                if pro[h[0]-1] != h[1]:
                    flag = 1
                    break
        if flag == 1:
            break
        if p == len(pro) - 1:
            ans = max(ans, sum(pro))

print(ans)

Submission status: Accepted

Solution code:
def II(): return int(input())
def MI(): return map(int, input().split())
N=II()
a=[0]*N
x=[[0]*N for i in range(N)]
y=[[0]*N for i in range(N)]
for i in range(N):
  a[i]=II()
  for j in range(a[i]):
    x[i][j],y[i][j]=MI()
    x[i][j]-=1
def check(honest):
  for i in range(N):
    if not honest[i]:
      continue
    for j in range(a[i]):
      if y[i][j]==0 and honest[x[i][j]]:
        return False
      if y[i][j]==1 and not honest[x[i][j]]:
        return False
  return True
def dfs(honest):
  if len(honest)==N:
    if check(honest):
      return sum(honest)
    else:
      return 0
  return max(dfs(honest+[True]),dfs(honest+[False]))
print(dfs([]))

Submission status: Accepted

Solution code:
def II(): return int(input())
def MI(): return map(int, input().split())
N=II()
shogens=[]
for i in range(N):
  a=II()
  shogens.append([])
  for j in range(a):
    x,y=MI()
    x-=1
    shogens[-1].append((x,y))
def is_honest(i,j):
  return (i>>j)%2==1
def honest_cnt(i):
  ans=0
  for j in range(N):
    ans+=is_honest(i,j)
  return ans
ans=0
for i in range(1<<N):
  ok=True
  for j in range(N):
    if not is_honest(i,j):
      continue
    for (x,y) in shogens[j]:
      if y==0 and is_honest(i,x):
        ok=False
      if y==1 and not is_honest(i,x):
        ok=False  
  if ok:
    ans=max(ans,honest_cnt(i))
print(ans)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
xys=[]
for i in range(N):
    A = int(input())
    xy = []
    for i in range(A):
        xy.append(list(map(int,input().split())))
    xys.append(xy)
#print('xys:', xys)  ############


#正直者1,  不親切0
a = [0,1]
Ls = list(itertools.product(a, repeat=N))
#print('Ls:', Ls)  ###########

mujun=[0]*(N+1)
count=0
ans=0
for L in Ls:
    #print('L:        ', L)  ###########
    flag=0
    hito=1
    #count=0
    count=sum(list(L))
    mujun=[0] + list(L)
    for i in L:
        #print('i:', i)    ###########
        if i==1:
            for xy in xys[hito-1]:
                #print('xy:', xy)  #########
                if xy[1] == 1:
                    if mujun[xy[0]]==0:
                        count=0
                        #print('mujuuuuuunnnnnnn!')
                        flag=1
                        break
                    #else:
                        #count+=1
                        #mujun[xy[0]]=1
                else:
                    if mujun[xy[0]]==1:
                        count=0
                        #print('mujuuuuuuuuuuuuuuuuuuuun!')   ###########
                        flag=1
                        break
                    #else:
                        #mujun[xy[0]]=-1


                #print('count:', count)  ###########
                #print('mujun:', mujun)  ###########
        hito+=1
    if flag==0:
        ans=max(ans,count)
    #print('ans:', ans)  ###########

#print('ans:', ans) ###########
print(ans)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
lis_hl = list(itertools.product('01',repeat = N))
#1正直者 　0不親切
A = []
X = []
for i in range(N):
    A.append(int(input()))
    Y =[]
    for j in range(A[-1]):
        Y.append(list(map(int,input().split())))
    X.append(Y)
honesty = 0
for hl in lis_hl:#honesty laier list
    flag = 0
    for i in range(N):#人について探査
        if flag == 0:
            is_hl = hl[i]# これから証言するひとは正直者か
            if is_hl == '1':
                
                for xi in X[i]:#証言を全探索
                    if xi[1] != int(hl[xi[0]-1]):
                        flag = 1
                        break
    if flag == 0:
        honesty = max(honesty,hl.count('1'))
print(honesty)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()
    A = []
    for _ in range(N):
        ni = I()
        A.append(LIR(ni))

    ans = 0
    for bit in range(1 << N):
        pattern = [bit >> i & 1 for i in range(N)]
        for (i, Ai) in enumerate(A):
            if not pattern[i]:
                continue
            # iが正直者の時
            for (x, y) in Ai:
                target = pattern[x-1]
                if target != y:
                    break
            else:
                continue
            break
        else:
            ans = max(ans, pattern.count(1))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#create date: 2020-06-30 22:48

import sys
stdin = sys.stdin
from itertools import product

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    t = [[-1] * n for _ in range(n)]
    for j in range(n):
        a = ni()
        for i in range(a):
            x, y = na()
            t[j][x-1] = y
    l = list(product([0, 1], repeat=n))
    ans = 0
    #print(t)
    for li in l:
        f = True
        for i in range(n):
            people = li[i]
            if people:
                for j in range(n):
                    if t[i][j] == 1 and li[j] == 0:
                        f = False
                    if t[i][j] == 0 and li[j] == 1:
                        f = False
        if f:
            #print(li, f)
            ans = max(ans, sum(li))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
N=int(input())
A=[]
for i in range(N):
  a=[]
  B=int(input())
  for _ in range(B):
    x,y=map(int,input().split())
    a.append([x,y])
  A.append(a)
ans=0
for i in list(itertools.product(range(2),repeat=N)):
  for j in range(len(A)):
    flag=True
    if i[j]==0:
      continue
    for x,y in A[j]:
      if i[x-1]!=y:
        flag=False
        break
    if not flag:
      break
  if flag:
    ans=max(ans,sum(i))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xy=[[] 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-=1
    xy[i].append((x,y))
ans=0
for i in range(1<<n):
  cnt=bin(i).count("1")
  if cnt<=ans:continue
  for j in range(n):
    if i&(1<<j):
      for x,y in xy[j]:
        if y==1 and i&(1<<x):continue
        if y==0 and i&(1<<x)==0:continue
        break
      else:
        continue
      break
  else:
    ans=cnt
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []

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

ans = 0

for i in range(2**n):
    ans_t = 0
    id_list =list(bin(i))[2:]
    id_list = [int(x) for x in id_list]
    while len(id_list) != n:
        id_list.insert(0,0)
    for j in range(n):
        flag = 0
        if id_list[j] == 0:
            continue
        else:
            for k in range(a[j][0]):
                if id_list[a[j][1][k][0]-1] != a[j][1][k][1]:
                    flag = 1
                    break
        if flag == 1:
            ans_t = 0
            break
        else:
            ans_t += 1
    if ans_t > ans:
        ans = ans_t

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
B=[]
for i in range (N):
    a=int(input())
    b=[]
    for j in range(a):
        x,y=map(int,input().split())
        b.append([x,y])
    B.append(b)
ans=0
for k in range(2**N):
    num=0
    L=[0]*N
    p=0
    for j in range(N):
        if ((k>>j)&1):
            L[N-1-j]=1
            num+=1
    for k in range(N):
        if L[k]==1:
            for m in range(len(B[k])):
                if L[B[k][m][0]-1]!=B[k][m][1]:
                    p=1
    if p==0:
        ans=max(ans,num)

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    B = [[] for _ in range(N)]
    for i in range(N):
        k = int(readline())
        for _ in range(k):
            x, y = map(int, readline().split())
            B[i].append((x - 1, y))

    ans = 0
    for bit in range(1 << N):
        ok = True
        for i in range(N):
            if not (bit & (1 << i)):
                continue
            for x, y in B[i]:
                if bool(bit & (1 << x)) != bool(y):
                    ok = False
                    break
            if not ok:
                break

        if ok:
            ans = max(ans, str(bin(bit)).count('1'))

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
evidence = [[] for _ in range(N)]
for i in range(N):
  A = int(input())
  for _ in range(A):
    x,y = map(int,input().split())
    evidence[i].append((x-1,y))
result = 0
for j in range(1,2**N):
  consistent = True
  for k in range(N):
    if (j >> k) & 1 == 0:
      continue
    for x,y in evidence[k]:
      if (j >> x) & 1 != y:
        consistent = False
        break
    if not consistent:
      break
  if consistent:
    result = max(result, bin(j)[2:].count("1"))
print(result)

Submission status: Accepted

Solution code:
n = int(input())

a_list = []
for _ in range(n):
  mini_list = []
  a = int(input())
  for _ in range(a):
    mini_list.append(list(map(int, input().split())))
  a_list.append(mini_list)

ans = 0
for i in range(2**n):
  ans_list = [0]*n
  cnt=0
  while i!=0:
    ans_list[cnt] = i%2
    cnt+=1
    i//=2
  
  flg = True
  for j, syogens in enumerate(a_list):
    if ans_list[j]==0:
      pass
    else:
      for syogen in syogens:
        person = syogen[0]-1
        status = syogen[1]
        if ans_list[person] != status:
          flg=False
  if flg:
    ans = max(ans,sum(ans_list))
print(ans)

Submission status: Accepted

Solution code:
import itertools

n = int(input())

l = list(itertools.product([0,1], repeat=n))[::-1]

A = {}
for i in range(n):
    ai = int(input())
    for j in range(ai):
        x, y = map(int, input().split())
        if i not in A:
            A[i] = []
        A[i].append((x, y))
    if ai == 0:
        A[i] = []


def shoujiki(i):
    check = {}
    cnt = 0
    for j in range(n):
        check[j+1] = i[j]
    for j in range(n):
        ai = len(A[j])
        if i[j] == 1:
            for k in range(ai):
                x, y = A[j][k]
                if check[x] != y:
                    return 0
    #return (check, shougen, cnt0, cnt)
    return sum(i)

mans = 0
for i in l:
    mans = max(shoujiki(i), mans)

print(mans)

Submission status: Accepted

Solution code:
from collections import deque


def do_code():
    num = int(input())
    matrix = [[2] * (num + 1) for _ in range(num + 1)]
    honests = [set() for _ in range(num + 1)]
    unkinds = [set() for _ in range(num + 1)]
    # 人iは1〜Nのためインデックス0は使わずに1~Nで使うようにする
    for n in range(1, num + 1):
        u = set()
        h = set()
        ans = int(input())
        for a in range(ans):
            x, y = map(int, input().split(" "))
            if y == 1:
                h.add(x)
            else:
                u.add(x)
        honests[n] = h
        unkinds[n] = u
    count = 0
    for n in range(1, 2 ** num):
        honest_set = set()
        for j in range(num):
            t = 2 ** j
            if n & t == t:
                honest_set.add(j + 1)
        th = set()
        tu = set()
        queue = deque(honest_set)
        visited = set()
        while len(queue) > 0:
            t = queue.popleft()
            if t in visited:
                continue
            visited.add(t)
            queue.extend(honests[t])
            th |= honests[t]
            tu |= unkinds[t]
        if not th.isdisjoint(tu):
            # 正直者と仮定した人の証言を集めた場合にhonest && unkindな人がいる＝矛盾
            continue
        if not honest_set.isdisjoint(tu):
            continue
        honest = max(len(th), len(honest_set))
        count = max(count, honest)
    print(count)


if __name__ == '__main__':
    do_code()

Submission status: Accepted

Solution code:
import itertools
n = int(input())
b = []
for i in range(n):
  a = int(input())
  c = []
  for j in range(a):
    x, y = map(int, input().split())
    c.append([x,y])
  b.append(c)
g = []
for i in list(itertools.product(range(2) ,repeat = n)):
  flag = True
  for j in range(n):
    if i[j] == 0:
      continue
    for x,y in b[j]:
      if i[x-1] != y:
        flag = False
        break
    if not flag:
      break
  if flag:
    g.append(sum(i))
print(max(g))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product

def solve(n,a):
    testimony = product([0,1],repeat=n)
    ans = 0
    for l in testimony:
        flag = True
        for test in a:
            if l[test[0]] and l[test[1]] and (test[2] == 0):
                flag = False
            if l[test[0]] and l[test[1]]==0 and test[2]:
                flag = False
        if flag:
            ans = max(ans,sum(l))
    return ans



def main():
    N = int(input())
    a = []
    for i in range(N):
        tmp = int(input())
        for _ in range(tmp):
            x,y = map(int,input().split())
            a.append([i,x-1,y])
    print(solve(N,a))
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
A=[]
for i in range(n:=int(input())):
  for _ in range(int(input())): x,y=map(int,input().split()); A+=[(i,x-1,y)]
print(max(sum(map(int,bin(i)[2:]))*all(i>>j&1<1 or i>>x&1==y for j,x,y in A) for i in range(2**n)))

Submission status: Accepted

Solution code:
n=int(input())
A=[]
for i in range(n):
  for _ in range(int(input())):
    x,y=map(int,input().split())
    A+=[(i,x-1,y)]
print(max(sum(map(int,bin(i)[2:]))*all(i>>j&1<1 or i>>x&1==y for j,x,y in A) for i in range(2**n)))

Submission status: Accepted

Solution code:
n=int(input())
A=[]
for i in range(n):
  for _ in range(int(input())):
    x,y=map(int,input().split())
    A+=[(i,x-1,y)]
print(max(sum(map(int,bin(i)[2:])) for i in range(2**n) if all(i>>j&1<1 or i>>x&1==y for j,x,y in A)))

Submission status: Accepted

Solution code:
n=int(input())
A=[]
for i in range(n):
  for _ in range(int(input())):
    x,y=map(int,input().split())
    A+=[(i,x-1,y)]
a=0
for i in range(2**n):
  if all(i>>j&1<1 or i>>x&1==y for j,x,y in A):
    a=max(a,sum(map(int,bin(i)[2:])))
print(a)

Submission status: Accepted

Solution code:
n=int(input())
A=[{} for _ in range(n)]
for i in range(n):
  for _ in range(int(input())):
    x,y=map(int,input().split())
    A[i][x]=y
a=0
for i in range(2**n):
  t=0
  for j in range(n):
    if i>>j&1:
      if A[j] and any(i>>~-k&1!=A[j][k] for k in A[j]): break
      else: t+=1
  else: a=max(a,t)
print(a)

Submission status: Accepted

Solution code:
n=int(input())
lst=[]
for i in range(n):
    a=int(input())
    b=[]
    for j in range(a):
        x,y=map(int,input().split())
        x-=1
        b.append([x,y])
    lst.append(b)
ans=0
for i in range(2**n):
    on=[]
    switch=0
    for j in range(n):
        if ((i>>j)&1):
            on.append(j)
    for j in on:
        judge=lst[j]
        for k in judge:
            if k[1]==1:
                if not k[0] in on:
                    switch=1
            else:
                if k[0] in on:
                    switch=1
    if switch==0:
        ans=max(ans,len(on))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
tst = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        tst[i].append([x,y])
ans = 0
for bit in range(1<<n):
    honest = [0]*n
    check = 1
    for i in range(n):
        if (bit>>i)&1:
            honest[-1-i] = 1
    for i in range(n):
        if not honest[i]:
            continue
        for l in tst[i]:
            if l[1]!=honest[l[0]-1]:
                check = 0
                break
    if check:
        ans = max(ans,sum(honest))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
tst = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        tst[i].append([x,y])
ans = 0
for bit in range(1<<n):
    liars = [0]*n
    check = 1
    for i in range(n):
        if (bit>>i)&1:
            liars[-1-i] = 1
    for i in range(n):
        if not liars[i]:
            continue
        for l in tst[i]:
            if l[1]!=liars[l[0]-1]:
                check = 0
                break
    if check:
        ans = max(ans,sum(liars))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
tst = [[] for i in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    x,y = map(int,input().split())
    tst[i].append([x,y])
ans = 0
for bit in range(1<<n):
  liars = [0]*n
  check = 1
  for i in range(n):
    if (bit>>i)&1:
      liars[-1-i] = 1
  for i in range(n):
    if liars[i]:
      for l in tst[i]:
        if l[1]!=liars[l[0]-1]:
          check = 0
          break
  temp = 0
  if check:
    temp = sum(liars)
  ans = max(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
testimonies = [[] for i in range(n)]
for idx1 in range(n):
    count = int(input())
    for idx2 in range(count):
        x,y = map(int, input().split())
        testimonies[idx1].append((x-1, y))

output = 0
for combination in range(2 ** n):
    consistent = True
    for index in range(n):
        if (combination >> index) & 1 == 0:
            continue
        for x,y in testimonies[index]:
            if (combination >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        output = max(output, bin(combination)[2:].count("1"))
print(output)

Submission status: Accepted

Solution code:
N = int(input())
a = [[] for _ in range(N)]
for i in range(N):
  A_i = int(input())
  for j in range(A_i):
    a[i].append(list(map(int, input().split())))

max_person = 0
for i in range(2**N):
  judge = True
  bin_num = bin(i)
  times = 0
  for j in reversed(bin_num):
    if j == "b":
      break
    if j == "1":
      for k in a[times]:
        if ((i >> k[0]-1) & 1) != k[1]:
          judge = False
    times += 1
  true_person = bin_num.count("1")
  if judge == True:
    max_person = max(max_person, true_person)
print(max_person)

Submission status: Accepted

Solution code:
N = int(input())
a = [[] for _ in range(N)]
for i in range(N):
  A_i = int(input())
  for j in range(A_i):
    a[i].append(list(map(int, input().split())))

max_person = 0
for i in range(2**N):
  judge = True
  bin_num = bin(i)
  times = 0
  end = False
  for j in reversed(bin_num):
    if j == "b":
      break
    if j == "1":
      for k in a[times]:
        if ((i >> k[0]-1) & 1) != k[1]:
          judge = False
    times += 1
  true_person = bin_num.count("1")
  if judge == True:
    max_person = max(max_person, true_person)
print(max_person)

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())

li = [[] for i in range(N)]
A = [0]*N
for i in range(N):
    a = int(input())
    A[i]=a
    li[i]=[list(map(int,input().split())) for i in range(a)]

counter = 0
for humen in product([0,1],repeat=N):
    flag = True
    for i in range(N):
        if humen[i]==1:
            for s in range(A[i]):
                if not li[i][s][1]==humen[li[i][s][0]-1]:
                    flag=False
                    break
        
                
    if flag :
        counter = max(counter,humen.count(1))


print(counter)

Submission status: Accepted

Solution code:
n = int(input())
a = [0 for _ in range(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]):
        s,t = map(int,input().split())
        x[i].append(s)
        y[i].append(t)
ans = 0
for i in range(2**n):
    karishoujiki = []
    shoujiki = []
    usotuki = []
    for j in range(n):
        if (i>>j)&1:
            karishoujiki.append(j)
            for k in range(a[j]):
                if y[j][k] == 1:
                    shoujiki.append(x[j][k]-1)
                else:
                    usotuki.append(x[j][k]-1)
    flag = 1
    shoujikiflag = [0 for _ in range(n)]
    karishoujikiflag = [0 for _ in range(n)]
    usotukiflag = [0 for _ in range(n)]
    for i in range(len(shoujiki)):
        shoujikiflag[shoujiki[i]] = 1
    for i in range(len(karishoujiki)):
        karishoujikiflag[karishoujiki[i]] = 1
    for i in range(len(usotuki)):
        usotukiflag[usotuki[i]] = 1
    
    for i in range(n):
        if shoujikiflag[i] and not karishoujikiflag[i]:
            flag = 0
        if usotukiflag[i] and karishoujikiflag[i]:
            flag = 0
    
    if flag:
        ans = max(ans,len(karishoujiki))

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N = Scanner.int()
    A = [[-1 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        a = Scanner.int()
        for _ in range(a):
            x, y = Scanner.map_int()
            x -= 1
            A[i][x] = y
    ans = 0
    for i in range(1 << N):
        truth = [False for _ in range(N)]
        for j in range(N):
            if i >> j & 1:
                truth[j] = True
        isOK = True
        for j in range(N):
            if not truth[j]:
                continue
            for k in range(N):
                if j == k:
                    continue
                if A[j][k] == 0 and truth[k]:
                    isOK = False
                if A[j][k] == 1 and not truth[k]:
                    isOK = False
        if isOK:
            ans = max(sum(truth), ans)
    print(ans)


def main():
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
T = []
try:
	while True:
		t = input()
		t=int(t)
		T_temp=[]
		for t_ in range(t) :
			temp = list(map(int,input().split()))
			T_temp.append(temp)
		T.append(T_temp)
except EOFError:
	pass
    
def check_Contradiction(true_list):
    S = {}
    for n in range(N):
        if n in true_list:
            S[n]=set([1])
        else:
            S[n]=set([0])

    for t in true_list:
        for T_ in T[t]:
            S[T_[0]-1].add(T_[1])
    ok=True
    for s in S.keys():
        if len(S[s])!=1:
            ok='False'
            break

    return ok

ok_max = -1
for i in range(2**N):
#     print('=====',i)
    true_list=[]
    for j in range(N):
        if i>>j&1 ==True:
            true_list.append(j)
#     print(true_list)
#     print(check_Contradiction(true_list))
            
    if check_Contradiction(true_list)==True:
        if ok_max < len(true_list):
            ok_max=len(true_list)
            
print(ok_max)