Problem:


Score : 300 points

Problem Statement

There are N people numbered 1 to N. Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.

Person i gives A_i testimonies. The j-th testimony by Person i is represented by two integers x_{ij} and y_{ij}. If y_{ij} = 1, the testimony says Person x_{ij} is honest; if y_{ij} = 0, it says Person x_{ij} is unkind.

How many honest persons can be among those N people at most?

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}

Output

Print the maximum possible number of honest persons among the N people.

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.

Sample Input 2

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

Sample Output 2

0

Assuming that one or more of them are honest immediately leads to a contradiction.

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



Sample input:
3
1
2 1
1
1 1
1
2 0


Sample output:
2

Submission status: Runtime Error

Solution code:
# abc147_c.py
# https://atcoder.jp/contests/abc147/tasks/abc147_c

# C - HonestOrUnkind2 /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# 1から N までの番号がついた N人の人がいます。
# 彼らはみな、必ず正しい証言を行う「正直者」か、真偽不明の証言を行う「不親切な人」のいずれかです。
# 人 iは Ai 個の証言を行っています。
# 人 i の j 個目の証言は 2 つの整数 xij , yij で表され、yij=1 のときは「人 xij は正直者である」
# という証言であり、yij=0 のときは「人 xijは不親切な人である」という証言です。
# この N人の中には最大で何人の正直者が存在し得るでしょうか？

# 制約
#     入力は全て整数
#     1≤N≤15
#     0≤Ai≤N−1
#     1≤xij≤N
#     xij≠i
#     xij1≠xij2(j1≠j2)
#     yij=0,1

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N
# A1
# x11 y11
# x12 y12
# :
# x1A1 y1A1
# A2
# x21 y21
# x22 y22
# :
# x2A2 y2A2
# :
# AN
# xN1 yN1
# xN2 yN2
# :
# xNAN yNAN

# 出力
# 存在し得る正直者の最大人数を出力せよ。

# 入力例 1
# 3
# 1
# 2 1
# 1
# 1 1
# 1
# 2 0

# 出力例 1
# 2

# 人 1と人 2 が正直者であり、人 3 が不親切な人であると仮定すると、正直者は 2人であり、矛盾が生じません。
# これが存在し得る正直者の最大人数です。

# 入力例 2
# 3
# 2
# 2 1
# 3 0
# 2
# 3 1
# 1 0
# 2
# 1 1
# 2 0

# 出力例 2
# 0

# 1人でも正直者が存在すると仮定すると、直ちに矛盾します。

# 入力例 3
# 2
# 1
# 2 0
# 1
# 1 0

# 出力例 3
# 1


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    N = int(lines[0])
    # N, M = list(map(int, lines[0].split()))
    # values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(N):
    #     valueses.append(list(map(int, lines[i+1].split())))

    # dic = dict()
    # # e.g.1
    # dic[0] = [[2, 1]] # 人1が「人2 is True」と言っている
    # dic[1] = [[1, 1]] # 人2が「人1 is True」と言っている
    # dic[2] = [[2, 0]] # 人3が「人2 is False」と言っている
    # # e.g.2
    # dic[0] = [[2, 1], [3, 0]]
    # dic[1] = [[3, 1], [1, 0]]
    # dic[2] = [[1, 1], [2, 0]]
    # # e.g.3
    # dic[0] = [[2, 0]]
    # dic[1] = [[1, 0]]

    dic = dict()
    # e.g.2
    key = -1
    is_a_line = True
    for i in range(1, len(lines)):
        if is_a_line:
            key += 1
            a = int(lines[i]) # 2
            dic[key] = list()
            # いくつあるかを取得
            remain_values = a
            is_a_line = False
        else:
            line = lines[i]
            dic[key].append(list(map(int, line.split())))
            remain_values -= 1
            if remain_values == 0:
                is_a_line = True

    result = 0
    for i in range(2**N):
        pattern = format(int(format(i, 'b')), '0=' + str(N))
        log(f'pattern=[{pattern}]')
        flag_this_pattern_is_ok = True
        # 各人の発言を評価 # 人1(=key)が「人2 is True」と言っている (※複数含まれる)
        for key in dic:
            # patternで人keyがTrueの場合、評価対象
            if pattern[key] == '1':
                for x, y in dic[key]: # 人keyが「人x is y」と言っている
                    if pattern[x-1] != str(y):
                        flag_this_pattern_is_ok = False
        if flag_this_pattern_is_ok:
            cnt = len(pattern.replace('0', ''))
            if result < cnt:
                result = cnt

    return [result]


# 引数を取得
def get_input_lines():
    line = input()
    N = int(line)
    lines = list()
    # あとで修正します...
    for _ in range(7):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['3', '1', '2 1', '1', '1 1', '1', '2 0']
        lines_export = [2]
    if pattern == 2:
        lines_input = ['3', '2', '2 1', '3 0', '2', '3 1', '1 0', '2', '1 1', '2 0']
        lines_export = [0]
    if pattern == 3:
        lines_input = ['2', '1', '2 0', '1', '1 0']
        lines_export = [1]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines()
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
L=[]
a=0
for i in range(N):
  A=int(input())
  for j in range(A):
    S=[]
    S=list(map(int,input().split()))
    S.append(i)
    L+=[S]
    a+=A
def X (i):
  T=True
  k=0
  for j in range(a):
    if L[j][0]==i+1 and L[j][1]==0:
      T=False
      k=j
  if T==False:
    T=X(L[k][2])
    if T==True:
      return False
  else:
    return True
c=0
for i in range(N):
  if X(i):
    c+=1
print(c)

Submission status: Runtime Error

Solution code:
N = int(input())
A = []
xy = []
for i in range(N):
    a =  int(input())
    A.append(a)
    for j in range(a):
        x, y = map(int, input().split())
        #２次元配列
        xy.append([x, y])
print(xy)

honest = 0

for i in range(1, 2**N):
    flag = 0
    for j in range(N):
        # j番目が正直と仮定する
        if (i>>j)&1 == 1:
            for x,y in xy[j]:
                # j番目は正直だが矛盾を発見
                if (i>>x)&1 != y:
                    flag = 1
                    break
    # 矛盾がある場合はflag == 1になる
    if flag == 0:
        honest = max(honest, bin(i)[2:].count('1'))
print(honest)

Submission status: Runtime Error

Solution code:
# 人数
N = int(input())
ans = 0
# 証言を二次元配列でタプルで格納(対象者, 真偽値（0:unkind, 1:honest）)
A = []
# 各人でループ
for i in range(N):
  # 各人の証言でループ
  for j in range(int(input())):
    A.append([])
    x, y = map(int, input().split())
    testimony = (x - 1, y) # index的には0始まりなので-1しとく
    A[i].append(testimony)

# 各人が正直者/不親切のパターンを全て列挙
for i in range(2 ** N):
  # パターンから正直者のみ抽出
  honest = []
  for j in range(N):
    if i >> j & 1 == 1:
      honest.append(j)
  # 正直者のパターンとその証言に矛盾がないかチェック
  isContradiction = False
  for j in honest:
    testimonies = A[j]
    for k in testimonies:
      if k[1] == 1:
        # 正直者があいつは正直者と証言しているのに、正直者リストになかったら矛盾
        if not k[0] in honest:
          isContradiction = True
          break
      else:
        # 正直者があいつは不親切と証言しているのに、正直者リストにいたら矛盾
        if k[0] in honest:
          isContradiction = True
          break
  if not isContradiction:
    # 矛盾がないパターンで最大を探す
    ans = max(ans, len(honest))
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
XY = [[] for _ in range(n)]
for i in range(n):
    for j in range(int(input())):
        x, y = map(int, input().split())
        XY[i].append([x-1, y])
honest = 0
for bit in range(1<<n):
    flag = True 
    for i in range(n):
        if bit & (1<<i) :
            for a, b in XY[i]:
                if bit & (1<<a) != b:
                    flag = False 
                    break
    if flag:
        honest = max(honest, bin(i)[2:].count('1'))
print(ans)

Submission status: Runtime Error

Solution code:
#abc147c　HonestOrUnkind
from itertools import product 
n = int(input())
XY = [[] for _ in range(n)]
for i in range(n):
    for j in range(int(input())):
        x, y = map(int, input().split())
        XY[i].append([x-1, y])
honest = 0
for bit in range(1<<n):
    flag = True 
    for i in range(n):
        if bit & (1<<i) :
            for a, b in XY[i]:
                if bit & (1<<a) != b:
                    flag = False 
                    break
    if flag:
        hoenst = max(honest, bin(i)[2:].count('1'))
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import product 
n = int(input())
XY = [[] for _ in range(n)]
for i in range(n):
    for j in range(int(input())):
        x, y = map(int, input().split())
        XY[i].append([x-1, y])
honest = 0
for bit in range(1<<n):
    flag = True 
    for i in range(n):
        if bit & (1<<i) :
            for a, b in XY[i]:
                if bit & (1<<a) != b:
                    flag = False 
                    break
    if flag:
        hoenst = max(honest, bin(i)[2:].count('1'))
        print(ans)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3]
import sys
sys.setrecursionlimit(2000)

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


def syojiki(i):
    for x, y in syogen[i]:
        if y == 1:
            syojiki_list.append(x)
            if len(syojiki_list) >= N:
                return
            syojiki(x)


def check_syojiki(syojikitati):
    d = {}
    for s in range(N):
        if not (s in syojikitati):
            d[s] = 0

    for s in syojikitati:
        d[s] = 1
        for x, y in syogen[s]:
            if d[x] != y:
                return False
            else:
                d[x] = y
    return True


max_syojiki = 0

for i in range(2 ** N):
    d = {}
    syojiki_list = []
    for j in range(N):
        if (i >> j) & 1:
            syojiki_list.append(j)
            syojiki(j)
    syojiki_list = list(set(syojiki_list))
    if check_syojiki(syojiki_list):
        max_syojiki = max(max_syojiki, len(syojiki_list))

print(max_syojiki)

Submission status: Runtime Error

Solution code:
n = int(input())
#入力が大変だわ
alist = []
for _ in range(n):
    p = []
    a = int(input())
    for __ in range(a):
        x, y = map(int, input().split())
        x  = x - 1
        alist += [(a,x,y)]
#A,x,yの情報を持った配列の完成よ
ans = 0
for i in range(2 ** n):
    for j, x, y in alist:
      for k in range(j):
        if ((i >> j)%1 < 1) or ((i >> x)% 1 == y):
          r = 1
        else:
          r = 0
          break
    if r == 1:
      ans = max(ans, sum(map(int,bin(i)[2:])))
            
print(ans - 1)

Submission status: Runtime Error

Solution code:
from itertools import product

N = int(input())
xy = [[] for i in range(N)]

for i in range(N):
    for j i range(int(input())):
        xy[i].append(list(map(int, input().split())))
        
ans = 0
for bit in product([0,1], repeat=N):
    f = 0
    for i, j in enumerate(bit):
        if j == 1:
            for x, y in xy[i]:
                if bit[x-1] != y:
                    f = 1
                    break
    if f == 0:
        ans = max(ans, sum(bit))
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import product

N = int(input())
xy = [[] for in range(N)]

for i in range(N):
    for j i range(int(input())):
        xy[i].append(list(map(int, input().split())))
        
ans = 0
for bit in product([0,1], repeat=N):
    f = 0
    for i, j in enumerate(bit):
        if j == 1:
            for x, y in xy[i]:
                if bit[x-1] != y:
                    f = 1
                    break
    if f == 0:
        ans = max(ans, sum(bit))
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        x, y = map(int, input().split())
        xy.append([x, y])
    XY.append(xy)
ans = 0
for k in range(2 ** n):
    s = [0] * n
    cnt = 0
    case = 0
    for j in range(n):
        if (k >> j) & 1:
            s[n - 1 - j] = 1
            cnt += 1
    for k in range(n):
        if s[k] == 1:
            for l in range(len(XY[l])):
                if s[XY[k][l][0] - 1] != XY[k][l][1]:
                    case = 1
    if case == 0:
        ans = max(ans, cnt)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        x, y = map(int, input().split())
        xy.append([x, y])
    XY.append(xy)
ans = 0
for i in range(2 ** n):
    s = [0] * n
    cnt = 0
    case = 0
    for j in range(n):
        if (i >> j) & 1:
            s[n - 1 - j] = 1
            cnt += 1
    for k in range(n):
        if s[k] == 1:
            for l in range(len(XY[l])):
                if s[XY[k][l][0] - 1] != XY[k][l][1]:
                    case = 1
    if case == 0:
        ans = max(ans, cnt)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        x, y = map(int, input().split())
        xy.append([x, y])
    XY.append(xy)
ans = 0
for i in range(2 ** n):
    s = [0] * n
    cnt = 0
    case = True
    for j in range(n):
        if (i >> j) & 1:
            s[n - 1 - j] = 1
            cnt += 1
    for k in range(n):
        if s[k] == 1:
            for l in range(len(XY[l])):
                if s[XY[k][l][0] - 1] != XY[k][l][1]:
                    case = False
    if case is True:
        ans = max(ans, cnt)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        x, y = map(int, input().split())
        xy.append([x, y])
    XY.append(xy)
ans = 0
for i in range(2 ** n):
    s = [0] * n
    cnt = 0
    case = True
    for j in range(n):
        if (i >> j) & 1:
            s[j] = 1
            cnt += 1
    for k in range(n):
        if s[k] == 1:
            for l in range(len(XY[l])):
                if s[XY[k][l][0] - 1] != XY[k][l][1]:
                    case = False
    if case is True:
        ans = max(ans, cnt)
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        x, y = map(int, input().split())
        xy.append([x, y])
    XY.append(xy)
ans = 0
for i in range(2 ** n):
    s = [0] * n
    cnt = 0
    case = True
    for j in range(n):
        if (i >> j) & 1:
            s[j] = 1
            cnt += 1
    for k in range(n):
        if s[k] == 1:
            for l in range(len(XY[l])):
                if s[XY[k][l][0] - 1] != XY[k][l][1]:
                    case = False
                    break
    if case is True:
        ans = max(ans, cnt)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
import itertools


def input():
    return sys.stdin.readline().rstrip()


def main():
    N = int(input())
    A = []
    X = [[] for _ in range(N)]
    Y = [[] for _ in range(N)]

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

    #    for i in itertools.product(range(2),repeat=N): ##大きい方からになっていない
    for i in range(N, 0, -1):  # 多い方から
        for honest in itertools.combinations(range(N), i):  # honest 正直者集合
            flag = 1
            for i in range(N):  # i::証言者
                if i not in honest:  # 嘘つきなら検索から外す
                    continue
                for j in range(A[i - 1]):
                    x_temp = X[i][j] -1
                    y_temp = Y[i][j]

                    if y_temp == 1 and (x_temp not in honest):
                        flag = 0
                        break
                    if y_temp == 0 and (x_temp in honest):
                        flag = 0
                        break
                if flag == 0:
                    break
            if flag == 1:
                print(i)
                exit()

    print(0)

    pass


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import itertools

n = int(input())

l = list(itertools.product([0,1], repeat=n))[::-1]

A = {}
for i in range(n):
    ai = int(input())
    for j in range(ai):
        x, y = map(int, input().split())
        if i not in A:
            A[i] = []
        A[i].append((x, y))

def shoujiki(i):
    check = {}
    cnt = 0
    for j in range(n):
        check[j+1] = i[j]
    for j in range(n):
        ai = len(A[j])
        if i[j] == 1:
            for k in range(ai):
                x, y = A[j][k]
                if check[x] == y:
                    cnt += 1
                else:
                    return 0
    return cnt

mans = 0
for i in l:
    mans = max(shoujiki(i), mans)

print(mans)

Submission status: Runtime Error

Solution code:
n = int(input())
tst = [[] for i 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])
ans = 0
for bit in range(1<<n):
    honest = [0]*n
    check = 1
    for i in range(n):
        if (bit>>i)&1:
            honest[-1-i] = 1
    for i in range(n):
        if not honest[i]:
            continue
        for l in tst[i]:
            if l[1]!=honest[l[0]-1]:
                check = 0
                break
    if check:
        ans = max(ans,sum(honest))
print(ans)

Submission status: Runtime Error

Solution code:
A = [0]*N
for i in range(N):
    a = int(input())
    A[i]=a
    li[i]=[list(map(int,input().split())) for i in range(a)]

counter = 0
for humen in product([0,1],repeat=N):
    flag = True
    for i in range(N):
        if humen[i]==1:
            for s in range(A[i]):
                if not li[i][s][1]==humen[li[i][s][0]-1]:
                    flag=False
                    break
        
                
    if flag :
        counter = max(counter,humen.count(1))


print(counter)

Submission status: Runtime Error

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

while len(input())>0:
    t = int(input())
    T_temp=[]
    for t_ in range(t) :
        temp = list(map(int,input().split()))
        T_temp.append(temp)
    T.append(T_temp)
    
def check_Contradiction(true_list):
    S = {}
    for n in range(N):
        if n in true_list:
            S[n]=set([1])
        else:
            S[n]=set([0])

    for t in true_list:
        for T_ in T[t]:
            S[T_[0]-1].add(T_[1])
    ok=True
    for s in S.keys():
        if len(S[s])!=1:
            ok='False'
            break

    return ok

ok_max = -1
for i in range(2**N):
#     print('=====',i)
    true_list=[]
    for j in range(N):
        if i>>j&1 ==True:
            true_list.append(j)
#     print(true_list)
#     print(check_Contradiction(true_list))
            
    if check_Contradiction(true_list)==True:
        if ok_max < len(true_list):
            ok_max=len(true_list)
            
print(ok_max)

Submission status: Runtime Error

Solution code:
    # 証言が矛盾していないかチェックする
    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)

Submission status: Runtime Error

Solution code:
# 証言が矛盾していないかチェックする
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)

Submission status: Runtime Error

Solution code:
import itertools
N = int(input())
A=[0,1]
B=[]
for j in range(N):
    AN = int(input())
    LI = []
    for k in range(AN):
        x,y =map(int,input().split())
        LI.append([x,y])
        if k == AN-1:
            B.append(LI)
Anl =list(itertools.product(A, repeat=N))
An1 = 0
for i in range(len(Anl)):
    box = []
    Anli = Anl[i]
    for j in range(len(Anli)):
        if Anli[j] == 0:
            box.append('T')
            continue
        else:
            Bj = B[j]
            for t in range(len(Bj)):
                Bjt = Bj[t]
                if Bjt[1] != Anli[Bjt[0]-1]:
                    box.append('F')
                    break
                elif t == len(Bj)-1:
                    box.append('T')
                else:
                    continue
    if 'F' not in box and Anli.count(1) > An1:
        An1 = Anli.count(1)
print(An1)

Submission status: Runtime Error

Solution code:
import itertools
N = int(input())
A=[0,1]
B=[]
for j in range(N):
    AN = int(input())
    LI = []
    for k in range(AN):
        x,y =map(int,input().split())
        LI.append([x,y])
        if k == AN-1:
            B.append(LI)
Anl =list(itertools.product(A, repeat=N))
for i in range(len(Anl)):
    box = []
    An1 = 0
    Anli = Anl[i]
    for j in range(len(Anli)):
        if Anli[j] == 0:
            box.append('T')
            continue
        else:
            Bj = B[j]
            for t in range(len(Bj)):
                Bjt = Bj[t]
                if Bjt[1] != Anli[Bjt[0]-1]:
                    box.append('F')
                    break
                elif t == len(Bj)-1:
                    box.append('T')
                else:
                    continue
    if 'F' not in box:
        An = Anli
print(An.count(1))

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction


def ternary (n, k, length):
    if n == 0:
        nums = ['0' for i in range(length)]
        nums = ''.join(nums)
        return nums
    nums = ''
    while n:
        n, r = divmod(n, k)
        nums += str(r)
    nums = nums[::-1]
    nums = nums.zfill(length)
    return nums

def main():
    num = int(input())
    say_count = []
    say_data = []
    for i in range(num):
        aaa = int(input())
        say_count.append(aaa)
        data = [list(map(int, input().split())) for i in range(aaa)]
        say_data.append(data)


    ans = 0
    for i in range(2 ** num):
        bin_data = list(map(int, ternary(i, 2, num)))
        kari_ans = bin_data.count(1)

        people_flg = [-1 for i in range(num)]
        dame_flg = 0
        for j in range(num):
            if people_flg[j] == -1:
                people_flg[j] = bin_data[j]
            else:
                if people_flg[j] != bin_data[j]:
                    dame_flg = 1

            if people_flg[j] == 0:
                continue

            for k in range(say_count[j]):
                people, flg = [say_dataj][k]
                people -= 1
                if people_flg[people] == -1:
                    people_flg[people] = flg
                else:
                    if people_flg[people] != flg:
                        dame_flg = 1

            if dame_flg:
                break
        if dame_flg:
            continue
        ans = max(ans, kari_ans)

    print(ans)






if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
shogen=[]
count_ans=[]
for i in range(N):
    A=int(input())
    shogen.append([list(map(int,input().split())) for i in range(A)])
def saiki(A):
    if len(A)==N:
        honest=set()
        honest_kari=set()
        unkind=set()
        count=0
        unkind_kari=set()
        for i in range(N):
            if A[i]==1:
                honest.add(i)
            else:
                unkind.add(i)
        for i in range(N):
            if i in honest:
                for j in range(len(shogen[i])):
                    if shogen[i][j][1]==0:
                        unkind_kari.add(shogen[i][j][0])
                    else:
                        honest_kari.add(shogen[i][j][0])
        for i in honest:
            if i not in unkind_kari:
                if i not in unkind:
                    count+=1
        for i in unkind:
            if i not in honest_kari:
                if i not in honest:
                    count+=1
        if count==len(unkind_kari)+len(honest_kari):
            count_ans.append(len(honest))

        
        return
    for i in range(2):
        A.append(i)
        saiki(A)
        A.pop()
saiki([])
print(max(count_ans))

Submission status: Runtime Error

Solution code:

def main():
    z = [-1] * 10
    xy = []
    n = int(input())
    for _ in range(n):
        a = int(input())
        xy.append([list(map(int, input().split())) for _ in range(a)])
    ans = 0
    
    for a in range(2**n):
        c = []
        for b in range(n):
            c.append(a >> b & 1)
       
        flag = True
        for i in range(n):
            if c[i] == 1:
                for x in xy[i]:
                    if z[x[0] - 1] == -1 or z[x[0] - 1] == x[1]:
                        z[x[0] - 1] = x[1]
                    else:
                        flag = False
            
        for i in range(n):
            if z[i] != -1:
                if z[i] !=c[i]:
                    flag = False
                        
        if flag:
            ans = max(ans, sum(c))
    
    print(ans)
        
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
@patch('builtins.input', test.test_input)
def main():
    z = [-1] * 10
    xy = []
    n = int(input())
    for _ in range(n):
        a = int(input())
        xy.append([list(map(int, input().split())) for _ in range(a)])
    ans = 0
    print(0)
        
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    z = [-1] * 10
    n = int(input())
    xy = []
    for _ in range(n):
        a = int(input())
        xy.append([list(map(int, input().split())) for _ in range(a)])
    ans = 0
    
    for a in range(2**n):
        c = []
        for b in range(n):
            c.append(a >> b & 1)
       
        flag = True
        for i in range(n):
            if c[i] == 1:
                for x, y in xy[i]:
                    if z[x - 1] == -1 or z[x - 1] == y:
                        z[x - 1] = y
                    else:
                        flag = False
            
        for i in range(n):
            if z[i] != -1:
                if z[i] !=c[i]:
                    flag = False
                        
        if flag:
            ans = max(ans, sum(c))
    
    print(ans)
        
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import math





n= int(input())



xandy=np.ones((n,n))

xandy=xandy*(-1)

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

max=0


for l in range(0,2**n):
    i=2**n-1-l
    flag=1
    if max<bin(i).count("1"):
        for j in range(0,n):
       
        #iを2進数表示した時kの位置ででの0-1が対応してあるか立っているか？
            if  bin( i& 2**j).count("1")>0:
                 for k in range(0,n):
                      if  xandy[j][k]!=-1 and xandy[j][k]!=(i >> k)%2:
                          flag=0 
                        break
                       
            if flag==0:
                break
        if flag==1 and max<bin(i).count("1"):
             max=bin(i).count("1")
         

print(max)

Submission status: Runtime Error

Solution code:
N = int(input())
testimony = [[] for _ in range(N)]
for i in range(N):
    num = int(input())
    person, state = map(int,input().split())
    testimony[i].append([person-1,state])
#print(testimony)
        
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)

Submission status: Runtime Error

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

res = 0
for i in range(1<<N):
  mapper = {1: [], 0: []}
  flg = True
  cnt = 0
  for j in range(N):
    if (i>>j)&1:
      for x,y in conditions[j]:
        if x in mapper[1-y] or j in mapper[0]:
          flg = False
          break
        mapper[y].append(x)
      cnt += 1
    else:
      for x,y in conditions[j] or j in mapper[1]:
        if x in mapper[y]:
          flg = False
          break
        mapper[1-y].append(x)

    if not flg: break

  if flg:
    res = max(res, cnt)

print(res)