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:
from itertools import product
N=int(input())
data=[]
for i in range(N):
    for j in range(int(input())):
        x,y=map(int,input().split())
        data.append((i,x-1,y))
#print(data)

ans=0
for i in product([1,0],repeat=N):
    #print(i)
    s=True
    for k in data:
        if i[k[0]]==1 and i[k[1]]!=k[2]:
            s=False
            break
    if s:
        ans=max(ans,sum(i))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import*
I = input
n = int(I())
c = 0;z = []
for i in range(n):
    for j in range(int(I())):
        z += [[i] + list(map(int, I().split()))]
for j in product([0,1], repeat=n):
    if all(j[i] == 0 or j[x-1] - y == 0 for i, x, y in z):
        c = max(c, sum(j))
print(c)

Submission status: Accepted

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

for i in range(1, n+1):
  comment = []
  for _ in range(int(input())):
    comment.append(list(map(int, input().split())))
  comments.append(comment)
  
check_lists = []
ans = 0

for j in range(2**n):
  check_list = []
  index_list = []
  for k in range(n):
    if j & 1<<k:
      index_list.append(k)
      for comment_i in comments[k]:
        check_list.append(comment_i)
  
  case_result = True
  
  for check_list_i in check_list:
    ind, flg = check_list_i
    
    if ind-1 in index_list and flg==0:
      case_result = False
      break
    if ind-1 not in index_list and flg==1:
      case_result = False
      break
  
  if case_result:
    ans = max(ans, len(index_list))
    
print(ans)

Submission status: Accepted

Solution code:
def main():
    # 入力
    n = int(input())

    boolls = [[]]
    for i in range(n):
        tmpls = []
        for x in boolls:
            y = x.copy()
            x.append(True)
            y.append(False)
            tmpls.append(x)
            tmpls.append(y)
        boolls = tmpls

    boolls.sort(key=lambda _: _.count(True), reverse=True)

    xyls = []
    for i in range(n):
        ai = int(input())
        tuples = []
        for j in range(ai):
            x, y = map(int, input().split())
            tuples.append((x, y == 1))
        xyls.append(tuples)

    tmpTrueCnt = n
    max_cnt = 0
    for boolx in boolls:
        truecnt = boolx.count(True)
        if truecnt == 0:
            break
        if max_cnt > truecnt:
            break

        if tmpTrueCnt > truecnt:
            tmpTrueCnt = truecnt

        ok = True
        for i in range(len(boolx)):
            tf = boolx[i]
            if tf:
                for message in xyls[i]:
                    if boolx[message[0] - 1] != message[1]:
                        ok = False
                        break
            if not ok:
                break
        if ok:
            max_cnt = tmpTrueCnt
            break

    print(max_cnt)


main()

Submission status: Accepted

Solution code:
n=int(input())
a=[]
xy=[]
for i in range(n):
  a.append(int(input()))
  xy.append([list(map(int,input().split())) for _ in range(a[-1])])

# bfs,dfs ?->try dfs
def dfs(seen_,i):#iの人が正直者だと仮定する。i=0,1,2,...,n-1
  seen=seen_.copy()
  seen[i]=1 # -1:未定、1:正直者、0:不親切
  todo=[]
  todo.append(i)
  while len(todo)>0:
    b=todo.pop()
    if seen[b]==1:
      l=xy[b]
      for li in l:
        if seen[li[0]-1]==-1:
          seen[li[0]-1]=li[1]
          if li[1]==1:
            todo.append(li[0]-1)
        elif seen[li[0]-1]!=li[1]:
          seen_[i]=0
          return seen_
  return seen

ans=0
for i in range(n):
  seen=[-1]*n
  seen[i]=1
  seen=dfs(seen,i)
  #print(i,seen)
  while seen.count(-1)>0:
    j=[k for k,v in enumerate(seen) if v==-1][0]
    seen=dfs(seen,j)
  ans=max(ans,seen.count(1))
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

# -1 no ans
# 1 syoziki
# 0 hu sinsetu

N = int(input())
ans = [[-1] * N for i in range(N)]


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


def is_ok(num):
    # -1 not decided
    # 1 syoziki
    # 0 husinsetu
    people = [-1] * N
    for i in range(N):
        # i is syoziki
        if((num >> i) & 1):
            if(people[i] == 0):
                return False
            people[i] = 1
            for j in range(N):
                if(ans[i][j] == 1):
                    if(people[j] == 0):
                        return False
                    people[j] = 1
                if(ans[i][j] == 0):
                    if(people[j] == 1):
                        return False
                    people[j] = 0
        else:
            if(people[i] == 1):
                return False
            people[i] = 0

    return True


def countBit(num):
    ori = num
    count = 0
    while(num > 0):
        if(num & 1):
            count += 1
        num = num >> 1
    return count


out = 0

for i in range(1 << N):
    if(is_ok(i)):
        out = max(out, countBit(i))

print(out)

Submission status: Accepted

Solution code:
n = int(input())
alist = []
xy = [[] for i in range(n)]
ans = 0
for i in range(n):
    xy[i] =  []
for i in range(n):
    alist.append(int(input()))
    for j in range(alist[i]):
        a,b=input().split()
        xy[i].append([int(a), int(b)])
g = [[] for i in range(2**n-1)]
for i in range(1,2**n):
    for j in range(n):
        if list(format(i,'0b').zfill(n))[j] == '1':
            g[i-1].append(xy[j])
def lie(xy,p):
    z = list(format(p,'0b').zfill(n)) 
    for i in range(len(xy)):
        for j in range(len(xy[i])):
            if str(xy[i][j][1]) == z[xy[i][j][0]-1]:
                continue
            else:
                return 'No'
                break
    return 'Yes'
for k in range(2**n-1):
    if lie(g[k],k+1) == 'Yes':
        ans = max(ans,list(str(format(k+1,'0b'))).count('1'))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a,x = [],[]
for i in range(n):
    a.append(int(input()))
    xy=[list(map(int,input().split())) for _ in range(a[i])]
    x.append(xy)
ans = 0
for i in range(2**n):
    cnt = 0
    for j in range(n):
        if i&(1<<j):
            for k,l in x[j]:
                if (i>>(k-1))&1!=l:
                    cnt=1
                    break
    if cnt==0:
        ans = max(ans,bin(i).count("1"))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())
tes = [[] for i in range(N)]
for i in range(N):
    A = int(readline())
    for j in range(A):
        x,y = map(int,readline().rstrip().split())
        tes[i].append((x-1,y))

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

Submission status: Accepted

Solution code:
n = int(input())

def popcount(x):
    return bin(x).count('1')

g = [[-1 for j in range(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 -= 1
        g[i][x] = y

ans = 0
for i in range(1 << n):
    d = [0 for _ in range(n)]
    for j in range(n):
        if i >> j & 1:
            d[j] = 1
    ok = True
    for j in range(n):
        if d[j]:
            for k in range(n):
                if g[j][k] == -1:
                    continue
                if g[j][k] != d[k]:
                    ok = False
    if ok:
        ans = max(ans, popcount(i))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())
tes = [[-1]*N for i in range(N)]
for i in range(N):
    A = int(readline())
    for j in range(A):
        x,y = map(int,readline().rstrip().split())
        tes[i][x-1] = y

cnt = 0
for i in range(2**N):
    hon = [0]*N
    for j in range(N):
        if (i>>j)&1:
            hon[j] = 1
    flag = True
    for j in range(N):
        if not flag:
            break
        if hon[j]:
            for k in range(N):
                if tes[j][k] == -1:
                    continue
                if tes[j][k] != hon[k]:
                    flag = False
                    break
            
    if flag:
        cnt = max(cnt,hon.count(1))
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())
tes = [[-1]*N for i in range(N)]
for i in range(N):
    A = int(readline())
    for j in range(A):
        x,y = map(int,readline().rstrip().split())
        tes[i][x-1] = y

cnt = 0
for i in range(2**N):
    hon = [0]*N
    for j in range(N):
        if (i>>j)&1:
            hon[j] = 1
    flag = True
    for j in range(N):
        if hon[j]:
            for k in range(N):
                if tes[j][k] == -1:
                    continue
                if tes[j][k] != hon[k]:
                    flag = False
                    break
            if not flag:
                break
    if flag:
        cnt = max(cnt,hon.count(1))
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())
tes = [[-1]*N for i in range(N)]
for i in range(N):
    A = int(readline())
    for j in range(A):
        x,y = map(int,readline().rstrip().split())
        tes[i][x-1] = y

cnt = 0
for i in range(2**N):
    hon = [0]*N
    for j in range(N):
        if (i>>j)&1:
            hon[j] = 1
    flag = True
    for j in range(N):
        if hon[j]:
            for k in range(N):
                if tes[j][k] == -1:
                    continue
                if tes[j][k] != hon[k]:
                    flag = False
                    break
        if not flag:
            break
    if flag:
        cnt = max(cnt,hon.count(1))
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())
tes = [[-1]*N for i in range(N)]
for i in range(N):
    A = int(readline())
    for j in range(A):
        x,y = map(int,readline().rstrip().split())
        tes[i][x-1] = y #ここまでが入力

cnt = 0
for i in range(2**N):
    hon = [0]*N
    for j in range(N):
        if (i>>j)&1:
            hon[j] = 1 #全状態2**N通りを作っておく
    flag = True
    for j in range(N):
        if hon[j]:      #hon=1ならtesとの整合性を比較
            for k in range(N):
                if tes[j][k] == -1:
                    continue    #証言されていない部分は飛ばす
                if tes[j][k] != hon[k]:
                    flag = False
    if flag:
        cnt = max(cnt,hon.count(1))
print(cnt)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
     
    testimony = [[] for _ in range(N)]
     
    for i in range(N):
        num = int(input())
        for j in range(num):
            person, state = map(int, input().split())
            testimony[i].append([person-1, state])
            
    honest = 0
    for i in range(1, 2**N):
        flag = 0
        for j in range(N):
            if (i>>j)&1 == 1: # j番目は正直と仮定
                for x,y in testimony[j]:
                    if (i>>x)&1 != y: # j番目は正直だが矛盾を発見
                        flag = 1
                        break
        if flag == 0:  # 矛盾がある場合はflag == 1になる
            honest = max(honest, bin(i)[2:].count('1'))  # 1の数をカウントし最大となるものを選択
    print(honest)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
people = []
shogens = [[]for i in range(n)]
def check():
    for i in range(n):
        if i not in people:continue
        for shogen in shogens[i]:
            person = shogen[0]
            honest = shogen[1]
            if honest and person not in people:return False
            if (not honest) and person in people:return False
    return True
        
            
            
            
        
for i in range(n):
    a = int(input())
    for j in range(a):
        p,q = map(int,input().split())
        p -= 1
        shogens[i].append((p,q))
def dfs(d,people):
    if d == n:
        
        if check():
            
            return len(people)
        else:
            return 0
    res = dfs(d+1,people)
    people.append(d)
    res = max(res,dfs(d+1,people))
    people.pop()
    return res
print(dfs(0,people))

Submission status: Accepted

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

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

ans = 0
fm = "0"+str(n)+"b"
for i in range(2**n):
    flag = True
    s = str(format(i,fm))
    for j in say:
        if s[j[0]] == "1" and int(s[j[1]]) + j[2] == 1:
            flag = False
            break
    if flag and ans < s.count("1"):
        ans = s.count("1")

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
honest = [[] for _ in range(N)]
unkind = [[] for _ in range(N)]
MAX = 0
for i in range(0,N):
    A = int(input())
    for _ in range(A):
        x, y =map(int,input().split(' '))
        if y == 0:
            unkind[i].append(x-1)
        else:
            honest[i].append(x-1)

for i in range(2**N):
    flg = 1
    for j in range(N):
        if ((i>>j) & 1):
            bool1 = all([(i>>k) & 1 for k in honest[j]])
            bool2 = all([~(i>>k) & 1 for k in unkind[j]])
            if not all([(i>>k) & 1 for k in honest[j]]) or not all([~(i>>k) & 1 for k in unkind[j]]):
                flg =0

    if flg:
        cnt = 0
        num = i
        while num:
            num &= num -1
            cnt += 1
        MAX = max(cnt,MAX) 

print(MAX)

Submission status: Accepted

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

N = int(input())
testimony = [[None for _ in range(N)] for _ in range(N)]
person = [None] * N

for i in range(N):
    person[i] = int(input())
    for _ in range(person[i]):
        j, good_or_bad = map(int, input().split())
        j -= 1
        testimony[i][j] = good_or_bad

#ここまでが入力

ans = 0

for i in range(1, 1<<N):
    which_person = [None] * N
    for j in range(N):
        which_person[j] = i>>j & 1
        #print(which_person[j])
    ok = True
    for j in range(N):
        if which_person[j]:
            for k in range(N):
                if testimony[j][k] == None:
                    continue
                if testimony[j][k] != which_person[k]:
                    ok = False
    if ok:
        ans = max(ans, which_person.count(1))
print(ans)

Submission status: Accepted

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

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

ans=0

for i in range(2**n):
    flag=0
    cnt=0
    for j in range(n):
        if((i>>j)&1)==1 and flag==0:#正直者の言うことは矛盾が生じていない場合調べる
            for k in range(len(word[j])):
                if ((i>>word[j][k][0]-1)&1) != word[j][k][1]:
                    flag=1#正直者が嘘を言う矛盾が生じた
                    break
    
    if flag==0:
        cnt=bin(i).count("1")
        ans=max(ans, cnt)

print(ans)

Submission status: Accepted

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

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

ans=0

for i in range(2**n):
    flag=0
    cnt=0
    for j in range(n):
        if((i>>j)&1)==1 and flag==0:
            for k in range(len(word[j])):
                if ((i>>word[j][k][0]-1)&1) != word[j][k][1]:
                    flag=1
                    break
    
    if flag==0:
        cnt=bin(i).count("1")
        ans=max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
# 人数
n = int(input())
# 人数分繰り返す
# 証言の個数を格納するリスト
a = []
# 証言を格納するリスト
xy = []
for i in range(n):
    # 証言の個数
    a_n = int(input())
    # 証言の個数分繰り返す
    xy_n = []
    for i in range(a_n):
        xy_n.append(list(map(int, input().split())))
    a.append(a_n)
    xy.append(xy_n)

def judge(bit):
    # こっちの方が直感的だが...
    # bit = bin(bit).replace('0b', '')
    # for i in bit:

    # bit....n人の証言を検証する
    for i in range(n):
        # 該当ビットが0なら無視
        if not(bit & (1 << i)):
            continue
        # 証言を検証
        for j in xy[i]:
            # その人を正直と言っているが、実際嘘つきだったらだめ
            # 人物番号とbitのズレは解消すること！
            if j[1] == 1 and not(bit & (1 << (j[0]-1))):
                return False

            # 不親切なのに実際は親切
            if j[1] == 0 and (bit & (1 << (j[0]-1))):
                return False

    return True

max_person = 0
# 2**N通りで考える
for bit in range(1 << n):
    if judge(bit):
        count = 0
        # bitに含まれる人数を数える
        for i in range(n):
            if bit & (1 << i):
                count += 1
        if max_person < count:
            max_person = count

print(max_person)

Submission status: Accepted

Solution code:
n = int(input())
l = [[] for _ in range(n)]
ans = 0

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

for i in range(2**n):
    judge = True
    for j in range(n):
        if judge == False:
            break
        if i & (1 << j): #証言者が正直者設定なら進む。
            for x, y in l[j]:
                if y == 0 and i & 1 << (x - 1): #証言:不親切 設定:親切
                    judge = False
                if y == 1 and i & 1 << (x - 1) == 0: #証言:正直、設定:不親切
                    judge = False
    if judge == True:
        cnt = bin(i).count("1")
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = [[] for _ in range(n)]
ans = 0

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

for i in range(2**n):
    judge = True
    for j in range(n):
        if i & (1 << j): #証言者が正直者設定なら進む。
            for x, y in l[j]:
                if y == 0 and i & 1 << (x - 1): #証言:不親切 設定:親切
                    judge = False
                if y == 1 and i & 1 << (x - 1) == 0: #証言:正直、設定:不親切
                    judge = False
    if judge == True:
        cnt = bin(i).count("1")
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

a = []

evidences = []
for i in range(n):
    ls = []
    x = int(input())
    a.append(x)
    for j in range(x):
        l = [int(_) for _ in input().split(' ')]
        ls.append(l)
    evidences.append(ls)

patterns = []
for i in range(2**n):
    pattern = [0] * n
    for j in range(n):
        if (i >> j & 1):
            pattern[j] = 1
    patterns.append(pattern)

honest = 0
for pattern in patterns:
    contradict = False
    for i in range(n):
        for evidence in evidences[i]:
            if(pattern[i] == 1):
                if (pattern[evidence[0]-1] != evidence[1]):
                    contradict = True
    if (contradict == False):
        honest = max(honest, pattern.count(1))

print(honest)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n = int(input())
    info = []
    for _ in range(n):
        a = int(input())
        tmp = []
        for __ in range(a):
            tmp.append(list(map(int, input().split())))
        info.append(tmp)
    
    mask = 0
    honest = [0] * n
    ans = 0
    while mask < (1 << n):
        part = 0
        is_ok = True
        for i in range(n):
            if 1  & mask >> i  == 1:
                 honest[i] = 1
                 part += 1
            else:
                honest[i] = 0

        for i in range(n):
            if honest[i] == 1:
                for w in info[i]:
                    if honest[w[0] - 1] != w[1]:
                        is_ok = False
        
        if is_ok:
            if part > ans:
                ans = part
        mask += 1
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=0

g=[[-1 for i in range(n)] for j in range(n)]
for i in range(n):
  a=int(input())
  for j in range(a):
    x,y=map(int,input().split())
    g[i][x-1]=y

for i in range(2**n):# iは正直な人間の数
  ok=True
  for j in range(n):
    if (i>>j)&1: #iのjビット目が1のなのか確認
      for k in range(n):
        if g[j][k]==-1: # 証言がなければパス
          continue
        if (i>>k)&1!=g[j][k]: # 証言があればあっているか確認
          ok=False
  if ok:
    d=i
    t=str(bin(d)).count('1') #立っている1の個数
    ans=max(t,ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    d = defaultdict(list)
    for i in range(N):
        n = int(input())
        for _ in range(n):
            d[i].append(list(map(int, input().split())))
    max_trust_num = 0

    # check all possible combinations of Honest or Unkind.
    for i in range(2**N):
        trust = True

        # assign Honest or Unnkind to each person.
        # if person i is Honest, trust_combs[i] = 1
        # else, trust_combs[i] = 0
        trust_combs = []
        for j in range(N):
            if (i >> j) & 1:
                trust_combs.append(1)
            else:
                trust_combs.append(0)
  
        # check if the combination of Honest or
        # Unkind contradicts the given statements.
        for k in range(len(trust_combs)):
            if trust_combs[k] == 1:
                for l in d[k]:
                    if not l[1] == trust_combs[l[0]-1]:
                        trust = False
        if trust:
            max_trust_num = max(max_trust_num, sum(trust_combs))

    print(max_trust_num)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A = []
for i in range(N):
	a = []
	for j in range(ri()):
		x, y = rl()
		a.append((x-1, y))
	A.append(a)

def check(A, b):
	for i, a in enumerate(A):
		for x, y in a:
			if b[i] == 1:
				if b[x] != y:
					return False
	return True

import itertools
ans = 0
for b in itertools.product([0,1], repeat=N):
	if check(A, b):
		ans = max(ans, sum(b))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n = int(input())
tells = [[] for _ in range(n)]
for i in range(n):
    for j in range(int(input())):
        tells[i].append(list(map(int, input().split())))
for i in product(['1', '0'], repeat=n):
    a = list(map(int, i))
    flag = True
    for j in range(n):
        for k in tells[j]:
            if a[j] and a[k[0]-1] != k[1]:
                flag = False
                break
    if flag:
        print(sum(a))
        break

Submission status: Accepted

Solution code:
N = int(input())
li = []
for i in range(N):
    A = int(input())
    li.append([[int(j) for j in input().split()] for k in range(A)])

ans = 0

for i in range(1 << N):
    consistent = True  # 全ての証言と矛盾がなければTrue
    honests = 0  # 正直者の人数
    for j in range(N):  # j番目の人の証言をチェックする
        if not consistent:
            break
        claims = li[j]  # j番目の人の証言リスト
        if (i >> j) & 1 == 1:
            # i is honest
            honests += 1
            for claim in claims:
                if (i >> (claim[0] - 1)) & 1 != claim[1]:
                    # 正直者・嘘つきの仮定と証言が一致しない
                    consistent = False
                    break
    if consistent:
        ans = max(ans, honests)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
X=[]*n

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

ans=0
for i in range(2**n):
	cnt=0
	for j in range(n):
		if (i>>j)&1:
			for k,l in X[j]:
				if not ((i>>(k-1))&1)==l:
					cnt=1
					break

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
X=[]*n
A=[]*n

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

ans=0
for i in range(2**n):
	cnt=0
	for j in range(n):
		if (i>>j)&1:
			for k,l in X[j]:
				if not ((i>>(k-1))&1)==l:
					cnt=1
					break

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
X=[]*n
A=[]*n

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

ans=0
for i in range(2**n):
	cnt=0
	for j in range(n):
		if (i>>j)&1:
			for k,l in X[j]:
				if not ((i>>(k-1))&1)==l:
					cnt=1

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
honest = []
unkind = []
for _ in range(n):
    a = int(input())
    ho = []
    un = []
    for _ in range(a):
        x, y = map(int, input().split())
        if y == 1:
            ho.append(x-1)
        else:
            un.append(x-1)
    honest.append(ho)
    unkind.append(un)

# 全探索
ans = []
for i in range(2 ** n):
    person = []
    for j in range(n):
        person.append(i % 2)
        i //= 2

    flag = False

    # honestを判定
    for j in range(n):
        if person[j] == 1:
            for k in honest[j]:
                if person[k] == 0:
                    flag = True
                    break
            if flag:
                break
    if flag:
        continue
    
    # unkindを判定
    for j in range(n):
        if person[j] == 1:
            for k in unkind[j]:
                if person[k] == 1:
                    flag = True
                    break
            if flag:
                break
    if flag:
        continue

    ans.append(sum(person))
print(max(ans))

Submission status: Accepted

Solution code:
N = int(input())

h = []

for i in range(N):
  m = int(input())
  g = []
  for j in range(m):
    a, b = map(int, input().split())
    g.append((a-1, b))
  h.append(g)
  
def judge(a, b):
  for i in range(N):
    if (b >> i) & 1:
      for j in a[i]:
        if ((b >> j[0]) & 1) != j[1]:
          return False
  return True
  
x = 0b0
ans = -1
for i in range(2**N):
  if judge(h, x):
    tmp = 0
    for i in range(N):
      if (x >> i) & 1:
        tmp += 1
    if tmp > ans:
      ans = tmp
  x += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

evidences = [[] for _ in range(N)]
for i in range(N): # i:人の番号
    A = int(input())
    for _ in range(A): #  x:人の番号, y:正直者か見破る番号
        x, y = map(int, input().split())
        evidences[i].append((x - 1, y))
        
# 全通り試す(最大は2**15だから問題ない)
result = 0
for i in range(1, 2 ** N): # iのビットは正直者と不親切な人の割合
    consistent = True# 全通り試して矛盾がなければtrue
    for j in range(N):# ビット演算で一人ずつ見ていく
        if (i >> j) & 1 == 0: # 選んだ一人が不親切なら
            continue
        for x, y in evidences[j]: # x:人の番号, y:正直者か見破る番号
            if (i >> x) & 1 != y: # xで一人を選んで,yの証言と一致してなかったら矛盾
                consistent = False
    if consistent:
        result = max(result, bin(i).count('1'))
print(result)

Submission status: Accepted

Solution code:
n = int(input())
testimony = []  # 各iの証言
 

# 例2 tstimony = [[(1, 1), (2, 0)], [(2, 1), (0, 0)], [(0, 1), (1, 0)]] 
for i in range(n):
    t = []
    for _ in range(int(input())):
        x, y = map(int, input().split())
        t.append((x - 1, y)) 
    testimony.append(t)

max_honest = 0  # 正直者の最大人数

# 例2 ishonest = [False, False, False],[True, False, False],[False, True, False],[True, True, False],[False, False, True],[True, False, True],[False, True, True],[True, True, True]
for i in range(1 << n):
    ishonest = [False] * n
    for j in range(n):
        if ((i >> j) & 1) == 1:
            ishonest[j] = True
    #print(ishonest)

    ok = True

    for k in range(n):
        # False（不親切な人）の証言は気にしない
        if ishonest[k] == False:
            continue
        
        # True（正直者）の証言はチェック
        for l in range(len(testimony[k])):
            person = testimony[k][l][0]
            true_false = testimony[k][l][1]
            
            # Trueのはずやのに証言が0(False)になっている場合はおかしい
            # Falseのはずやのに証言が1(True)になっている場合はおかしい
            if (ishonest[person] == True) and (true_false == 0) or (ishonest[person] == False) and (true_false == 1):
                ok = False

        if ok == False:
            break
        
    if ok == True:

        if ishonest.count(True) > max_honest:
            max_honest = ishonest.count(True)

print(max_honest)

Submission status: Accepted

Solution code:
n = int(input())
a = [0 for _ in range(n)]
xyies = [[] for _ in range(n)]
for i in range(n):
    aa = int(input())
    a[i] += aa
    xyies[i] = [list(map(int,input().split())) for _ in range(aa)]
ans = 0
for i in range(2**n):
    H_or_U = [0 for _ in range(n)]#インデックス番号の人間がHonestなら1、Unkindなら0をリストに記憶させます。
    for j in range(n):
        if (i >> j) & 1:
            H_or_U[j] += 1
    syougens = []
    for j in range(n):
        if H_or_U[j]:#j番の人間がもしも正直ならば
            syougen = xyies[j]
            for k in range(a[j]):
                if H_or_U[syougen[k][0]-1] == syougen[k][1]:#j番の人間のk番目のsyougenが正しい場合
                    syougens.append(True)
                else:
                    syougens.append(False)
    if all(syougens):
        ans = max(ans,sum(H_or_U))
print(ans)