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
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines

n = int(input())
#a = [int(i) for i in readline().split()]

shogen = [None for _ in range(n)]

for i in range(n):
    c = int(input())
    g = []
    for _ in range(c):
        p,q = [int(i) for i in readline().split()]
        g.append([p-1,q])
    
    #print(g)
    shogen[i] = g


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

N = 2**n
ans = 0
for mask in range(N):
    c = check(mask)
    #if c: print(mask,c)
    ans = max(ans,c)    

print(ans)

Submission status: Accepted

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

for i in range(n):
    a = int(input())
    shogens.append([])
    for j in range(a):
        x, y = map(int, input().split())
        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 sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[None]*n
    for i in range(n):
        a=int(input())
        XY=[tuple(map(int,input().split())) for _ in range(a)]
        E[i]=XY

    N=2**n
    ans=0
    for S in range(N):
        flag=True
        for i in range(n):
            if((S>>i)&1)==0: continue # 正直者のみを見る
            for x,y in E[i]:
                x-=1
                if((S>>x)&1)!=y:
                    flag=False
        if(flag):
            ans=max(ans,bin(S).count('1'))
    print(ans)
resolve()

Submission status: Accepted

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


best = 0

def check(state):
	for i in range(N):
		if state[i] == 1:
			for x, y in data[i]:
				if y != state[x]:
					return False
	return True

def combination(state):
	global best
	if len(state) == N:
		if check(state):
			count = sum(state)
			if count > best:
				best = count
	else:
		combination(state + [0])
		combination(state + [1])

combination([])

print(best)

Submission status: Accepted

Solution code:
n = int(input())
from collections import defaultdict
dic = defaultdict(list)

for i in range(n):
    a = int(input())
    for _ in range(a):
        x,y = map(int,input().split())
        dic[i].append((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
    
    for idx, b in enumerate(bit):
        if b == 1:
            for x,y in dic[idx]:
                if bit[x] != y:
                    break
            else:
                continue
            break
    else:
        ans = max(ans, sum(bit))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        l[i].append([x,y])
op=['0','1']
for i in range(n-1):
    tmp=[]
    for j in op:
        tmp.append(j+'0')
        tmp.append(j+'1')
    op=tmp
ans=0
for i in op:
    t=list(i)
    f=0
    for j in range(n):
        if i[j]=='1':
            for k in l[j]:
                if t[k[0]-1]!=str(k[1]):
                    f+=1
    if f==0:
        p=0
        for q in t:
            if q=='1':
                p+=1
        ans=max(ans,p)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())


memo = []
for i in range(N):
    a = int(input())
    l = []
    for _ in range(a):
        x,y = map(int,input().split())
        l.append((x-1,y==1))
    memo.append(l)
    
def check(p):
    return all(p[x]==y for i,l in enumerate(memo) for x,y in l if p[i])

m = max(sum(p) for p in product((True,False), repeat=N) if check(p))
print(m)

Submission status: Accepted

Solution code:
n = int(input())

a = [0] * n
d = [[] for _ in range(n)]
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        d[i].append(tuple(map(int, input().split())))

def decode(s):
    r = [0] * n
    for i in range(n):
        r[i] = int(bool(s & (1 << i)))
    return r

def validate(s):
    r = decode(s)
    for i in range(n):
        if not r[i]:
            continue
        for x, y in d[i]:
            if r[x - 1] != y:
                return 0
    return sum(r)

def solve():
    ans = 0
    for i in range(2 ** n):
        ans = max(ans, validate(i))
    print(ans)

solve()

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    a=[]
    x=[]
    for i in range(n):
        a.append(int(input()))
        x.append([list(map(int,input().split())) for _ in [0]*a[-1]])
    cnt=0
    for i in range(2**n):
        flag=0
        c=("0"*n+bin(i)[2:])[-n:]
        for i in range(n):
            if c[i]=="0":
                continue
            for j,k in x[i]:
                if (k==1 and c[j-1]=="0") or (k==0 and c[j-1]=="1"):
                    flag=1
                    break
        if flag==1:
            continue
        cnt=max(cnt,c.count("1"))
    print(cnt)
main()

Submission status: Accepted

Solution code:
n = int(input())
info = [[] 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
        info[i].append((x, y))

ans = 0
for bit_state in range(1 << n):
    flag = True
    for i in range(n):
        # i番目は正直者
        if (bit_state >> i) & 1:
            for x, y in info[i]:
                if (bit_state >> x) & 1 != y:
                    flag = False
    if flag:
        ans = max(bin(bit_state).count("1"), ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
words = []
for i in range(n):
	a = int(input())
	w = []
	for _ in range(a):
		x, y = map(int, input().split())
		w.append([x-1, y])
	words.append(w)

#print(words)
ans = 0
for bit in range(1<<n):
	ok = True
	is_honest = [(bit>>i) & 1 for i in range(n)]
	#print(is_honest)
	for i in range(n):
		if not is_honest[i]:
			continue
		for x, y in words[i]:
			if is_honest[x] != y:
				ok = False
	if ok:
		ans = max(ans, sum(is_honest))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

g = [[-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 s in range(2**n):
	ok = True
	for i in range(n):
		if (s>>i&1) == 1:
			for j in range(n):
				if g[i][j] == -1: continue
				if (s>>j&1) != g[i][j]: ok = False
	if ok:
		#print("s = ", s)
		t = 0
		x = s
		while x > 0:
			t += x%2
			x //= 2
		ans = max(ans, t)

print(ans)

Submission status: Accepted

Solution code:
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())))

#print(data)
ans = 0
for i in range(1<<n):
    truth = []
    for x in range(n):
        if i&(1<<x):
            truth.append(x+1)

    q = True
    for j in truth:
        for x,y in data[j-1]:
            if x in truth and y == 0:
                q = False
                break
            if x not in truth and y == 1:
                q = False
                break
    if q:
        ans = max(ans,len(truth))
        #print(truth)

print(ans)

Submission status: Accepted

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

N=int(input())
C=[]
for i in range(N):
    A=int(input())
    B=[tuple(map(int,input().split())) for i in range(A)]
    C.append(B)

ANS=0

for i in range(1<<N):
    HONEST=[j for j in range(N) if 1<<j & i !=0]

    #print(i,HONEST)

    flag=1

    for h in HONEST:
        for p,k in C[h]:
            if k==1:
                if p-1 in HONEST:
                    continue
                else:
                    flag=0
                    break

            else:
                if p-1 in HONEST:
                    flag=0
                    break
        if flag==0:
            break

    if flag==1:
        #print(i,HONEST)
        ANS=max(ANS,len(HONEST))

print(ANS)

Submission status: Accepted

Solution code:
N = int(input())
B = [[] for i in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        B[i].append((x-1, y))
ans = 0
for s in range(1<<N):
    flag1 = True
    cnt = 0
    for i in range(N):
        if s&(1<<i):
            cnt+=1
            flag2 = True
            for x, y in B[i]:
                if ((s>>x)&1) != y:
                    flag2 = False
                    break
            if not flag2:
                flag1 = False
    if flag1:
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

A =[]
for i in range(n):
    m = int(input())
    A.append([list(map(int,input().split())) for i in range(m)])

# print(A)
ans = 0
for i in range(2**n):
    r = 1
    ib = list(format(i, "b").zfill(n))
    # print(ib)
    for j in range(n):
        if ib[j] == "1":
            for k in range(len(A[j])):
                if int(ib[A[j][k][0]-1]) != A[j][k][1]:
                    r = 0
    if r == 1:
        ans = max(ans, ib.count("1"))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
data = [[] for _ in range(N)]

for i in range(N):
    Ai = int(input())
    
    for _ in range(Ai):
        xi, yi = map(int, input().split())
        data[i].append((xi-1, yi))
    
ans = 0

for i in range(2**N):
    flag = [False]*N
    ans_cand = 0
    
    for j in range(N):
        if (i>>j)&1:
            flag[j] = True
            ans_cand += 1
    
    F = True
    
    for j in range(N):
        if flag[j]:
            for xi, yi in data[j]:
                if (yi==0 and flag[xi]) or (yi==1 and not flag[xi]):
                    F = False
                    
    if F:
        ans = max(ans, ans_cand)

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1 << N):
  ok = True
  cnt = 0
  for j in range(N):
    if (i >> j & 1) == 1:
      cnt += 1
  for j in range(N):
    if (i >> j & 1) == 1:
      for x, y in A[j]:
        if y == 0:
          if (i >> x & 1) == 1:
            ok = False
        elif y == 1:
          if (i >> x & 1) == 0:
            ok = False
  if ok:
    ans = max(ans, cnt)

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
testimony = [[-1]*N for i in range(N)]
count = 0
for i in range(N):
  A = int(input())
  for j in range(A):
    x,y = map(int,input().split())
    testimony[i][x-1]=y
fro i in range(2**N):
  honest = [0]*N
  for j in range(N):
    if(i>>j)&1:
      honest[j]=1
  flag=True
  for j in range(N):
    if honest[j]==1:
      for k in range(N):
        if testimony[j][k]==-1:
          continue
        if testimony[j][k]!=honest[k]:
          flag=False
  if flag==True:
    count=max(count,hones.count(1))
print(count)

Submission status: Runtime Error

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


ans=0
for bit_state in range(2**N):
  flag=True
  for i in range(N):
    if (bit_state>>i)&1:
      for x, y in XY[i]:
        if (bit_state >>x)&1 != y:
          flag=False
  if flag:
    ans=max(ans, bin(bit_state).count("1"))
    
print(ans)

Submission status: Runtime Error

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

ans=0
for bit_state in range(1<<N):
  flag=True
  for i in range(N):
    if (bit_state>>i)&1:
      for x, y in XY[i]:
        if (bit_state >>x)&1 != y:
          flag=False
  if flag:
    ans=max(ans, bin(bit_state>>x).count("1"))
    
print(ans)

Submission status: Runtime Error

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

ans=0
for bit_state in range(2**N):
  flag=True
  for i in range(N):
    if (bit_state>>i)&1:
      for x, y in XY[i]:
        if (bit_state >>x)&1 != y:
          flag=False
  if flag:
    ans=max(ans, bin(bit_state>>x).count("1"))
    
print(ans)

Submission status: Runtime Error

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

ans=0
for bit_state in range(2**N):
  flag=True
  for i in range(N):
    if (bit_state>>i)&1:
      for x, y in XY[i]:
        if (bit_state >>x)&1 != y:
          flag=False
  if flag:
    ans=max(ans, bin(bit_state>>x).count("1"))
    
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
li = [np.full(n, -1, dtype=np.int) for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        li[i][x-1] = y

ans = 0
for i in range(2**n):
    s = 0
    t = [0]*n
    for j in range(n):
        if i>>j & 1:
            t[j]=1
    is_contradict = 0
    for j in range(n):
        if t[j]:
            for k in range(n):
                if li[j][k]==-1:
                    continue
                if li[j][k] != t[k]:
                    is_contradict = 1
    if not is_contradict:
        ans = max(ans, sum(t))

print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
XY=[]
for _ in range(N):
    A=int(input())
    xylist=[]
    for _ in range(A):
        xylist.append(list(map(int,input().split())))
    XY.append(xylist)
    ans=0
for i in range(2**N):
    num=0
    honest=[-1]*N
    for person in range(N):
        if i&(2**person)>0:
            if honest[person]!=1 and honest[person]!=-1:
                num=0
                break
            elif honest[state[0]-1]==-1:
                honest[person]=1
                num+=1
            for state in XY[person]:
                if state[1]!=honest[state[0]-1] and honest[state[0]-1]!=-1:
                    num=0
                    break
                elif honest[state[0]-1]==-1:
                    honest[state[0]-1]=state[1]
                    if state[1]==1:
                        num+=1
            else:
                continue
            num=0
            break
        else:
            if honest[person]!=0 and honest[person]!=-1:
                num=0
                break
            else:
                honest[person]=0
            for state in XY[person]:
                if state[1]!=1-honest[state[0]-1] and honest[state[0]-1]!=-1:
                    num=0
                    break
                elif honest[state[0]-1]==-1:
                    honest[state[0]-1]=1-state[1]
                    if state[1]==0:
                        num+=1
            else:
                continue
            num=0
            break
    ans=max(ans,num)
print(ans)

Submission status: Runtime Error

Solution code:
#
# joi2008yo e
#
import sys
from io import StringIO
import unittest
import copy


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2 5
0 1 0 1 0
1 0 0 0 1"""
        output = """9"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 6
1 0 0 0 1 0
1 1 1 0 1 0
1 0 1 1 0 1"""
        output = """15"""
        self.assertIO(input, output)


def resolve():
    R, C = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(R)]
    A_rev = [[1 - v for v in a] for a in A]

    ans = 0
    for bit in range(1 << R):
        num = 0
        T = copy.deepcopy(A)
        for i, t in enumerate(T):
            if 1 << i & bit:
                T[i] = A_rev[i]

        T = list(zip(*T))
        for t in T:
            num += max(t.count(0), t.count(1))
        ans = max(ans, num)

    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Runtime Error

Solution code:
from itertools import product

n = int(input())

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

ret = 0
for x in product((0, 1), repeat=n):
  tmp = [-1] * n
  ok = True
  for i in range(n):
    if x[i] == 1:
      for y in d[i + 1]:
        if tmp[y[0] - 1] == -1:
          tmp[y[0] - 1] = y[1]
        elif tmp[y[0] - 1] != y[1]:
          ok = False
          break
    if not ok:
      break
  if ok and all(a == b or b == -1 for a, b in zip(x, tmp)):
    ret = max(ret, sum(x))

print(ret)

Submission status: Runtime Error

Solution code:
N = int(input())
XY_list = [[] for _ in range(N)]
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        XY_list[i].append([person - 1, state])
ans = 0
for i in range(1 << N):
    bool = True
    for j in range(N):
        if (i >> j) & 1 == 1:
            for person, state in XY_list[j]:
                if (i >> person) & 1 != state:
                    bool = False
                    break
"""
        else:
            for person, state in XY_list[j]:
                if (i >> person) & 1 == state:
                    bool = False
                    break
"""
    if bool:
        ans = max(ans, bin(i)[2:].count("1"))
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
XY=[[[]] for n in range(N)]
for n in range(1,N+1):
  a=int(input())
  XY[n]=[list(map(int, input().split())) for _ in range(a)]

maxH=0
for mask_i in range(1<<N):
  
  H=[0]*(N+1)
  for n in range(N):
    if mask_i>>n&1:
      H[n+1]=1
  #print(H[1:])
  
  for n in range(1,N+1):
    ok=True
    if H[n]==1:
      for x,y in XY[n]:
        if H[x]!=y:
          ok=False
          break
  if ok:
    maxH=max(maxH,sum(H))

print(maxH)

Submission status: Runtime Error

Solution code:
n = int(input())
ls = [0]*n
param_list = [0]*2**n
for i in range(2**n):
    l = [False]*n
    for id_r, row in enumerate(ls):
        if i & (2 ** id_r) >0:
            l[id_r] = True
    param_list[i] = l 
#1print(param_list)
"""
for i in range(2**(n-1)):
    l = [True]+[False]*(n-1)
    for id_r, row in enumerate(ls):
        if i & id_r >0:
            l[id_r] = True
    param_list[i+2**(n-1)] = l 
print()
print(len(param_list))
print(param_list)
a_list = get_unique_list(param_list)
print(len(a_list))
print(a_list)"""

for i in range(n):
    A = int(input())
    for k in range(A):
        a,b = map(int, input().split())
        b = (1==b)
        new_param =[]
        for d in a_list:
            if d[i]:
                if d[a-1] == b:
                    new_param.append(d)
                    pass
                else:
                    #print(2)
                    pass
            else:
                new_param.append(d)
                #if d[a-1] is b:
                    #print(3)
                    #pass
                #else:
                    #print(4)
                    #new_param.append(d)
                    #pass
            
        param_list = new_param
        #print(param_list)
            
ans = 0    
for d in param_list:
    ans = max(ans, d.count(True))
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
XYList = []
for i in range(N):
    A = int(input())
    for j in range(A):
        XY = []
        XY.append(list(map(int, input().split())))
    XYList.append(XY)
maxSum = 0
for i in range(2**N):
    sum = 0
    for j in range(N):
        if i >> j & 1:
            honest = True
            for XY in XYList[j]:
                if ((i >> (XY[0]-1)) & 1) != XY[1]:
                    honest = False
                    break
            if honest:
                sum += 1
            else:
                sum = 0
                break
    if maxSum < sum:
        maxSum = sum
print(maxSum)

Submission status: Runtime Error

Solution code:
n = int(input())

check = []
ans = []
for i in range(n):
  a = int(input())
  for _ in range(a):
    tmp = list(map(int,input().split()))
    check.append(tmp)
  ans.append(check[-1][1])

def count(ans):
  x = ans.count(1)
  print(x)
count(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = []
x = []
y = []
for i in range(N):
    A.append(int(input()))
    bx = [0] * A[i]
    by = [0] * A[i]
    for j in range(A[i]):
        bx[j], by[j] = map(int, input().split())
    x.append(bx)
    y.append(by)

ma = 0
ans = []
for i in range(2**N):
    flg = 0
    ans.append(bin(i))
    for j in range(N):
        if (i >> j) & 1:
            for k in range(A[j]):
                if str(bin(i))[-x[j][k]] == str(y[j][k]):
                    continue
                else:
                    flg = 1
                    ans.pop(-1)
                    break
        if flg == 1:
            break
    ma = max(ma, list(ans[-1]).count('1'))
print(ma)

Submission status: Runtime Error

Solution code:
N = int(input())
A = []
x = []
y = []
for i in range(N):
    A.append(int(input()))
    bx = [0] * A[i]
    by = [0] * A[i]
    for j in range(A[i]):
        bx[j], by[j] = map(int, input().split())
    x.append(bx)
    y.append(by)

ma = 0
ans = []
for i in range(2**N):
    flg = 0
    ans.append(bin(i))
    for j in range(N):
        if (i >> j) & 1:
            for k in range(A[j]):
                if str(bin(i))[-x[j][k]] == str(y[j][k]):
                    pass
                else:
                    flg = 1
                    ans.pop(-1)
                    break
        if flg == 1:
            break
    ma = max(ma, list(ans[-1]).count('1'))
print(ma)

Submission status: Runtime Error

Solution code:
N = int(input())
A = []
x = []
y = []
for i in range(N):
    A.append(int(input()))
    bx = [0] * A[i]
    by = [0] * A[i]
    for j in range(A[i]):
        bx[j], by[j] = map(int, input().split())
    x.append(bx)
    y.append(by)

ma = 0
ans = []
for i in range(2**N):
    flg = 0
    ans.append(bin(i))
    for j in range(N):
        if (i >> j) & 1:
            for k in range(A[j]):
                ni = str(bin(i))
                if ni[-x[j][k]] == str(y[j][k]):
                    pass
                else:
                    flg = 1
                    ans.pop(-1)
                    break
        if flg == 1:
            break
    ma = max(ma, list(ans[-1]).count('1'))
print(ma)

Submission status: Runtime Error

Solution code:
N = int(input())
A = []
x = []
y = []
for i in range(N):
    A.append(int(input()))
    bx = [0] * A[i]
    by = [0] * A[i]
    for j in range(A[i]):
        bx[j], by[j] = map(int, input().split())
    x.append(bx)
    y.append(by)

ans = []
for i in range(2**N):
    flg = 0
    ans.append(bin(i))
    for j in range(N):
        if (i >> j) & 1:
            for k in range(A[j]):
                ni = str(bin(i))
                if ni[-x[j][k]] == str(y[j][k]):
                    pass
                else:
                    flg = 1
                    ans.pop(-1)
                    break
        if flg == 1:
            break
ma = 0
for i in range(len(ans)):
    ma = max(ma, list(ans[i]).count('1'))
print(ma)

Submission status: Runtime Error

Solution code:
N = int(input())
A = []
x = []
y = []
for i in range(N):
    A.append(int(input()))
    bx = [0] * A[i]
    by = [0] * A[i]
    for j in range(A[i]):
        bx[j], by[j] = map(int, input().split())
    x.append(bx)
    y.append(by)

ans = []
for i in range(2**N):
    flg = 0
    ans.append(bin(i))
    for j in range(N):
        if (i >> j) & 1:
            for k in range(A[j]):
                ni = str(bin(i))
                #print(ni)
                if ni[-x[j][k]] == str(y[j][k]):
                    pass
                else:
                    flg = 1
                    ans.remove(bin(i))
                    break
        if flg == 1:
            break
ma = 0
for i in range(len(ans)):
    ma = max(ma, list(ans[i]).count('1'))
print(ma)

Submission status: Runtime Error

Solution code:
N = int(input())
A = []
x = []
y = []
for i in range(N):
    A.append(int(input()))
    bx = [0] * A[i]
    by = [0] * A[i]
    for j in range(A[i]):
        bx[j], by[j] = map(int, input().split())
    x.append(bx)
    y.append(by)

ans = []
for i in range(2**N):
    flg = 0
    ans.append(bin(i))
    for j in range(N):
        if (i >> j) & 1:
            for k in range(A[j]):
                ni = list(str(bin(i)))
                if ni[-x[j][k]] == str(y[j][k]):
                    pass
                else:
                    flg = 1
                    ans.remove(bin(i))
                    break
        if flg == 1:
            break
ma = 0
for i in range(len(ans)):
    ma = max(ma, list(ans[i]).count('1'))
print(ma)

Submission status: Runtime Error

Solution code:
N = int(input())
ListN=[]*
List = []
keepOrder
for i in range(N):
  k = int(input())
  ListN.append(k)
  for j in range(k):
    List.append(list(map(int, input().split())))
for bits in range(2**N):
  keepOrder = list(bin(bits))
  flag= True
  print(bits,keepOrder)
  for j in range(N):
    if((bits>>j) & 1): 
      for k in range(ListN[j]):
        if keepOrder[List[k][0]-1]!=List[k][1]:
          flag = False
    else:
        if keepOrder[List[k][0]-1]==List[k][1]:
          flag = False
  if flag:
    res = max(res,keepOrder.count("1")
print(res)

Submission status: Runtime Error

Solution code:
import itertools
n = int(input())
l = []
for i in range(n):
  d = int(input())
  for dd in range(d):
    x, y = map(int, input().split())
    l.append([i, x-1, y])
    
ans = 0
for p in itertools.product([0, 1], repeat=n):
  for ll in l:
    if p[ll[0]] == 1 and p[ll[1] != ll[2]:
		break
	else:
		ans = max(ans, sum(p))
print(ans)

Submission status: Runtime Error

Solution code:
# ABC_147_C_HonestOrUnkind2.py

N=int(input())
A=[]
for i in range(N):
    a=int(input())
    xy=[list(map(int, input().split())) for _ in range(a)]
    A.append([a,xy])
# print(A)

# 下からi桁目のbitが1->人iは正直
# 下からi桁目のbitが0->人iは不親切

ans=0
for i in range(2**N):
    for j in range(N):
        for k in range(A[j][0]):
            flag=0
            if (i >> j) & 1 != A[j][1][k][1]:
                flag=1
                break
        if flag==1:
                break
    else:
        # print(bin(i))
        ct=0
        for l in range(N):
            ct+=((i>>l)&1)
        ans=max(ans,ct)

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
XY = {}
for i in range(1, N + 1):
    a = int(input())
    xy = []
    for j in range(a):
        t = list(map(int, input().split()))
        xy.append(t)
    XY[i] = xy
#print(XY)

import itertools

target = list(itertools.product([0, 1], repeat=N))
#print(target)


def check(XY, target):
    for xy in XY:
        t, s = xy[0] - 1, xy[1]
        if target[t] != s:
            return False
    return True

ans = 0
for t in target:
    is_OK = True
    for i in range(N):
        if not check(XY[i], t):
            is_OK = False
            break
    if is_OK:
        ans = max(ans,t.count(1))
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
g = [[-1]* 15 for _ in range(15)]
for i in range(n) :
    m = int(input())
    for j in range(n) :
        x, y = map(int, input().split())
        #人iが「人xはyである」と証言している
        g[i][x-1] = y

ans = 0
for i in range(1<<n) :
    honest = [0] * n
    for j in range(n) :
        if (i>>j) & 1 == 1 :
            honest[j] = 1
    #ここまでですべての組み合わせを網羅している
    ok = True
    for j in range(n) :
        if honest[j] : #正直者の証言だけ検証する
            for k in range(n) :
                if g[j][k] == -1 :
                    continue
                if g[i][j] != honest[k] :
                    ok = False
            if ok :
                ans = max(ans, honest.count(1))
print(ans)