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:
N = int(input())

shougen = [[]for i in range(0,N+1,1)]
A = [0]*(N+1)
for i in range(1,N+1,1):
    A[i] = int(input())
    for j in range(0,A[i],1):
        shougen[i].append(list(map(int,input().split())))

maxshoujiki =0
for i in range(0,pow(2,N),1):
    is_shoujiki = [0]*(N+1)
    for j in range(0,N,1):
        if((i>>j)&1):
            is_shoujiki[j+1]=1

    isBAD = False
    for j in range(1,N+1,1):
        if is_shoujiki[j] == 1:
            for k in range(0,A[j],1):
                if is_shoujiki[shougen[j][k][0]]!=shougen[j][k][1]:
                    isBAD = True
    if not isBAD:
        maxshoujiki = max(maxshoujiki,sum(is_shoujiki))

print(maxshoujiki)

Submission status: Accepted

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: Accepted

Solution code:
N = int(input())
ans = 0
xy = [[] for _ in range(N)]
for i in range(N):
  A = int(input())
  for j in range(A):
    x, y = map(int, input().split())
    xy[i].append([x-1, y])
for i in range(1<<N):
  flag = 1
  count = list()
  for j in range(N):
    if i>>j & 1:
      count.append(j)
  for k in count:
    for x, y in xy[k]:
      if(y == 1):
        if x not in count:
          flag = 0
      else:
        if x in count:
          flag = 0
  
  if(flag == 1):
    ans = max(ans, len(count))
print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
li = []
for _ in range(n):
    lee = int(input())
    tmp = []
    for i in range(lee):
        tmp.append(list(map(int,input().split())))
    li.append(tmp)
#li
# [[[2, 1], [3, 0]], [[3, 1], [1, 0]], [[1, 1], [2, 0]]]
kumi = list(itertools.product(range(2), repeat=n))
#print(kumi)
# [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0),
#  (1, 0, 1), (1, 1, 0), (1, 1, 1)]
ans_li = []
for kk in kumi:
    flag = True
    for i,k in enumerate(kk):
        if k == 1:
            target = li[i]
            for t in target:
                #print(t,'tuple')
                if kk[t[0]-1]!=t[1]:
                    flag = False
    if flag:
        ans_li.append(sum(kk))
if len(ans_li)==0:
    print(0)
else:
    print(max(ans_li))

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    b = format(i, 'b')
    b = str(b).rjust(n,'0')
    b = b[::-1]
    cou = 0
    p = 0
    for j in range(n):
        if p == 1:
            break
        if b[j] == "1":
            cou += 1
            for k,g in syo[j]:
                if int(b[k-1]) != g:
                    p = 1
                    break
    if p == 0:
        ans = max(ans,cou)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N=int(input())
A=[]
arr=[]
ans=0
li=list(itertools.product([0,1], repeat=N))

for n in range(N):
  a=int(input())
  A.append(a)
  arr.append([ list(map(int,input().split())) for  _ in range(a)])
  
for l in li:
  
  flg=0
  for n in range(N):
    if l[n]==1:
      for m in range(A[n]):
        if l[arr[n][m][0]-1]!=arr[n][m][1]:
          flg=1
          break
      if flg==1:
        break
  if flg==1:
    continue
  count=l.count(1) 
  ans=max(ans,count)
      
print(ans)

Submission status: Accepted

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

for n in range(N):
  a=int(input())
  A.append(a)
  arr.append([ list(map(int,input().split())) for  _ in range(a)])
  
for i in range(2**N):
  ord =[0]*N
  count=0
  flg=0
  
  for n in range(N):
    if (i >>n)&1:
      count +=1
      ord[n]=1
   
  for n in range(N):
    if ord[n]==1:
      for m in range(A[n]):
        if ord[arr[n][m][0]-1]!= arr[n][m][1]:
          flg=1
          break
   
  if flg==1:
    continue
  ans=max(ans,count)
        
      
      
print(ans)

Submission status: Accepted

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

ans = 0
for bit in range(1 << N):
  honest_cnt = 0
  flag = True
  for i in range(N):
    if (bit >> i) & 1 == 0:
      continue
    honest_cnt += 1
    for x, y in XY[i]:
      if (bit >> (x-1)) & 1 != y:
        flag = False
        break
  if flag:
    ans = max(ans, honest_cnt)
    
print(ans)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
talks = []
for i in range(N):
    temp = int(input())
    talks.append([list(map(int, input().split())) for _ in range(temp)])
bit = itertools.product([0, 1], repeat=N)
ans = 0
for b in bit:
    flag = True
    for i in range(N):
        if b[i] == 0:
            continue
        for talk in talks[i]:
            if b[talk[0]-1] != talk[1]:
                flag = False
                break
    if flag:
        ans = max(ans, (sum(b)))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
lia,lib,lic,lid = [],[],[],[]
count = 0
for i in range(n):
    lib.append(int(input()))
    for j in range(lib[i]):
        lid.append([int(s) for s in input().split()])
    lic.append(lid)
    lid = []
for i in range(2**n):
    b = "0"*(n-len(bin(i))+2)+bin(i)[2:]
    li = [int(b[s]) for s in range(n)]
    f = 1
    for j in range(n):
        for k in range(lib[j]):
            if li[j] == 1:
                if li[lic[j][k][0]-1] != lic[j][k][1]:
                    f = 0
    if f == 1:
        lia.append(li)
        count += 1
for i in range(count):
    lia[i] = sum(lia[i])
print(max(lia))

Submission status: Accepted

Solution code:

import itertools

N = int(input())

all_list = list(itertools.product([0,1], repeat=N))

xy_list =[]

for i in range(N):
    for j in range(int(input())):
        x, y = map(int, input().split())
        xy_list.append((i+1,x,y))

#print(xy_list)

num_ok = 0
for i in all_list:
    #どの人の証言なのか
    flag = True

    for j in xy_list:
        if i[j[0]-1] == 1:
            if i[j[1]-1] != j[2]:
                flag = False        
                break

    if flag == True:
        if num_ok < i.count(1):
            num_ok = i.count(1)


print(num_ok)

Submission status: Accepted

Solution code:
import itertools

N = int(input())

all_list = list(itertools.product([0,1], repeat=N))

xy_list =[]

for i in range(N):
    for j in range(int(input())):
        x, y = map(int, input().split())
        xy_list.append((i+1,x,y))

#print(xy_list)

num_ok = 0
for i in all_list:
    #どの人の証言なのか
    flag = True

    for j in xy_list:
        if i[j[0]-1] == 1:
            if i[j[1]-1] != j[2]:
                flag = False        
    if flag == True:
        if num_ok < i.count(1):
            num_ok = i.count(1)


print(num_ok)

Submission status: Accepted

Solution code:
from itertools import product
n=int(input())
li=[[] for _ in range(n)]
A=[]
for i in range(n):
    a=int(input())
    A.append(a)
    for _ in range(a):
        x,y=map(int,input().split())
        li[i].append([x,y])
ans=0
for p in product([0, 1], repeat = n):
    f = 0
    for i in range(n):
        if f==0:
            for j in range(A[i]):
                if p[i]==1 and li[i][j][1] == 0:
                    if p[li[i][j][0] - 1] == 1:
                        f += 1
                        break
                elif p[i]==1 and li[i][j][1] == 1:
                    if p[li[i][j][0] - 1] == 0:
                        f += 1
                        break
        else:
            break
    if f==0:
        ans=max(ans,p.count(1))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list()
xy = list()
flag = True
num = 0
output=0
for i in range(N):
  A.append(int(input()))
  xy.append([list(map(int,input().split())) for _ in range(A[i])])
  
for i in range(2**N):
  flag = True
  num = str(format(i, 'b').zfill(N))
  for j in range(N):
    if ((i>>j)&1) == 1:
      for k in range(len(xy[N-j-1])):
        if int(num[xy[N-1-j][k][0]-1]) !=  xy[N-1-j][k][1]:
          flag = False
          break
    if flag == False:
      break
  if flag == True and output <= str(bin(i)).count('1') :
    output = str(bin(i)).count('1')
print(output)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
testimony = []
for n in range(N):
    A = int(input())
    testimony.append([list(map(int,input().split())) for _ in range(A)])

ans = 0
for bit in itertools.product([0,1],repeat = N):
    for n in range(N):
        if bit[n]:
            for t in testimony[n]:
                if bit[t[0]-1] != t[1]:
                    break
            else:
                continue
            break
    else:
        ans = max(ans,sum(bit))
print(ans)

Submission status: Accepted

Solution code:
2
n = int(input())
a = [[] for _ in range(n)]
for i in range(n): # i人目
  num = int(input()) # i人目の証言の数
  for j in range(num):
    x,y = map(int,input().split())
    a[i].append([x,y])

#n = 3
#a = [[[2, 1]], [[1, 1]], [[2,0]]]

ans = 0
for candi in range(1,2**n): # 正直者・不明者の候補リスト candi

  ck = 1 # 必ず一人は正直者がいる

  for i in range(n): # i番目の人の証言

    if not candi >> i & 1:
      continue

    for x,y in a[i]: # x番目の人はyです
      if candi >> (x-1) & 1 != y :
        ck = 0
        break
  if ck:
    temp = format(candi,'b').count('1')
    ans = max(ans,temp)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
testimony = [[] for _ in range(N)]
ans = 0
for n in range(N):
    A = int(input())
    for _ in range(A):
        x,y = map(int,input().split())
        testimony[n].append([x-1,y]) # 人のナンバリングを0startにする
# print(testimony)
for bit in range(2**N):
#     print("bit",bit)
    honest_cnt = 0
    for j in range(N):
#         print("j",j)
        if (bit>>j) & 1:
            honest_cnt += 1
            for t in testimony[j]:
                if (bit>>t[0])&1 != t[1]:
#                     print("break")
                    break
            else:
#                 print("continue")
                continue
#             print("break")
            break
    else:
#         print("new_ans")
        ans = max(ans,honest_cnt)
print(ans)

Submission status: Accepted

Solution code:
import itertools 
n=int(input())
g=[[-1 for _ in range(15)] for _ in range(15)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        g[i][x-1]=y
ans=0

for i in range(2**n):
    honests = [0 for _ in range(n)]
    for j in range(n):
        if(i>>j)&1:
            honests[j]=1
    ok=True
    for j in range(n):
        if honests[j]:
            for k in range(n):
                if g[j][k]==-1: continue
                if g[j][k]!=honests[k]: ok=False
    if ok:
        ans=max(ans,honests.count(1))
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from itertools import product
def main():
    n=int(input())
    XY=[[] for _ in range(n)]
    for i in range(n):
        a=int(input())
        for j in range(a):
            x,y=map(int,input().split())
            XY[i].append((x-1,y))
    tf=list(product([1,0],repeat=n)) #i人目の正直か嘘か
    ans=0
    for tfx in tf:
        for i,x in enumerate(tfx):
            if x==1: #i番目が正直人なら
                for xxy in XY[i]:#i番目の証言を
                    if tfx[xxy[0]]!=xxy[1]:
                        break
                else:
                    continue
                break
        else:
            ans=max(ans,sum(1 if a==1 else 0 for a in tfx))
    print(ans)


        
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

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

li = list(product(range(2), repeat=n))[::-1]
for l in li:
    reps = []
    for i in range(n):
        if l[i]:
            reps.append((i + 1, 1))
            reps += xys[i]
        else:
            reps.append((i + 1, 0))
    reps = list(set(reps))
    flg = True
    for i in range(1, n + 1):
        if (i, 1) in reps and (i, 0) in reps:
            flg = False
            break
    if flg:
        print(sum(l))
        exit()
print(0)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = []
xy = []
ans = 0
def hantei(i):
    global bi
    for j in range(a[i]):
        if int(bi[xy[i][j][0]]) != int(xy[i][j][1]):
            return False
    return True
    
for i in range(n):
    s = int(input())
    a.append(s)
    slist = []
    for i in range(s):
        x,y = map(int,input().split())
        x -= 1
        slist.append([x,y])
    xy.append(slist)

for i in range(2**n):
    bi = bin(i)[2:].zfill(n)
    
    for j in range(n):
        if bi[j] == "1":
            if hantei(j) == False:
                break
    else:
        #print(i,sum([int(a)for a in bi]))
        ans = max(ans, sum([int(a)for a in bi]))
print(ans)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
ans = 0
x = [[0 for i in range(15)] for j in range(n)]
y = [[0 for i in range(15)] for j in range(n)]
a = [0 for i in range(n)]
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        tmpx, tmpy = map(int, input().split())
        x[i][j] = tmpx - 1
        y[i][j] = tmpy

person = [i for i in range(n)]
## i:正直と仮定する人の人数
for i in range(1,n + 1):
    ## j:i人正直と仮定したときの全ての組み合わせ
    for j in itertools.combinations(person,i):
        truth = [0 for i in range(n)]
        flag = True
        ##正直な人の処理 k:正直と仮定した人の番号
        for k in j:
            ##正直と仮定した人が他の正直者によって：嘘つきと言われていたら矛盾
            if truth[k] == -1:
                flag = False
                break
            ##k番目の人は正直とする
            truth[k] = 1
            ##正直な人の証言を信用 l:番号kのl番目の情報
            for l in range(a[k]):
                ##嘘つきの情報があれば
                if y[k][l] == 0:
                    ##すでに正直者と決まっていたら矛盾
                    if truth[x[k][l]] == 1 or x[k][l] in j:
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = -1
                ##正直者の情報があれば
                else:
                    if truth[x[k][l]] == -1 or not (x[k][l] in j): 
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = 1
            ##矛盾が生じたら
            if not flag: break
        """
        ##l:嘘つきと仮定した人の番号
        for k in list(set(person) - set(j)):
            ##嘘つきと仮定した人が正直と言われていたら矛盾
            if truth[k] == 1:
                flag = False
                break
            ##k番目の人は嘘つきとする
            truth[k] = -1
            ##嘘つきの証言は嘘 l:番号kのl番目の情報
            for l in range(a[k]):
                ##嘘つきの情報があれば
                if y[k][l] == 0:
                    ##すでに嘘つきと決まっていたら矛盾
                    if truth[x[k][l]] == -1 or x[k][l] in list(set(person) - set(j)):
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = 1
                ##正直者の情報があれば
                else:
                    if truth[x[k][l]] == 1 or not (x[k][l] in list(set(person) - set(j))):
                        flag = False
                        break
                    else:
                        truth[x[k][l]] = -1
            ##矛盾が生じたら
            if not flag: break
        """
        if not flag:continue
        ##矛盾が一切無ければ
        ans = i
        break

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = []
ans = 0
for i in range(n):
    x =int(input())
    lists = [list(map(int,input().split())) for j in range(x)]
    A.append(lists)

for i in range(2**n):
    honesty = [0]*n
    for j in range(n):
        if (i>>j) & 1:
            honesty[j] = 1
    true = 1
    for j in range(n):
        if honesty[j] == 1:
            for k in range(len(A[j])):
                x,y = A[j][k]
                if not honesty[x-1] == y:
                    true = 0
                    break
    if true == 1:
        ans = max(ans,sum(honesty))
print(ans)

Submission status: Accepted

Solution code:
N = int(input()) #人数

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

ans = 0
import itertools
for i in itertools.product([1,0], repeat=N):
    tmp = sum(list(i))
    for j in state:
        if i[j[0]] == 1 and i[j[1]] != j[2]:
            tmp = 0
            break
    ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0

for bit in list(itertools.product([0, 1], repeat=N)):
    ok = True
    for i in range(N):
        if bit[i]:
            for x, y in T[i]:
                if bit[x] != y:
                    ok = False
    if ok:
        ans = max(ans, sum(bit))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
shougen=[[-1]*(n+1) for _ in range(n+2)]
for i in range(1,n+1):
  a = int(input())
  for j in range(a):
    x,y = map(int, input().split())
    shougen[i][x]=y
 
ans=0
for i in range(2**n):
  f=True
  for j in range(n):
    if i>>j & 1:
      for k,s in enumerate(shougen[j+1][1:],start=0):
        if s == 1 and not i>>k & 1:
          f=False
        if s == 0 and i>>k & 1:
          f=False
  else:
    if f:
      ans=max(ans, str(bin(i)).count("1"))
 
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

def main():
    ans = 0
    for i in range(1<<N):
        ans = max(ans, detect(i))
    print(ans)

def detect(i):
    ONT = 0
    for j in range(N):
        if  not (i & 1<<j):
            continue
        ONT += 1
        for x, y in STATE[j]:

            if (y==0) ^ (i>>(x-1) & 1) == 0:
                return 0
    return ONT

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
stdin = open(0).read().rstrip().split('\n')
N = int(stdin[0])
A = []
i=1
j=-1
while i< len(stdin):
    l=[]
    index=int(stdin[i])
    l.append(index)
    i+=1
    for _ in range(index):
        l.append(list(map(int,stdin[i].split())))
        i+=1
    A.append(l)
ans = 0
for bit in range(2**N):
    s = format(bit,'b').zfill(N)
    flag = True
    for j in range(len(A)):
        if s[j] == '1':
            num = A[j][0]
            for k in range(1,num+1):
                if A[j][k][1]!=int(s[A[j][k][0]-1]):
                    flag = False
                    break
        if not flag:
            break
    if flag:
        ans = max(ans,s.count('1'))
print(ans)

Submission status: Accepted

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

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

def main():
    ans = 0
    for i in range(1<<N):
        ans = max(ans, detect(i))
    print(ans)

def detect(i):
    ONT = 0
    for j in range(N):
        if  not (i & 1<<j):
            continue
        ONT += 1
        for x, y in STATE[j]:
            # if (i & 1<<(x-1)) == (y>0):
            #     print('good')
            #     continue
            # else:
            #     return 0
            # if ((i & (1 << (x-1)))>0) != (y>0):
            if (y == 1) and (i&(1<<(x-1))) == 0:
                return 0
            # if (y == 0) and (i&(1<<(x-1))) > 0:
            if (y==0) and (i>>(x-1) & 1) == 1:
                return 0
    return ONT

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for _ in range(N):
  a = int(input())
  tmp = [list(map(int, input().split())) for _ in range(a)]
  xy += [tmp]

ans = 0
for i in range(2**N):
  d = {i:-1 for i in range(1, N+1)}
  flag = True
  tmp = 0
  #print("---i---", i)
  for j in range(N):
    #print(d, j)
    if (i>>j)&1: # 正直
      tmp += 1
      if d[j+1] == 0:
        flag = False
        break
      d[j+1] = 1
      for x, y in xy[j]:
        if d[x] == -1:
          d[x] = y
        else:
          if d[x] != y:
            flag = False
            break
    else:
      if d[j+1] == 1:
        flag = False
        break
      d[j+1] = 0
    
  if flag:
    ans = max(tmp, ans)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
L=[]
for i in range(n):
	a = int(input())
	for j in range(a):
		x,y=map(int, input().split())
		L.append([i,x-1,y])
ans=0
import itertools
for i in itertools.product([1,0], repeat=n):
	s = sum(list(i))
	for l in L:
		if i[l[0]]==1 and i[l[1]]!=l[2]:
			s=0
			break
	ans= max(ans,s)
print(ans)

Submission status: Accepted

Solution code:
#C

N = int(input())
P = []
ans = 0

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

#全探索
for i in range(2**N):
  Flag = True
  for j in range(N): #N人の〇×を順に見る
    
    if (i >> j) & 1 == 1: #j桁目が1、つまりj番目が正直者→チェック
      for YN in P[j]:
        if (i >> YN[0]) & 1 != YN[1]:
          Flag = False
          break

    if Flag:
      continue
    else:
      break

  if Flag:
    ans = max(ans, bin(i).count("1"))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
v=[]
f=True
c=res=0

for i in range(n):
    a=int(input())
    xy=tuple(tuple(map(int,input().split())) for _ in range(a))
    v.append(xy)
for i in range(2**n):
    f=True
    for j in range(n):
        if not (i & (1<<j)):
            continue
        for xy in v[j]:
            x=xy[0]-1
            y=xy[1]
            if y==1 and (not(i & (1<<x))):
                f=False
            if y==0 and (i & (1<<x)):
                f=False
        if not f:
            break
    else:
        c=0
        for k in range(n):
            if (i & (1<<k)):
                c+=1
        res=max(res,c)
print(res)

Submission status: Accepted

Solution code:
n = int(input())
max_ = 2**n
a = []
for i in range(n):
  p = int(input())
  b = []
  for j in range(p):
    x, y = map(int, input().split())
    b.append((x-1,y))
  a.append(b)
c_max = 0
for i in range(max_):
  mujun = False
  bi = format(i, '0'+str(n)+'b')
  c1 = bi.count("1")
  
  for j in range(len(bi)):
    if bi[j] == "1":
      for syougen in a[j]:
        if bi[syougen[0]] != str(syougen[1]):
          mujun = True
  if not mujun:
    if c1 > c_max:
      c_max = c1
print(c_max)

Submission status: Accepted

Solution code:
n = int(input())
L = [[]*n 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 = x-1
        L[i].append((x,y))
#print(L)
ans = 0
for i in range(1<<n):
    bit = [(i>>j)&1 for j in range(n)]
    #print(bit)
    flag = True
    for j in range(n):
        if bit[j]:
            for x,y in L[j]:
                if bit[x] != y:
                    flag = False
                    break
            if not flag:
                break
    if flag:
        ans = max(ans,sum(bit)) 
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
map_list = [[-1 for i in range(n)] for i in range(n)]

for i in range(n):
    m = int(input())
    for j in range(m):
        x,y = map(int,input().split())
        map_list[i][x-1]=y
ans=0
for i in range(2**n):
    honest = [0 for i in range(n)]
    for j in range(n):
        if (i>>j)&1:
            honest[j]=1
    flag=True
    for j in range(n):
        if honest[j]:
            for k in range(n):
                if map_list[j][k]==-1:continue
                if map_list[j][k]!=honest[k]:flag=False
    if flag:
        ans=max(ans,honest.count(1))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import itertools

n = int(input())

xy = []
for i in range(n):
    a = int(input())
    xy.append([list(map(int, input().split())) for _ in range(a)])
ans = 0
for i in itertools.product([0, 1], repeat=n):
    honest_list = list(i)
    flag = 0
    for index in range(n):
        if i[index] == 0:
            continue
        xy_tmp = xy[index]
        # print(xy_tmp)
        for k in range(len(xy_tmp)):
            x, y = xy_tmp[k]

            if honest_list[x-1] != y:
                flag = 1
            # if honest_list[x-1] == -1:
            #     honest_list[x-1] = y
            # else:  # 0or1
            #     if honest_list[x-1] != y:
            #         flag = 1
            #         break
            #     else:
            #         continue

        # if flag == 1:
        #     break
    if flag != 1:
        ans = max(ans, sum(honest_list))

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N=int(input())
A=[0]*N
L=[0]*N                    #1なら正直者、0なら真偽不明
R=[ [] for _ in range(N)]    #証言内容
for i in range(N):
  A[i]=int(input())  #証言の個数
  for j in range(A[i]):
    a,b=map(int,input().split())
    R[i].append([a,b])    
#print(R)

pro=product([0,1],repeat=N)
maxi=0
for pat in pro:
  T=[[] for _ in range(N)]
  for i,man in enumerate(pat):
    if man==1:
      for c in R[i]:
        T[c[0]-1].append(c[1])
  #print(sum(pat),pat,T)
  check=True
  for j,test in enumerate(T):
    for num in test:
      if num!=pat[j]:
        check=False
  if check:
    maxi=max(maxi,sum(pat))
    
print(maxi)

Submission status: Accepted

Solution code:
N = int(input())
t = []
for _ in range(N):
    A = int(input())
    tt = []
    for _ in range(A):
        tt.append(list(map(int, input().split())))
    t.append(tt)
ans = 0
for b in range(1 << N):
    f = True
    c = 0
    for i, tt in enumerate(t):
        if b >> i & 1:
            c += 1
            for x, y in tt:
                if b >> (x - 1) & 1 != y:
                    f = False
                    break
    if f:
        ans = max(ans, c)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
t = []
for _ in range(N):
    A = int(input())
    tt = []
    for _ in range(A):
        tt.append(list(map(int, input().split())))
    t.append(tt)
ans = 0
for b in range(1 << N):
    f = True
    for i, tt in enumerate(t):
        for x, y in tt:
            if b & 1 << i:
                if (b & 1 << (x - 1)) >> (x - 1) != y:
                    f = False
                    break
    if f:
        ans = max(ans, bin(b).count('1'))

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())
a = []
for _ in range(n):
  a_i = int(input())
  t = []
  for _ in range(a_i):
    t.append(tuple(map(int,input().split())))
  a.append(t)

ans = 0
for case in product(range(2),repeat=n):
  frag = False
  for i in range(n):
    if case[i]==1:
      for x,y in a[i]:
        if case[x-1]!=y:
          frag = True
          break
    if frag:
      break
  if not frag:
    ans = max(ans,sum(case))
print(ans)

Submission status: Accepted

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

n = int(input())

from collections import defaultdict
d = defaultdict(list)

for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = [int(x) for x in input().split()]
        d[i].append((x - 1, y))
ans = 0
for k in range(2**n):
    res = 0
    j = bin(k)[2:].zfill(n)
    flag = 1
    for i in range(n):
        if j[i] == "0":
            continue
        for x, y in d[i]:
            if int(j[x]) != int(y):
                flag = 0
                break
        res += 1
    if flag:
        ans = max(ans, res)
print(ans)

Submission status: Accepted

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

for i in range(n):
    ai=int(input())
    axy.append([])
    for j in range(ai):
        axy[-1].append(list(map(int,input().split())))

ans=0
pat=2**n
#print(axy)
for p in range(pat):
    #i文字目は人iが正直者か日正直者か
    bin_p=list(map(int,bin(p)[2:].zfill(n)))

    flag=False
#    print(bin_p)
    for i in range(n):

        for axyi in axy[i]:
#            print(axyi)
            if(bin_p[i]==1 and bin_p[axyi[0]-1] != axyi[1]):
                flag=True
                break

#             if(bin_p[i]==0 and bin_p[axyi[0]-1] == axyi[1]):
#                 flag=True
#                 break


        if(flag):
            break
    else:
#        print(bin_p,flag)
        ans=max(ans,bin_p.count(1))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n=int(input())
    A=[0]*n
    st=[[] for _ in range(n)]
    for i in range(n):
        a=int(input())
        for j in range(a):
            x,y=map(int,input().split())
            st[i].append((x,y))

    
    # bit全探索    
    # https://qiita.com/gogotealove/items/11f9e83218926211083a#%E4%BE%8B%E9%A1%8C-1
    # 昇順での探索だよ
    ans=0
    for i in range(2 ** n):
        inconsistent=False
        cnt=0
        for j in range(n):  # このループが一番のポイント
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                cnt+=1
                for p in st[j]:
                    if p[1]==1 and not ((i >> (p[0]-1) & 1)):
                        inconsistent=True
                    elif p[1]==0 and not not ((i >> (p[0]-1) & 1)):
                        inconsistent=True
            else:
                continue
            

        if not inconsistent:
            ans=max(ans,cnt)
    print(ans)
    

    
resolve()