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: Runtime Error

Solution code:
N = int(input())
total = 0
tmp = 0
A = []
xy = []
l = []
for i in range(N):
  A.append(int(input())
  for j in range(A[i]):
    l.append(list(map(int,input().split())))
  xy.append(l)
  l.clear()
for i in range(2**N):
  flag = 1
  t = format(i, '0{}b'.format(N))
  for k in range(N):
    if t[k] == '1':
      tmp += 1
      for l in range(A[k]):
        if int(t[xy[k][l][0]-1]) != xy[k][l][1]:
          flag = 0
          break
      else:
        continue
      break
  if flag == 1 and total < tmp:
    total = tmp
  tmp = 0
print(total)

Submission status: Runtime Error

Solution code:
N = int(input())
total = 0
tmp = 0
A = []
xy = []
l = []
for i in range(N):
  A.append(int(input())
  for j in range(A[i]):
    l.append(list(map(int,input().split())))
  xy.append(l)
  l.clear()
for i in range(2**N):
  flag = 1
  i = format(i, '0{}b'.format(N))
  for k in range(N):
    if i[k] == '1':
      tmp += 1
      for l in range(A[k]):
        if int(i[xy[k][l][0]]) != xy[k][l][1]:
          flag = 0
          break
      else:
        continue
      break
  if flag == 1 and total < tmp:
    total = tmp
  tmp = 0
print(total)

Submission status: Runtime Error

Solution code:
N = int(input())
total = 0
tmp = 0
A = []
xy = []
for i in range(N):
  A.append(int(input())
  t = [list(map(int,input().split())) for j in range(A[i])]
  xy.append(t)
for i in range(2**N):
  flag = 1
  i = format(i, '0{}b'.format(N))
  for k in range(N):
    if i[k] == '1':
      tmp += 1
      for l in range(A[k]):
        if int(i[xy[k][l][0]]) != xy[k][l][1]:
          flag = 0
          break
      else:
        continue
      break
  if flag == 1 and total < tmp:
    total = tmp
  tmp = 0
print(total)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
total = 0
tmp = 0
A = []
xy = []
for i in range(N):
  A.append(int(input())
  t = [list(map(int(input().split()))) for j in range(A[i])]
  xy.append(t)
for i in range(2**N):
  flag = 1
  i = format(i, '0{}b'.format(N))
  for k in range(N):
    if i[k] == '1':
      tmp += 1
      for l in range(A[k]):
        if int(i[xy[k][l][0]]) != xy[k][l][1]:
          flag = 0
          break
      else:
        continue
      break
  if flag == 1 and total < tmp:
    total = tmp
  tmp = 0
print(total)

Submission status: Runtime Error

Solution code:
N = int(input())
A = []

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

ans = 0
cnt = 0
bit = format(cnt, "#015b")
for _ in range(2 ** N):
    d = {}
    for i in range(N):
        d[i] = int(bit[-i])

    flag = False
    for i in range(N):
        for x, y in A[i]:
            if d[i] == 1:
                if d[x - 1] == y:
                    pass
                else:
                    flag = True
                    break
            else:
                if d[x - 1] == y:
                    flag = True
                    break
                else:
                    pass

        if flag:
            break

    if flag:
        cnt += 1
        bit = format(cnt, "#015b")
        continue

    a = sum(list(map(int, list(bit[2:]))))
    ans = max(a, ans)
    cnt += 1
    bit = format(cnt, "#015b")


print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N=int(input())
    A=[0]*N
    shougen=[[] for i in range(0,N)]
    for i in range(0,N):
        A[i]=int(input())
        for j in range(0,A[i]):
            a,b=map(int,input().split())
            shougen[i].append([a,b])
    m=0
    for i in range(0,2**N):
        flag=0
        check=[]
        for j in range(0,N):
            if i>>j & 1==1:
                check.extend(shougen[j])
        for j in range(0,N):
            if ([j+1,0] in check) or ([j+1,1] in check):
                if [j+1,0] in check:
                    if j==0:
                        data=[0]
                    else:
                        data.append(0)
                if [j+1,1] in check:
                    if j==0:
                        data=[1]
                    else:
                        data.append(1)

            else:
                if j==0:
                    data=[2]
                else:
                    data.append(2)
        for j in range(0,N):
            if data[j]!=2:
                if int(data[j])!=(i>>j)%2 :
                    flag=1
        if len(data)!=N:
            flag=1
        if flag==0:
            test=sum(i>>j &1 for j in range(0,N))
            if test>m:
                m=test

    print(m)

Submission status: Runtime Error

Solution code:
#ABC 147 C 「Honest or Unkind」

n=int(input())
ans=0
A=[[] for _ in range(n)]

for i in range(n):
    a=int(input())
    for j in range(a):
        A[i].append(tuple(map(int,input().split())))
        
#-------------------------------------------------------------iをn桁２進数表記（[2:]で0bを切って、zfill()で左揃えへ）
for i in range(2**n):
    ii=str(bin(i))[2:].zfill(n)
#-------------------------------------------------------------#i個目の場合が証言をみたすか調べる：2**n個の組み合わせ
    chk=True
    cur=0
 
    for j in range(n):　　　　　　　　　　　　　　　　　　　　　  #j個目の証言を満たすか調べる
        if ii[j]=="0":
            continue
        else:
            cur+=1　　　　　　　　　　　　　　　　　　　　　　　  #Count up 
            for x,y in A[j]:                                  #turpleで(x,y)を指定する
                if y==1 and ii[x-1]=="0":                     #Aとiiを比較
                    chk=False                                 #違っていたらFalseへ
                elif y==0 and ii[x-1]=="1":
                    chk=False
    if chk:　　　　　　　　　　　　　　　　　　　　　　　　　　　　#もしChk = Trueのままだったらn個全ての証言をみたすので、これまでのマックスと比べる
        ans=max(ans,cur)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)

output = 0

N = int(input())

statement_all = []
for _ in range(N):
    M = int(input())
    statement = []
    for _ in range(M):
        temp = list(map(int,input().split()))
        statement.append(temp)
    statement_all.append(statement)


def check(a,b):
    if hypo[a - 1] == b:
        return True
    else:
        return False


pattern = 2 ** N

for p in range(pattern):
    hypo = [0,0,0]
    
    for k in range(N):
        if bin(p>>k & 1) == '0b1':
            hypo[k] = 1    
        if bin(p>>k & 1) == '0b0':
            hypo[k] = 0
    
    result = 0        
    for j in range(N):
        if hypo[j] == 1:
            for i in range(len(statement_all[j])):
                if not check(statement_all[j][i][0],statement_all[j][i][1]):
                    result += 1

    if result == 0:
        output = max(output,sum(hypo))

print(output)

Submission status: Runtime Error

Solution code:
output = 0

N = int(input())

statement_all = []
for _ in range(N):
    M = int(input())
    statement = []
    for _ in range(M):
        temp = list(map(int,input().split()))
        statement.append(temp)
    statement_all.append(statement)


def check(a,b):
    if hypo[a - 1] == b:
        return True
    else:
        return False


pattern = 2 ** N

for p in range(pattern):
    hypo = [0,0,0]
    
    for k in range(N):
        if bin(p>>k & 1) == '0b1':
            hypo[k] = 1    
        if bin(p>>k & 1) == '0b0':
            hypo[k] = 0
    
    result = 0        
    for j in range(N):
        if hypo[j] == 1:
            for i in range(len(statement_all[j])):
                if not check(statement_all[j][i][0],statement_all[j][i][1]):
                    result += 1

    if result == 0:
        output = max(output,sum(hypo))

print(output)

Submission status: Runtime Error

Solution code:
output = 0

N = int(input())

statement_all = []
for _ in range(N):
    M = int(input())
    statement = []
    for _ in range(M):
        temp = list(map(int,input().split()))
        statement.append(temp)
    statement_all.append(statement)

def check(a,b):
    if hypo[a - 1] == b:
        return True
    else:
        return False


pattern = 2 ** N

for p in range(pattern):
    hypo = [0,0,0]
    
    for k in range(N):
        if bin(p>>k & 1) == '0b1':
            hypo[k] = 1    
        if bin(p>>k & 1) == '0b0':
            hypo[k] = 0
    
    result = 0        
    for j in range(N):
        if hypo[j] == 1:
            for i in range(len(statement_all[j])):
                if not check(statement_all[j][i][0],statement_all[j][i][1]):
                    result += 1

    if result == 0:
        output = sum(hypo)

print(output)

Submission status: Runtime Error

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

ans = 0

for i in range(2**n):
    flag = 0
    for j in range(n):
        if (i >> j) & 1:#もし正直者だったら
            for k in ls[j]:#証言の確認
                if (i >> k[0])&1 != k[1]:#もし証言がおかしかったら
                    flag = 1
                    break
    if flag == 0:
        ans = max(ans, bin(i)[2:].count(1))
print(ans)

Submission status: Runtime Error

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

ans = 0

for i in range(2**n):
    flag = 0
    for j in range(n):
        if (i >> j) & 1:
            for k in ls[j]:
                if (i >> k) & 1 != y:
                    flag = 1
                    break
    if flag == 0:
        ans = max(ans, bin(i)[2:].count('1'))
print(ans)

Submission status: Runtime Error

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

ans = 0

for i in range(2**n):
    flag = 0
    for j in range(n):
        if (i >> j) & 1:
            for k in ls[j]:
                if (i >> k[0]) & 1 != y:
                    flag = 1
                    break
    if flag == 0:
        ans = max(ans, bin(i)[2:].count('1'))
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
xy_lst = []
split_lst = []
a_lst = []
for i in range(n):
    a = int(input())
    a_lst.append(a)
    for j in range(a):
        xy = list(map(int,input().split()))
        xy_lst.append(xy)
    if a>1:
        tmp_lst = []
        for k in range(a):
            tmp_lst.append(xy_lst[i*a+k])
        split_lst.append(tmp_lst)
    elif a==1:
        split_lst.append(xy_lst[i])

unkind = 0
for i in range(n):
    a = a_lst[i]
    for j in range(a):
        who = xy_lst[i*a+j][0]
        opinion = xy_lst[i*a+j][1]
        if opinion==1:
            if [i+1, 0] in split_lst[who-1]:
                unkind += 1
                break
        elif opinion==0:
            if [i+1, 1] in split_lst[who-1]:
                unkind += 1
                break

honest_prolst = []
for i in range(n):
    a = a_lst[i]
    for j in range(a):
        who = xy_lst[i*a+j][0]
        opinion = xy_lst[i*a+j][1]
        if opinion==1:
            honest_prolst.append(who)

honest_lst = list(set(honest_prolst))
honest = len(honest_lst)

if honest==0:
    print(1)

else:
    print(honest-unkind)

Submission status: Runtime Error

Solution code:

def sub():
    m = int(input())
    if m == 0:
        return False
    for _ in range(m):
        i,j = map(int,input().split(' '))
        if j == 0:
            return True

def main():
    n = int(input())
    count = 0
    for _ in range(n):
        if sub():
            count += 1
    print(n - count)

main()

Submission status: Runtime Error

Solution code:

n = int(input())
def sub():
    m = int(input())
    if m == 0:
        return False
    for _ in range(m):
        i,j = map(int,input().split(' '))
        if j == 0:
            return True

def main():
    count = 0
    for _ in range(n):
        if sub():
            count += 1

    return print(n - count)

main()

Submission status: Runtime Error

Solution code:
n = int(input())
def sub():
    m = int(input())
    for _ in range(m):
        i,j = map(int,input().split(' '))
        if j == 0:
            return True

def main():
    count = 0
    for _ in range(n):
        if sub():
            count += 1

    return print(n - count)

main()

Submission status: Runtime Error

Solution code:
bestprg2019 
n=int(input())
al=[]
l=[]
for i in range(n):
  a=int(input())
  al.append(a)
  templ=[list(map(int,input().split())) for i in range(a)]
  l.append(templ)
ans=0
for i in range(2**n):
  b=bin(i)
  chkdic={}
  n_honest=0#正直者の人数をカウント
  flag=False#矛盾が生じるかどうか
  for j in range(n):
    if ((i >> j) & 1):#もし正直者なら
      n_honest+=1
      #saying_l=l[j]
      #a=al[j]
      chkdic[j+1]=1
    else:
      chkdic[j+1]=0
  #chkdicをもとに判定
  for j in range(n):
    if ((i >> j) & 1):
      saying_l=l[j]
      a=al[j]
      for k in range(a):
        saying=saying_l[k]
        if chkdic[saying[0]]!=saying[1]:
          flag=True
          break
    if flag:
      break  
  if not flag:
    ans=max(ans,n_honest)
print(ans)

Submission status: Runtime Error

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

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

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

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

print(max_honest)

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

a = []
for i in range(N):
	A = INT()
	a.append([LIST() for _ in range(A)])

maxv = 0
for i in range(2**N):
	s = "{:0" + str(3) + "b}"
	F = [int(i) for i in s.format(i)]
	flag = 0
	for j in range(N):
		if F[j] == 1:
			for k in range(len(a[j])):
				if a[j][k][1] == 1:
				 	if F[a[j][k][0] - 1]*a[j][k][1] == 0:
				 		flag = 1
					 	break
				else:
					if F[a[j][k][0] - 1]*a[j][k][1] == 0:
						flag = 1
						break

	if flag == 1:
		continue

	wa = sum(F)
	if maxv < wa:
		maxv = wa

print(maxv)

Submission status: Runtime Error

Solution code:
from itertools import product

N = int(input())
c = product(range(2), repeat=N)
d = [[] for _ in range(N)]

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


ans = 0
for l in c:
    o = [None]*N
    is_conflict = False
    for i, j in enumerate(l):
        if j==0:continue
        for x, y in d[i]:
            if (o[x-1]!=None and o[x-1]!=y) or l[x-1]!=y:
                is_conflict = True
                break
            o[x-1] = y
        if is_conflict == True:
            break
    else:
        ans = mas(ans, sum(l))

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
s = np.full((N, N), -1)
max_num = 0

for i in range(N):                                                                                                                                                                                          
    a = int(input())                                                                                                                                                                                        
    s[i][i] = 1                                                                                                                                                                                             
    for j in range(a):                                                                                                                                                                                      
        x, y = (int(z) for z in input().split())                                                                                                                                                            
        s[i][x-1] = y                                                                                                                                                                                       


def honest_counter(arry, num, limit, hnum):                                                                                                                                                                 
    global max_num                                                                                                                                                                                          
    if num == 0:                                                                                                                                                                                            
        ary = s[:, num]                                                                                                                                                                                     
        honest_num = np.sum(ary != 0)                                                                                                                                                                       
        honest_index = list(zip(*np.where(ary != 0)))                                                                                                                                                       
        unkind_index = list(zip(*np.where(ary != 1)))                                                                                                                                                       
                                                                                                                                                                                                            
    else:                                                                                                                                                                                                   
        honest_num = np.sum(arry != 0)                                                                                                                                                                      
        honest_index = list(zip(*np.where(arry != 0)))                                                                                                                                                      
        unkind_index = list(zip(*np.where(arry != 1)))                                                                                                                                                      
                                                                                                                                                                                                            
        if num == limit-1:                                                                                                                                                                                  
            if hnum > max_num:                                                                                                                                                                              
                max_num = hnum                                                                                                                                                                              
            return                                                                                                                                                                                          
                                                                                                                                                                                                            
        if honest_num == 1:                                                                                                                                                                                 
            return                                                                                                                                                                                          
                                                                                                                                                                                                            
    honest_index = list(map(lambda x:x[0], honest_index))                                                                                                                                                   
    unkind_index = list(map(lambda x:x[0], unkind_index))                                                                                                                                                   
                                                                                                                                                                                                            
    honest_counter(s[honest_index, num+1], num+1, limit, hnum+1)                                                                                                                                            
    honest_counter(s[unkind_index, num+1], num+1, limit, hnum)                                                                                                                                              

honest_counter(s, 0, N, 0)
print(max_num)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
s = np.full((N, N), -1)
max_num = 0

for i in range(N):                                                                                                                                                                                          
    a = int(input())                                                                                                                                                                                        
    s[i][i] = 1                                                                                                                                                                                             
    for j in range(a):                                                                                                                                                                                      
        x, y = (int(z) for z in input().split())                                                                                                                                                            
        s[i][x-1] = y                                                                                                                                                                                       

print(s)

def honest_counter(arry, num, limit, hnum):                                                                                                                                                                 
    global max_num                                                                                                                                                                                          
    if num == 0:                                                                                                                                                                                            
        ary = s[:, num]                                                                                                                                                                                     
        honest_num = np.sum(ary != 0)                                                                                                                                                                       
        honest_index = list(zip(*np.where(ary != 0)))                                                                                                                                                       
        unkind_index = list(zip(*np.where(ary != 1)))                                                                                                                                                       
                                                                                                                                                                                                            
    else:                                                                                                                                                                                                   
        honest_num = np.sum(arry != 0)                                                                                                                                                                      
        honest_index = list(zip(*np.where(arry != 0)))                                                                                                                                                      
        unkind_index = list(zip(*np.where(arry != 1)))                                                                                                                                                      
                                                                                                                                                                                                            
        if num == limit-1:                                                                                                                                                                                  
            if hnum > max_num:                                                                                                                                                                              
                max_num = hnum                                                                                                                                                                              
            return                                                                                                                                                                                          
                                                                                                                                                                                                            
        if honest_num == 1:                                                                                                                                                                                 
            return                                                                                                                                                                                     
                                                                                                                                                                                                            
    honest_index = list(map(lambda x:x[0], honest_index))                                                                                                                                                   
    unkind_index = list(map(lambda x:x[0], unkind_index))                                                                                                                                                   
                                                                                                                                                                                                            
    honest_counter(s[honest_index, num+1], num+1, limit, hnum+1)                                                                                                                                            
    honest_counter(s[unkind_index, num+1], num+1, limit, hnum)                                                                                                                                              

honest_counter(s, 0, N, 0)
print(max_num)