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

comments = []
for i in range(person_num):
    comments_num = int(input())
    comment = []
    for j in range(comments_num):
        comment.append(list(map(int, input().split())))
    comments.append(comment)

honest_max = 0
for i in range(2 ** person_num):
    check = list(bin(i)[2:].zfill(person_num))
    for j in range(person_num):
        if check[j] == "1":
            for comment in comments[j]:
                if check[comment[0]-1] != str(comment[1]):
                    break
            else:
                continue
            
            break
    else:
        if honest_max < check.count("1"):
            honest_max = check.count("1")

print(honest_max)

Submission status: Accepted

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

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

ans = 0

for p in itertools.product([1,0], repeat=n):
  ok = 1
  for l in ll:
    if p[l[0]] == 1 and p[l[1]] != l[2]:
      ok = 0
      break
  if ok:
    ans = max(ans, sum(p))

print(ans)

Submission status: Accepted

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

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

from itertools import product

lb = [''.join(b) for b in product('01', repeat=n)]
lc = [sum(int(j) for j in i) for i in lb]
lc, lb = zip(*sorted(zip(lc, lb), reverse=True))
lb = [[int(j) for j in i] for i in lb]

for l in lb:
  ok = 1
  for i in range(n):
    a = la[i]
    for j in range(a):
      x, y = lxy[i][j]
      if l[i] == 1 and l[x-1] != y:
        ok = 0
        break
  if ok:
    print(sum(int(k) for k in l))
    break
else:
  print(0)

Submission status: Accepted

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

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

lb = []
for i in range(2**n):
  lb += [str(bin(i))[2:].zfill(n)]
lc = [sum(int(j) for j in i) for i in lb]
lc, lb = zip(*sorted(zip(lc, lb), reverse=True))
lb = [[int(j) for j in i] for i in lb]

for l in lb:
  ok = 1
  for i in range(n):
    a = la[i]
    for j in range(a):
      x, y = lxy[i][j]
      if l[i] == 1 and l[x-1] != y:
        ok = 0
        break
  if ok:
    print(sum(int(k) for k in l))
    break
else:
  print(0)

Submission status: Accepted

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

lb = []
for i in range(2**n):
  lb += [str(bin(i))[2:].zfill(n)]
lc = [sum(int(j) for j in i) for i in lb]
lc, lb = zip(*sorted(zip(lc, lb), reverse=True))
lb = [[int(j) for j in i] for i in lb]

for l in lb:
  ok = 1
  for i in range(n):
    a = la[i]
    for j in range(a):
      x, y = lxy[i][j]
      if l[i] == 1 and l[x-1] != y:
        ok = 0
        break
  if ok:
    print(sum(int(k) for k in l))
    break
else:
  print(0)

Submission status: Accepted

Solution code:
def main():
    n = int(input())

    evidences = [[] for _ in range(n)]

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

    ans = 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 evidences[j]:
                if (i >> x) & 1 != y:
                    consistent = False
                    break
            if not consistent:
                break
        if consistent:
            ans = max(ans, bin(i)[2:].count('1'))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
testimony_table = [[] for _ in range(n)]

for i_witness in range(n):
    ai = int(input())
    for _ in range(ai):
        xij, yij= map(int, input().split())
        testimony_table[i_witness].append((xij-1,yij))

ans = 0
for i in range(2**n):
    isConflict = False

    for j_witness in range(n): # それぞれの桁について0か1かを判断したいので
        if (i >> j_witness) & 1 == 0: # j桁目が1かどうかをジャッジ
            continue


        for x_suspect, y_testimony in testimony_table[j_witness]:
            if ((i >> x_suspect) & 1) != y_testimony:
                isConflict = True
                break

        if isConflict:
            break
    if isConflict == False:
        ans = max(ans, bin(i).count("1"))

print(ans)

Submission status: Accepted

Solution code:
def dudge(k):
    for i in range(n):
        p = (k >> i) % 2
        if p == 0: continue

        for claim in xy[i]:
            x = claim[0]
            y = claim[1]

            truth = (k >> x-1) % 2
            if truth == 1 and y == 0:
                return False
            elif truth == 0 and y == 1:
                return False
    return True


n = int(input())

xy = []
for i1 in range(n):
    ai = int(input())
    xy.append([])

    for i2 in range(ai):
        xi,yi = map(int, input().split())
        xy[i1].append((xi, yi))

result = 0
for k in range(1 << n):
    if dudge(k):
        l = [i for i in range(n) if (k >> i) % 2 == 1]
        cnt = 0
        result = max(result, len(l))

print(result)

Submission status: Accepted

Solution code:
def dudge(k):
    for i in reversed(range(n)):
        p = (k >> i) % 2
        #print(' i = ', i, ' p = ', p)
        if p == 0: continue

        for claim in xy[i]:
            x = claim[0]
            y = claim[1]

            truth = (k >> x-1) % 2
            #print('   x = ', x,  ' y = ', y, ' t = ', truth)
            if truth == 1 and y == 0:
                return False
            elif truth == 0 and y == 1:
                return False
    return True


n = int(input())

xy = []
for i1 in range(n):
    ai = int(input())
    xy.append([])

    for i2 in range(ai):
        xi,yi = map(int, input().split())
        xy[i1].append((xi, yi))

#print(xy)

result = 0
for k in reversed(range(1 << n)):
    #print(bin(k))

    if dudge(k):
        #print('    True')
        l = [i for i in range(n) if (k >> i) % 2 == 1]
        cnt = 0
        #for i in range(n):
        #    if (k >> i) % 2 == 1: cnt += 1
        #print('    ', l, len(l))
        result = max(result, len(l))
        #result = max(result, cnt)

print(result)

Submission status: Accepted

Solution code:
def dudge(k):
    for i in reversed(range(n)):
        p = (k >> i) % 2
        #print(' i = ', i, ' p = ', p)
        if p == 0: continue

        for claim in xy[i]:
            x = claim[0]
            y = claim[1]

            truth = (k >> x-1) % 2
            #print('   x = ', x,  ' y = ', y, ' t = ', truth)
            if truth == 1 and y == 0:
                return False
            elif truth == 0 and y == 1:
                return False
    return True


n = int(input())

xy = []
for i1 in range(n):
    ai = int(input())
    xy.append([])

    for i2 in range(ai):
        xi,yi = map(int, input().split())
        xy[i1].append((xi, yi))

#print(xy)

result = 0
for k in reversed(range(1 << n)):
    #print(bin(k))

    if dudge(k):
        #print('    True')
        #l = [i for i in range(n) if (k >> i) % 2 == 1]
        cnt = 0
        for i in range(n):
            if (k >> i) % 2 == 1: cnt += 1
        #print('    ', l, len(l))
        #result = max(result, len(l))
        result = max(result, cnt)

print(result)

Submission status: Accepted

Solution code:
from itertools import product
N = int(input())

An = []
Xn, Yn = [], []

for i in range(N):
    An.append(int(input()))
    Xn.append([])
    Yn.append([])
    for j in range(An[i]):
        x, y = map(int, input().split())
        Xn[i].append(x)
        Yn[i].append(y)

ans = 0
for prod in product("01", repeat=N):
    # bits : i 番目の bit が 1 なら i は正直者として, 仮定する
    bits = list(map(int, prod))
    flag = True

    # bits のリストで矛盾が無いかを調べる
    for i in range(N):
        # i が不親切と仮定するなら,調べる必要はない
        if bits[i] != 1:
            continue

        # B[i] == 1, つまり i が正直者である場合, A_i 個の証言を調べる
        for j in range(An[i]):
            # 「i の証言 : y_ij = 1 のとき x_ij == 1 (正直者である)」に矛盾がある場合
            if Yn[i][j] == 1 and bits[Xn[i][j]-1] == 0:
                flag = False

            # 「i の証言 : y_ij = 0 のとき x_ij == 0 (不親切である)」に矛盾がある場合
            elif Yn[i][j] == 0 and bits[Xn[i][j]-1] == 1:
                flag = False

    # flag が True => bits のリストで矛盾がない
    if flag:
        ans = max(ans, bits.count(1))

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())


say=[]
for _ in range(N):
    temp=[-1]*N
    A=int(input())
    for __ in range(A):
        x,y=map(int,input().split())
        temp[x-1]=y
    say.append(temp)

#print(say)

ans=0
for i in range(2**N):
    katei=list(str(bin(i))[2:])
    katei=list(map(int,katei))
    katei=[0]*(N-len(katei))+katei
    #print(katei)
    
    flag=True
    for num in range(N):
        if katei[num]==1:
            for num2 in range(N):
                if (say[num][num2]==0 and katei[num2]==1) or (say[num][num2]==1 and katei[num2]==0):
                    flag=False
    if flag:
        ans=max(ans,sum(katei))
    
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

# B[i]=1: 人iは正直者，0: 不親切
# すべての取りうる状態について
ans = []
for e in itertools.product("01",repeat=N):
    # tmp = "".join(e)
    B = [int(a) for a in e]

    flag = True
    # この状態が矛盾しないことをチェックする
    # つまり，
    # i=正直者かつi「jは正直者」=> j=不親切
    # i=正直者かつi「jは不親切」=> j=正直者
    # の場合，矛盾
    for i in range(N):
        # iが正直者ならば
        if B[i] == 1:
            # iのすべての証言について
            for j in range(A[i]):
                # 「x[i][j]は正直者」と証言した場合
                if y[i][j] == 1:
                    # x[i][j]が正直者であることを確認
                    if B[x[i][j]] == 0: flag = False
                else:
                    # x[i][j]が不親切であることを確認
                    if B[x[i][j]] == 1: flag = False

    if flag:
        # 正直者の数
        ans.append([e == 1 for e in B].count(True))

# 矛盾しない状態の中で，正直者の数が最大になるもの
print(max(ans))

Submission status: Accepted

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

max_val = 0
for i in range(2 ** N):
    check = True
    for j in range(N):
        if i >> j & 1 == 1:
            for x, y in all[j]:
                if i >> (x-1) & 1 != y:
                    check = False
                    break
    if check == True:
        max_val = max(max_val, bin(i)[2:].count('1'))
print(max_val)

Submission status: Accepted

Solution code:

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: 
            for x,y in testimony[j]:
                if (i>>x)&1 != y: 
                    flag = 1
                    break
    if flag == 0: 
        honest = max(honest, bin(i)[2:].count('1')) 
print(honest)

Submission status: Accepted

Solution code:
def main():
    N = int(input())

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

    ans = 0

    for i in range(1, 2**N):
        tmp = 0
        flag = True
        for j in range(N):
            if (i>>j)&1 == 1:
                tmp += 1
                for d in data[j]:
                    if (i>>d[0])&1 != d[1]:
                        flag = False
        if (flag) & (tmp > ans):
            ans = tmp
    print(ans)

    return 0
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [0] * N
X = [[] for _ in range(N)]
for i in range(N):
  A[i] = int(input())
  for j in range(A[i]):
    X[i].append(list(map(int, input().split())))
Truth = 2 ** N
ans = 0
while(bin(Truth) != bin(2 ** (N + 1))):
  for i in range(N):
    if(bin(Truth)[i+3] == "1"):
      for j in range(A[i]):
        if(int(bin(Truth)[X[i][j][0] + 2]) != X[i][j][1]):
          break
      else:
        continue
      Truth += 1
      break
  else:
    ans = sum(list(map(int,list(bin(Truth)[3:]))))
    Truth += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
 
 
def main():
    N = int(input())
    testimonies = []
    for _ in range(N):
        a = int(input())
        xy = []
        for _ in range(a):
            xy.append(list(map(int, input().split(" "))))
        testimonies.append(xy)
 
    assumptions = product([0, 1], repeat=N)
    assumptions = sorted(assumptions, key=lambda x: x.count(0))
    for assumption in assumptions:
        for i in range(N):
            if assumption[i]:
                for testimony in testimonies[i]:
                    if not assumption[testimony[0] - 1] == testimony[1]:
                        break
                else:
                    continue
                break
        else:
            print(assumption.count(1))
            break
        continue
 
 
if __name__ == '__main__':
    main()
from itertools import product


def main():
    N = int(input())
    testimonies = []
    for _ in range(N):
        a = int(input())
        xy = []
        for _ in range(a):
            xy.append(list(map(int, input().split(" "))))
        testimonies.append(xy)

Submission status: Accepted

Solution code:
#abc147-c:dfs
def dfs(i,evid,honest):
    #evid:正直者と仮定した人の発現
    #honest:正直者の番号

    global ans
    if i==n:
        count = len(honest)

        #発言に矛盾がないか調べる
        for i in range(1,n+1):

            if i in honest:
                if [i,0] in evid:
                    count=0
            else:
                if [i,1] in evid:
                    count=0

        ans=max(ans,count)

    else:
        dfs(i+1,evid+l[i],honest+[i+1])
        #正直者と仮定する
        dfs(i+1,evid,honest)
        #不親切な人

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

ans=0
dfs(0,[],[])
print(ans)

Submission status: Accepted

Solution code:
from itertools import product


def main():
    N = int(input())
    testimonies = []
    for _ in range(N):
        a = int(input())
        xy = []
        for _ in range(a):
            xy.append(list(map(int, input().split(" "))))
        testimonies.append(xy)

    assumptions = product([0, 1], repeat=N)
    assumptions = sorted(assumptions, key=lambda x: x.count(0))
    for assumption in assumptions:
        for i in range(N):
            if assumption[i]:
                for testimony in testimonies[i]:
                    if not assumption[testimony[0] - 1] == testimony[1]:
                        break
                else:
                    continue
                break
        else:
            print(assumption.count(1))
            break
        continue


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int()] * N
    x = [[] for i in range(N)]
    y = [[] for i in range(N)]
    for i in range(N):
        A[i] = int(input())
        for j in range(A[i]):
            xij, yij = map(int, input().split())
            x[i].append(xij - 1)
            y[i].append(yij)
    ans = 0
    for b in range(1 << N):
        flg = True
        for i in range(N):
            if not b & 1 << i:
                continue
            for j in range(A[i]):
                if 1 & b >> x[i][j] ^ y[i][j]:
                    flg = False
                    break
            if not flg:
                break
        if flg:
            ans = max(ans, bin(b).count("1"))
    print(ans)
    return


main()

Submission status: Accepted

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

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

ans = 0
for i in range(2**n):
    tmp = '0'*n
    for j in range(n):
        if i >> j & 1:
            tmp = tmp[:j]+'1'+tmp[j+1:]
    
    flg = True
    
    for j in range(n):
        if tmp[j] =='1':
            for k in range(len(lst[j])):
                x,y = lst[j][k]
                if tmp[x-1] == str(y):
                    continue
                else:
                    flg = False
        else:
            continue
    if flg:
        ans = max(ans, list(tmp).count('1'))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Q = [[] for _ in range(N)]

for i in range(N):
    A = int(input())

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

res = 0

for k in range(1 << N):
    flag = False
    for i in range(N):
        f = (k & (1 << i)) > 0

        if not f:
            continue
        for q in Q[i]:
            x, y = q
            tx = (k & (1 << x)) > 0

            if (y and not tx) or (not y and tx):
                flag = True
                break

        if flag:
            break
    else:
        res = max(res, bin(k).count("1"))

print(res)

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
XY = [[] for _ in range(N)]
for i in range(N):
    A = int(stdin.readline().rstrip())
    for j in range(A):
        x, y = [int(_) for _ in stdin.readline().rstrip().split()]
        XY[i].append([x-1, y])

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

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0
for pattern in product(range(2), repeat=N): # 0:不正直 1:正直
  flag = True
  for i in range(N):
    if pattern[i]: # iさんが正直と仮定
      # 発言と一致するか？
      for a in range(A[i]):
        if pattern[XY[i][a][0]-1] != XY[i][a][1]:
          flag = False
          break
  if flag:
    ans = max(ans, sum(pattern))

print(ans)

Submission status: Accepted

Solution code:
a = int(input())
l = []

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

def is_honest(i,j):
    return (i >> j)%2 ==1

def honest_cnt(i):
    ans = 0
    for j in range(a):
        ans += is_honest(i,j)
    return ans
ans =0

for i in range(1 << a):
    ok = True
    for j in range(a):
        if not is_honest(i,j):continue
        for (x,y) in l[j]:
            if y == 0 and is_honest(i,x):ok = False
            if y == 1 and not is_honest(i,x):ok = False
        
    if ok:
        ans = max(ans, honest_cnt(i))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A =[0]*N
S =[[] for i in range(N)]
ans = 0
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        S[i].append(list(map(int, input().split())))
form = "0" + str(N) + "b"
for i in range(2**N):
    p = list(map(int, list(format(i,form))))
#    print([[p[j] == 0 or p[S[j][k][0]-1] == S[j][k][1] for k in range(len(S[j]))] for j in range(N)])
    if all([all([p[j] == 0 or p[S[j][k][0]-1] == S[j][k][1] for k in range(len(S[j]))]) for j in range(N)]):
        ans = max(ans,sum(p))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())  # 人数の入力
a = [0] * n  # 証言のリスト
x = [[0] * n for _ in range(n)]  # 人
y = [[0] * n for _ in range(n)]  # 判定

for i in range(n):
    a[i] = int(input())  # 証言数の入力
    for j in range(a[i]):
        # 人とその人の判定を入力
        x[i][j], y[i][j] = map(int, input().split())
        x[i][j] -= 1  # 人のインデックスは1から始まるように設定する


def check(honest):  # 矛盾の有無を判定する関数
    for i in range(n):
        if not honest[i]: continue  # Trueでないなら次のloopを回す
        for j in range(a[i]):
            # 判定がTrueで証言者がunkindならFalseを返す
            if y[i][j] == 1 and not honest[x[i][j]]: return False
            # 判定がFalseで証言者がhonestならTrueを返す
            if y[i][j] == 0 and honest[x[i][j]]: return False
    # 以上の条件に当てはまらなったらTrueを返す
    return True


def dfs(honest):  # 深さ優先探索の実装
    if len(honest) == n:  # 全て確認し終わったら
        if check(honest):  # 矛盾がなければ
            return sum(honest)  # Trueの数を合計して出力
        else:  # 矛盾があれば
            return 0
    # まだ全て確認していなければ，再帰を使って全探索を続ける
    return max(dfs(honest + [True]), dfs(honest + [False]))


print(dfs([]))

Submission status: Accepted

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

N = int(input())
tf = [[] for _ in range(N)]
pl = []
for i in range(N):
    p = int(input())
    pl.append(p)
    for j in range(p):
        tf[i].append(list(map(int, input().split())))

ans = 0
import itertools
for flags in itertools.product([1, 0], repeat=N):
    f = True
    for i in range(N):
        for j in range(pl[i]):
            if flags[i] == 1:
                if flags[tf[i][j][0] - 1] != tf[i][j][1]:
                    f = False
            # elif flags[i] == 0:
            #     if flags[tf[i][j][0] - 1] == tf[i][j][1]:
            #         print(i)
            #         print(tf[i][j][0] - 1)
            #         print(flags)
            #         f = False
            if not f:
                break
        if not f:
            break
    if f:
        ans = max(sum(flags), ans)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
shogen=[]
for i in range(N):
  a=int(input())
  ash=[]
  for j in range(a):
    xy=tuple(map(int,input().split()))
    ash.append(xy)
  shogen.append(ash)
cnt="0000"
for i in range(1<<N):
  flag=True
  fact="0"*(N-len(bin(i)[2:]))+bin(i)[2:]
  for j in range(N):
    if fact[j]=='1':
      s=shogen[j]
      for xy in s:
        if fact[xy[0]-1]!=str(xy[1]):
          flag=False
          break
  if flag:
    cnt=fact
ans=0
for c in cnt:
  ans+=int(c)
      
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

XY=[[list(map(int,input().split())) for i in range(int(input()))] for n in range(N)]
for i in range(N):
    for m in range(len(XY[i])):
        XY[i][m][0]-=1

num=set()
for i in range(2**N):
    AC=[-1 for Z in range(N)]
    lst=(N-len(bin(i)[2:]))*"0"+bin(i)[2:]
    flag=0
    for l in range(N):
        if lst[l]=="1":
            if AC[l]==0:
                flag=1
                break
            else:
                AC[l]=1

            for x,y in XY[l]:
                if AC[x]==-1:
                    AC[x]=y
                if AC[x]==1 and y==0 or AC[x]==0 and y==1 :
                    flag=1
                    break
            if flag:
                break
        else:
            if AC[l]==1:
                flag=1
                break
            else:
                AC[l]=0
    if not flag:
        num.add(sum(AC))
print(max(num))

Submission status: Accepted

Solution code:
def is_case_possible(case):
    for i, flag in enumerate(case):
        if flag == '1':
            for x, y in XY[i]:
                x -= 1
                if case[x] != str(y):
                    return False
    return True

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

ans = 0
for i in range(2**N):
    case = bin(i)[2:].zfill(N)
    if is_case_possible(case):
        ans = max(ans, case.count('1'))
print(ans)

Submission status: Accepted

Solution code:
from collections import namedtuple
from itertools import compress, product

Testimony = namedtuple('Testimony', 'honest_persons unkind_persons')

def bin_iter(num, width=1):
    assert width > 0
    while num > 0 or width > 0:
        yield num & 1
        num >>= 1
        width -= 1

def pop_count(num):
    return sum(bin_iter(num))

def solve(testimonies):
    def is_not_contradicted(honest_persons):
        for testimony in compress(testimonies, bin_iter(honest_persons, len(testimonies))):
            if (testimony.honest_persons | honest_persons) > honest_persons:
                return False
            if testimony.unkind_persons & honest_persons:
                return False
        return True
    return max(map(pop_count, filter(is_not_contradicted, range(1 << len(testimonies)))), default=0)

def main():
    N = int(input())
    testimonies = []
    for _ in range(N):
        honest_persons, unkind_persons = 0, 0
        for _ in range(int(input())):
            x, y = list(map(int, input().split()))
            if y == 1:
                honest_persons |= (1 << (x - 1))
            else:
                unkind_persons |= (1 << (x - 1))
        testimonies.append(Testimony(honest_persons, unkind_persons))
    print(solve(testimonies))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    
    xy=list()
    A=list()
    for i in range(N):
        a=int(input())
        l=list()
        for _ in range(a):
            l.append(tuple(map(int, input().split())))
        A.append(a)
        xy.append(l)

    answer = 0
    for i in range(2**N):
        contradict=False
        count = 0
        for j in range(N):
            if (i>>j)&1 > 0:
                count += 1
                for x, y in xy[j]:
                    k = (i>>(x-1))&1
                    if (y==1 and k==0) or (y==0 and k==1):
                        contradict=True
                        break
            if contradict==True:
                break
        else:
            answer = max(answer, count)

    print(answer)

# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc147","c",main)

Submission status: Accepted

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

def is_honest(i,j):
    return(i >> j)%2 ==1

def honest_cnt(i):
    ans = 0
    for j in range(n):
        ans += is_honest(i,j)
    return ans

ans= 0
for i in range(1<<n):
    bl = True
    for j in range(n):
        if not is_honest(i,j):
            continue
        for (x,y) in shogen[j]:
            if y==0 and is_honest(i,x):
                bl = False
            if y==1 and not is_honest(i,x):
                bl = False
    if bl:
        ans=max(ans,honest_cnt(i))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
xy = []
for _ in range(N):
    a = int(input())
    A.append(a)
    tmp = []
    for _ in range(a):
        tmp.append(tuple(map(int, input().split())))
    xy.append(tmp)
ans = 0
for i in range(2**N)[::-1]:
    is_honest = [0] * N
    for idx, c in enumerate(bin(i)[2:][::-1]):
        if c == "1":
            is_honest[idx] = 1

    flag = True
    for i in range(N):
        a = A[i]
        for j in range(a):
            x, y = xy[i][j][0], xy[i][j][1]
            if is_honest[i]:
                if is_honest[x-1] != y:
                    flag = False
                    break
        if not flag:
            break
    if flag:
        ans = max(ans, sum(is_honest))
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

N = int(input())
A = [0]*N
xy = []
for i in range(N):
    A[i] = int(input())
    xy_i = []
    for j in range(A[i]):
        xy_i.append([int(k) for k in input().split()])
    xy.append(xy_i)

ans = 0
for i in range(1, 2**N):
    nisin = str(bin(i))[2:].zfill(N)
    flag = True
    for j in range(N):
        if nisin[j] == '1':
            for k in range(A[j]):
                if ((xy[j][k][1] == 1 and nisin[xy[j][k][0]-1] == '1') or (xy[j][k][1] == 0 and nisin[xy[j][k][0]-1] == '0')):
                    flag = True
                else:
                    flag = False
                    break
        
            if (not flag):
                break
    if (flag):
        ans = max(ans, nisin.count('1'))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
tb1 = [[-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())
        tb1[i][x-1] = y
gmax = 0
for i in range(1,2**n):
    nomatch = False
    for j in range(n):
        if ((i >> j) & 1):
            nomatch = False
            for ind in range(n):
                if ind==j:pass
                else:
                    shou = False
                    resl = False
                    if tb1[j][ind] == -1:continue
                    elif tb1[j][ind] == 1:shou = True
                    elif tb1[j][ind] == 0:pass
                    if ((i>>ind)&1):resl = True
                    if shou != resl:
                        nomatch = True
                        break
        if nomatch:break
    else:
        tempstr = bin(i)
        c = tempstr.count('1')
        gmax = max(gmax,c)
print(gmax)