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:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, XYs):
    ans = 0
    for i in range(2 ** N):
        for j in range(N):
            if (i >> j) & 1:
                for x, y in XYs[j + 1]:
                    if ((i >> (x - 1)) & 1) ^ y:
                        break
                else:
                    continue
                break
        else:
            ans = max(ans, bin(i).count('1'))
    print(ans)


if __name__ == '__main__':
    N = int(input())
    XYs = [[] for _ in range(N + 1)]
    for i in range(N):
        Ai = int(input())
        for _ in range(Ai):
            XYs[i + 1].append([int(i) for i in input().split()])
    # N = 15
    # XYs = [[] for _ in range(N + 1)]
    # for i in range(N):
    #     for j in range(15):
    #         if i == j:
    #             continue
    #         XYs[i + 1].append([j + 1, 1])
    # print(N)
    # for i in range(len(XYs)):
    #     print(i, XYs[i])
    solve(N, XYs)

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())
al = []

for _ in range(n):
    curr_al = []
    a = int(input())
    for i in range(a):
        x,y = map(int, input().split())
        curr_al.append((x,y))
    al.append(curr_al)


pattern = 2
ite = product(range(pattern),repeat=n)
ans = 0
for it in ite:
    a_01_l = list(it)
    curr_ans = a_01_l.count(1)
    # print('-----')
    # print(a_01_l)
    for i, curr_it in enumerate(it):
        if curr_it == 1:
            check = True
            for a in al[i]:
                if a_01_l[a[0]-1] != a[1]:
                    check = False
            if not check:
                break
    else:
        # print('ok')
        ans = max(curr_ans,ans)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
state=[[] for _ in range(n)]
for _ in range(n):
    a=int(input())
    for i in range(a):
        x,y=map(int,input().split())
        state[_].append([x,y])
ans=0
for i in range(2**n):
    temp=[0]*n
    for j in range(n):
        if i&1: temp[j]=1
        i>>=1
    flag=1
    for k,s in enumerate(temp):
        if s==0: continue
        for st in state[k]:
            if temp[st[0]-1]!=st[1]:
                flag=0
                break
            if not flag: break
    if flag:
        cnt=temp.count(1)
        if cnt>ans: ans=cnt
print(ans)

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = []
xy = [[] for i in range(N)]
for i in range(N):
    A.append(I())
    for j in range(A[i]):
        x,y = LI()
        xy[i].append([x-1,y])

# 人は0-index
# 各人が正直者か不親切な人かで全探索、1…正直者、0…不親切な人

ans = 0
for i in range(2**N):
    B = [[] for _ in range(N)]
    a = 0  # 正直者の人数
    for j in range(N):
        if (i>>j) & 1:  # jが正直者
            B[j].append(1)
            a += 1
            for k in range(A[j]):
                B[xy[j][k][0]].append(xy[j][k][1])
        else:  # jが不親切な人
            B[j].append(0)
    if sum(len(set(B[j])) for j in range(N)) != N:  # この場合矛盾
        continue
    else:
        ans = max(ans,a)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import itertools
n = int(input())
a_li = []
x_li = []
y_li = []
for i in range(n):
  a = int(input())
  a_li.append(a)
  tmp_x = []
  tmp_y = []
  for j in range(a):
    x, y = list(map(int, input().split()))
    x -= 1
    tmp_x.append(x)
    tmp_y.append(y)
  x_li.append(tmp_x)
  y_li.append(tmp_y)
total_li = list(itertools.product([0, 1], repeat=n))
ans = 0
for each in total_li:
  flag = True
  for i, person in enumerate(each):
    if person == 1:
      per_li = x_li[i]
      hone_li = y_li[i]
      for pe, ho in zip(per_li, hone_li):
        if each[pe] != ho:
          flag = False

  if flag:
    ans = max(ans, sum(each))
print(ans)

Submission status: Accepted

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

def main():
    # 証言が矛盾していないかチェックする
    def check(bit):
        for i in range(n):
            if not bit & (1 << i):
                continue

            for human, is_honest in a[i]:
                if is_honest == 1 and (bit & (1 << human)):
                    continue
                elif is_honest == 0 and not (bit & (1 << human)):
                    continue
                else:
                    return False
        return True

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

    # 全パターン回す
    for bit in range((1 << n)):
        num = 0
        if check(bit):
            for k in range(n):
                if bit & (1 << k):
                    num += 1
            ans = max(ans, num)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

ans = 0
for i in range(2**n):
  ok = True
  for j in range(n):
    if (i>>j) & 1 == 0:continue
    for x,y in p[j]:
      if (i>>x)&1 != y:
        ok = False
        break
    if ok == False:
      break
  if ok:
    #print(i)
    cnt = len([j for j in range(n) if (i>>j)&1])
    ans = max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

X = list(range(1, N+1))

n = N
ans = 0
for bit in range(2**n):
    Pick = []
    for j in range(n):
        mask = 1 << j
        if bit & mask:
            Pick.append(X[j])
#    print()
#    print(Pick)
    flag = True
    for pick in Pick:
        for xy in A[pick]:
            x = xy[0]
            y = xy[1]
            if y == 1 and x in Pick:
                flag *= True
            elif y == 0 and not(x in Pick):
                flag *= True
            else:
                flag *= False
#            print(x, y, flag)
#        print(pick, flag)
    if flag == True:
        ans = max(ans, len(Pick))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
  b=int(input())
  c=[[] for _ in range(n)]
  for j in range(b):
    x,y=map(int,input().split())
    c[x-1]=y
  a.append(c)
ans=[]
for i in range(2**n):
  tr=bin(i)[2:].zfill(n)
  cnt=0
  for j in range(n):
    if tr[j]=='1':
      for k in range(n):
        if a[j][k]!=[] and a[j][k]!=int(tr[k]):
          break
      else:
        cnt+=1
  if sum(list(map(int,tr)))==cnt:ans.append(cnt)
print(max(ans))

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * n
x = [0] * n
y = [0] * n
for i in range(n):
    a[i] = int(input())
    t = [[int(j) for j in input().split()] for k in range(a[i])]
    x[i] = [j[0] for j in t]
    y[i] = [j[1] for j in t]

mx = 0
for bit in range(1<<n):
    flag = True
    tf = [0] * n
    for i in range(n):
        if bit & (1 << i): 
            tf[i] = 1
    for i in range(n):
        if tf[i] == 0:
            continue
        for j in range(a[i]):
            if tf[x[i][j]-1] != y[i][j]:
                flag = False
    if flag: mx = max(mx, bin(bit).count("1"))
print(mx)

Submission status: Accepted

Solution code:
def my_eval(ar,str):
    res = True
    n = len(str)
    # print(n)
    # print("start")
    for i in range(n):
        # print(i)

        if(ar[str[i][0]] == 1):
            # print(str[i][0])
            # print(str[i][1])
            # print(str[i][2])
            # print(ar[str[i][1]-1])
            # print(ar[str[i][1]-1] == str[i][2])
            # print(ar)
            # print()
            if(ar[str[i][1]] != str[i][2]):
                res = False
    # print("end")
    # print()
    return res

if __name__ == "__main__":

    # 全探索
    n = int(input())
    str = []
    for i in range(n):
        a = int(input())

        for j in range(a):
            x = list(map(int,input().split()))
            x.insert(0,i+1)
            str.append(x)
    ar = [0] * (n+1)
    res = 0
    # print(str)
    count = 0
    for i in range(2**n):
        count = 0
        for j  in range(n):
            if(i >> j & 1 == 1):
                ar[j+1] = 1
                count += 1
            else:
                ar[j+1] = 0
        # print(ar)
        if(my_eval(ar,str)):
            res = max(res,count)
    print(res)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    shougen = []
    for _ in range(N):
        A = int(input())
        shougen.append([list(map(int, input().split())) for _ in range(A)])
    
    ans = 0
    for i in range(2**N):
        state = [1]*N
        
        for j in range(N):
            if (i >> j) & 1:
                state[j] = 0
        
        flag = True
        for k in range(N):
            if not flag:
                break
            if state[k] == 1:
                for ele in shougen[k]:
                    if state[ele[0]-1] != ele[1]:
                        flag = False
                        break
                    
        if flag:
            ans = max(ans, sum(state))
    
    print(ans)
                
    
if __name__  == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for ptn in range(1<<N):
    conflict = False
    for i in range(N):
        if (ptn>>i) & 1:
            for x, y in xyss[i]:
                if (ptn>>x) & 1 != y:
                    conflict = True
                    break
        if conflict:
            break
    else:
        num1 = bin(ptn).count('1')
        if num1 > ans:
            ans = num1

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    xy = []
    for i in range(n):
        a = int(input())
        xy.append([tuple(map(int, input().split())) for _ in range(a)])

    c = 0
    for i in range(1 << n):
        popcnt = bin(i).count('1')
        if popcnt <= c:
            continue
        all_honest = True
        for j in range(n):
            if (1 << j) & i != 0:
                for x, y in xy[j]:
                    x -= 1  # 人の番号をひとつずらす
                    if ((1 << x) & i) >> x != y:
                        all_honest = False
                        break
            if not all_honest:
                break
        if all_honest:
            c = popcnt

    print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    xy = []
    for i in range(n):
        a = int(input())
        xy.append([tuple(map(int, input().split())) for _ in range(a)])

    c = 0
    for i in range(1 << n):
        popcnt = bin(i).count('1')
        if popcnt <= c:
            continue
        all_honest = True
        for j in range(n):
            if (1 << j) & i != 0:
                for x, y in xy[j]:
                    x -= 1  # 人の番号をひとつずらす
                    if ((1 << x) & i) >> x != y:
                        all_honest = False
                        break
            if not all_honest:
                break
        if all_honest:
            if popcnt > c:
                c = popcnt

    print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    xy = []
    for i in range(n):
        a = int(input())
        xy.append([tuple(map(int, input().split())) for _ in range(a)])

    c = 0
    for i in range(1 << n):
        all_honest = True
        for j in range(n):
            if (1 << j) & i != 0:
                for x, y in xy[j]:
                    x -= 1  # 人の番号をひとつずらす
                    if ((1 << x) & i) >> x != y:
                        all_honest = False
                        break
            if not all_honest:
                break
        if all_honest:
            popcnt = bin(i).count('1')
            if popcnt > c:
                c = popcnt

    print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
l=[]
ans=0
for i in range(a):
  s=ii()
  h=[list(mi()) for _ in range(s)]
  l.append(h)
for k in range(2**a):
  lst=[]
  for p in range(a):
    if k>>p & 1:
      lst.append(p)
  t=True
  for aa in lst:
    for m in l[aa]:
      if m[1]==0:
        if m[0]-1 in lst:
          t=False
          break
      else:
        if not m[0]-1 in lst:
          t=False
          break
  if t:
    ans=max(ans,len(lst))
print(ans)

Submission status: Accepted

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

N = int(readline())
A = [[] for _ in range(N)]

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


ans = 0
for i in range(2**N):
    pattern = [0] * N
    valid = True
    for j in range(N):
        if (i >> j) & 1:
            pattern[j] = 1

    # ビットが1になっている人の証言をみる
    for k in range(N):
        if pattern[k]:
            for x, y in A[k]:
                if pattern[x] != y:  # 矛盾があれば終了、このパターンはありえない。
                    valid = False
                    break
    if valid:
        ans = max(ans, sum(pattern))

print(ans)

Submission status: Accepted

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

N = int(readline())
A = [[] for _ in range(N)]

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


ans = 0
for i in range(2**N):
    good = [0] * N
    f = 1
    for j in range(N):
        if (i >> j) & 1:
            good[j] = 1

    for k in range(N):
        if good[k]:
            for x, y in A[k]:
                if good[x] != y:
                    f = 0
    if f:
        ans = max(ans, sum(good))

print(ans)

Submission status: Accepted

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

from itertools import product
N = int(input())
A = {}
for i in range(N):
    A[i] = []

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

ret = -1
for p in product([0,1], repeat=N):
    cnt = 0
    flag = True
    for i in range(N):
        if p[i] == 1:
            for XY in A[i]:
                if XY[1] != p[XY[0]]:
                    flag = False
    if flag:
        ret = max(sum(p), ret)


print(ret)

Submission status: Accepted

Solution code:
from collections import deque


def solve():
    N = int(input())
    XY= [[]]
    for _ in range(N):
        A = int(input())
        xylist = []
        for __ in range(A):
            x, y = map(int, input().split())
            xylist.append([x,y])
        XY.append(xylist)
        ans = 0
    for bit in range(2 ** N):
        honestset = set()
        unhonestset = set()
        for i in range(N):
            if ((bit >> i) & 1) == 1:
                honestset.add(i+1)
            else:
                unhonestset.add(i+1)

        before = 100
        before_un = 100
        while (before != len(honestset) or before_un != len(unhonestset)):
            before = len(honestset)
            before_un = len(unhonestset)
            tmp = list(honestset)
            for x in tmp:
                for xin, yin in XY[x]:
                    if yin == 1:
                        honestset.add(xin)
                    else:
                        unhonestset.add(xin)
        if len(honestset & unhonestset) == 0:
            ans = len(honestset) if ans < len(honestset) else ans

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())
A = []
shougen = []
for i in range(N):
    a = int(input())
    A.append(a)
    ls = []
    for j in range(a):
        ls.append([int(k) for k in input().split()])
    shougen.append(ls)
truth = [0, 1]
ans = 0
for x in product(truth, repeat=N):
    num = 0
    for i, y in enumerate(x):
        if y == 1:
            for z in shougen[i]: 
                if x[z[0]-1] != z[1]:
                    num += 1
    if num == 0:
        ans = max(ans, sum(x))
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())

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

def countB(b):
    ret = 0
    while b > 0:
        if b % 2 == 1:
            ret += 1
        b //= 2

    return ret

ans = 0
for i in range(2 ** N):
    hs = [-1] * N
    contradiction = False
    for j in range(N):
        if i & 1 << j > 0:
            for k in range(N):
                if people[j][k] == -1:
                    continue
                if hs[k] == -1:
                    hs[k] = people[j][k]
                else:
                    if hs[k] != people[j][k]:
                        contradiction = True
    if not contradiction:
        for j in range(N):
            if hs[j] == -1:
                continue
            if i & 1 << j > 0 and hs[j]:
                continue
            if i & 1 << j == 0 and not hs[j]:
                continue
            else:
                break
        else:
            ans = max(ans, countB(i))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

A = []
xy = []

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

ans = 0
p = [-1]*N

def dfs(i, p):
    global ans
    if i == N:
        ans = max(ans, sum(p))
    else:
        p_true = p.copy()
        if p_true[i] != 0:
            p_true[i] = 1
            ok = True
            for x, y in xy[i]:
                if y == p_true[x-1] or p_true[x-1] == -1:
                    p_true[x-1] = y
                else:
                    ok = False
            if ok:
                dfs(i+1, p_true)
        p_false = p.copy()
        if p_false[i] != 1:
            p_false[i] = 0
            dfs(i+1, p_false)

dfs(0, p)

print(ans)

Submission status: Accepted

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

ans = 0

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

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

combination([])
print(ans)

for i in range(2**N) :
    a = list(format(i,"b").zfill(N))
    for j in range(N) :
        if a[j] == "0" :
            data[j]

Submission status: Accepted

Solution code:
N = int(input())

XY = []
for _ in range(N):
    A = int(input())

    temp = []
    for _ in range(A):
        temp.append(list(map(int, input().split())))

    XY.append(temp)


max_honest = 0
for c in range(1 << N):
    check = [0] * N
    contradict = False

    cnt1 = 0
    while c != 0:
        if 1 & c:
            check[cnt1] = 1

        c >>= 1
        cnt1 += 1

    for i in range(N):
        if check[i] == 1:
            for x, y in XY[i]:
                if check[x - 1] != y:
                    contradict = True
                    break

            if contradict:
                break

    if not contradict:
        max_honest = max(max_honest, sum(check))


print(max_honest)

Submission status: Accepted

Solution code:
N = int(input())

XY = []
for _ in range(N):
    A = int(input())

    temp = []
    for _ in range(A):
        temp.append(list(map(int, input().split())))

    XY.append(temp)


max_honest = 0
for c in range(1 << N):
    check = [0] * N
    contradict = False
    temp = c

    cnt2 = 0
    while temp != 0:
        if 1 & temp:
            check[cnt2] = 1

        temp >>= 1
        cnt2 += 1

    for i in range(N):
        if check[i] == 1:
            for x, y in XY[i]:
                if check[x - 1] != y:
                    contradict = True
                    break

            if contradict:
                break

    if not contradict:
        cnt1 = 0
        for i in range(N):
            if check[i] is not None and check[i] == 1:
                cnt1 += 1

        max_honest = max(max_honest, cnt1)


print(max_honest)

Submission status: Accepted

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

#0-indexedにしておく
for i in range(N):
  A=int(input())
  for _ in range(A):
    x,y=map(int,input().split())
    Ins[i].append((x-1,y))

for i in range(2**N):
  flag=1
  honest=[]
  unkind=[]
  for j in range(N):
    if (i>>j)&1:
      honest.append(j)
    else:
      unkind.append(j)
      #ここまでは想定の組み合わせを作る作業
  for k in honest:
    #honestな人の証言を見ていく
    for l in Ins[k]:
      if l[1]==1 and l[0] in unkind:
        flag=0
        break
        #honestな人がある人物をhonestと答えたのにも関わらず
        #その人がunkindに入るような組み合わせは駄目...ケース1
      elif l[1]==0 and l[0] in honest:
        flag=0
        break
        #honestな人がある人物をunkindと答えたのにも関わらず
        #その人がhonestに入るような組み合わせは駄目...ケース2
  if flag==1:
    ans=max(ans,len(honest))
    #ケース1にもケース2にも該当しない場合
    #現在のhonestの人数をansと比較して大きい方を採用
print(ans)

Submission status: Accepted

Solution code:
def readinput():
    n=int(input())
    shogensList=[]
    for i in range(n):
        a=int(input())
        shogens=[]
        for _ in range(a):
            shogen=list(map(int,input().split()))
            shogens.append(shogen)
        shogensList.append(shogens)
    return n, shogensList

def isMujun(shogensList, shojikiList):
    for shojiki in shojikiList:
        shogens=shogensList[shojiki]
        #print('shogens: {}'.format(shogens))
        #print('shojikiList: {}'.format(shojikiList))
        for x,y in shogens:
            if(y==1):
                if not (x-1 in shojikiList):
                    return True
            else:
                if x-1 in shojikiList:
                    return True
    return False

def main(n,shogensList):
    maxShojiki=0
    for x in range(2**n):
        shojikiList=[]
        b=1
        for i in range(n):
            if (x&b==b):
                shojikiList.append(i)
            b=b*2
        #print('shojikiList: {}'.format(shojikiList))
        #print(isMujun(shogensList, shojikiList))
        if not isMujun(shogensList, shojikiList):
            maxShojiki=max(maxShojiki, len(shojikiList))
    return maxShojiki

if __name__=='__main__':
    n,shogensList=readinput()
    ans=main(n,shogensList)
    print(ans)

Submission status: Accepted

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

# print(pr)

for i in range(2 ** n):
    tflist = [0]*n  # 全員嘘つきと仮定　0＝嘘つき
    for j in range(n):
        if ((i >> j) & 1):
            tflist[j] = 1
    # print(tflist)
    mujun = False
    for k in range(n):
        if (tflist[k] == 1):
            # print(k)
            for m in pr[k]:
                # print(m)
                #print(tflist[m[0] - 1], m[1])
                if (tflist[m[0] - 1] != m[1]):
                    # print("mujun")
                    mujun = True
                    break
    if (not (mujun)):
        ans = max(ans, tflist.count(1))
        # print("anschange")

    # print()

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1 << N):
    isPossible = True
    bit = [0] * N
    for k in range(N):
        if (i >> k) & 1:
            bit[k] = 1
    for idx, b in enumerate(bit):
        if b == 1:
            for x, y in T[idx]:
                isPossible &= (bit[x] == y)
    if isPossible:
        ans = max(ans, bit.count(1))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
saying =[]
people =[]
result = 0

for i in range(N):
    A=int(input())
    people.append(0)
    saying.append([])
    for j in range(A):
        x, y = map(int,input().split())
        saying[i].append(x)
        saying[i].append(y)

for i in range(2**N):

    for j in range(N):
        if(i & 1<<j):
            people[j]=1
        else:
            people[j]=0
    honest = 0
    for j in range(N):
        if people[j]==1:
            for k in range(0, len(saying[j]),2):
                if people[saying[j][k]-1] != saying[j][k+1]:
                    break
            else:
                honest += 1
                continue
            break
    else:
        if honest>result:
            result = honest

print(result)

Submission status: Accepted

Solution code:
from itertools import product
n = int(input())
a = [[] for i in range(n)]

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

ans = 0
for c in product([1, 0], repeat=n):
    f = True
    for i, p in enumerate(c):
        if p == 1:
            for x, y in a[i]:
                if c[x] != y:
                    f = False
                    break
        if not f:
            break
    if f:
        ans = max(ans, sum(c))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

testimony = []

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

ans = 0

for i in range(2**n):
    good = [0]*n
    f = 1
    for j in range(n):
        if (i>>j)&1:
            good[j] = 1

    for k in range(n):
        if good[k]:
            for l,m in testimony[k]:
                if good[l] != m:
                    f = 0
    
    if f:
        ans = max(ans,sum(good))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

shogen = []

for _ in range(N):
    A = int(input())
    asho = []
    for i in range(A):
        x, y = map(int, input().split())
        asho.append((x-1, y))
    shogen.append(asho)
# print(shogen)
ans = 0

for i in range(2**N):
    good = [0 for _ in range(N)]
    f = 1
    for j in range(N):
        if ((i >> j)&1):
            good[j] = 1
    # print(f"good{good}")
    for k in range(N):
        # print("k", k)
        if good[k]:
            for l, m in shogen[k]:
                # print(f"l{l} m{m}")
                if good[l] != m:
                    f = 0
    # print("f", f)
    if f:
        ans = max(ans, sum(good))

print(ans)