Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

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

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

0

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

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



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


Sample output:
2

Submission status: Accepted

Solution code:
N=int(input())
llie=[[] for i in range(N)]
ltrue=[[] for i in range(N)]
for i in range(N):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        if y==0:
            llie[i].append(x)
        else:
            ltrue[i].append(x)
ans=0
for i in range(2**N):
    dlie={}
    dtrue={}
    tmpsum=0
    f=0
    for j in range(N):
        if i&1:
            if j+1 in dlie:
                f=1
                break
            else:
                for x in llie[j]:
                    if x in dtrue:
                        f=1
                        break
                    dlie[x]=1
                for x in ltrue[j]:
                    if x in dlie:
                        f=1
                        break
                    dtrue[x]=1
                if f==0:
                    tmpsum+=1
                    dtrue[j+1]=1
                else:
                    break
        else:
            if j+1 in dtrue:
                f=1
                break
            dlie[j+1]=1
        i>>=1
    if f==0:
        ans=max(ans,tmpsum)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

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

def counter(sample):
    if sample == 0:
        return 0
    else:
        return counter(sample >> 1) + (sample & 1) #末尾が１なら１をたす

count = 0
for sample in range(2**n):
    judge = True
    for i in range(n):
        if not sample & (1 << i):
            continue
        else:
            for j in mtx[i]:
                if ((sample >> (j[0] - 1)) & 1) ^ j[1]:
                    judge = False
                    break
            if not judge:
                break
    if judge:
        count = max(count, counter(sample))
    
print(count)

Submission status: Accepted

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


for x in range(2**n):
    s=bin(x)[2:].zfill(n)
    sgn=1
    for i in range(n):
        if int(s[i])==1:
            for j in range(n):
                if d[i][j]!=-1 and d[i][j]!=int(s[j]):
                    sgn=0

                    break

        if sgn==0: break
    if sgn==1:
        tmp=sum(int(s[k]) for k in range(n))
        ans=max(ans,tmp)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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

for ans in range(n, 0, -1):
  for x in combinations(range(n), ans):
    for y in x:
      for i, z in enumerate(lst[y]):
        if (z == 1 and i not in x) or (z == -1 and i in x):
          break
      else:
        continue
      break
    else:
      break
  else:
    continue
  print(ans)
  break
else:
  print(0)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    s = format(i, "b").zfill(n)
    flag = 1
    for j in range(len(s)):
        if s[j] == "1":
            for k in range(len(v[j])):
                if v[j][k][1] == 1 and s[v[j][k][0]-1] == "0":
                    flag = 0
                    break
                if v[j][k][1] == 0 and s[v[j][k][0]-1] == "1":
                    flag = 0
                    break
    """    else:
            for k in range(len(v[j])):
                if v[j][k][1] == 1 and s[v[j][k][0]-1] == "1":
                    flag = 0
                    break
                if v[j][k][1] == 0 and s[v[j][k][0]-1] == "0":
                    flag = 0
                    break"""
    if flag == 1:
        ans = max(ans, s.count("1"))

print(ans)

Submission status: Accepted

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


count=0
for i in range(2**n):
  x=[0]*n
  pre=0
  for j in range(n):
    if ((i>>j)&1):
      x[n-1-j]=1 
      for l in range(d[j]):
        if ((i>>(a[j][l][0]-1))&1)!=a[j][l][1]:
          pre+=1
  if pre!=0:
    count=count
  else:
    count=max(count,x.count(1))
print(count)

Submission status: Accepted

Solution code:
#C - HonestOrUnkind2
import itertools
import numpy as np
 
N = int(input())
info = []
for i in range(N):
    A = int(input())
    for _ in range(A):
        x,y = map(int,input().split())
        info.append((i,x-1,y))
A = np.array(list(itertools.product([0,1],repeat=N)), np.bool)
for i,x,y in info:
    bl = (~A[:,i]) | (A[:,x] == bool(y))
    A = A[bl]
    
answer = A.sum(axis = 1).max()
print(answer)

Submission status: Accepted

Solution code:
import copy
#n桁の二進数の作成

n = int(input())
def makebin(n):

  ans = []
  for i in reversed(range(2 ** n)):
    tmp = bin(i)
    ans.append(tmp[2:].zfill(n))
  return ans
binData = makebin(n)

#入力値処理

data = {}
for i in range(n):
  a = int(input())
  alist = []
  for j in range(a):
    #タプルの生成
    x,y = list(map(int,input().split()))
    alist.append((x,y))
  #data[i] == タプルのリスト
  data[i] = alist[:]

#2進データとの比較

#2進データの要素についてループ
answer = []
flag = 1
for i in binData: #binData:n桁のbinaryのリスト
  #binaryの情報をmemoにコピー
  memo = []
  for k in range(n):
    memo.append(i[k])
  flag = 1 #flag == 0 : そのbinaryリストは矛盾
  #n文字の2進数についてループ
  for j in range(n):
    
    
    s = i[j]
    t = memo[j]
    #j番目の人がkindであるとき i:n桁のbinaryリスト
    if i[j] == '1':
      #自分自身をkindとしてmemo
      memo[j] = '1'
      #データと照合してmemoに書き込み
      #証言に矛盾がないかの分岐 
      #j番目の証言に対してループ
      for test in data[j]:
        #矛盾が生じた場合
        if (memo[test[0]-1] == '1' and test[1] == 0 ) or \
          (memo[test[0]-1] == '0' and test[1] == 1):
          flag = 0
          memo = ['0'] * n
          break

        else:
          memo[test[0]-1] = str(test[1])
      if flag == 0:
        break
    #binaryリストに対して矛盾が生じなかった場合  
  if j == n-1:
    answer.append(memo.count('1'))
print(max(answer))

Submission status: Accepted

Solution code:
n = int(input())

xy = []
a_list = []

for i in range(n):
    a = int(input())
    a_list.append(a)
    for j in range(a):
        x,y = map(int,input().split())
        xy.append([x,y])
        
#print(xy)
#print(a_list)

num = 2**n
hito = []
flag = True

for i in reversed(range(num)):
    #print(i)
    hito = []
    tmp = i
    while tmp != 0:
        if tmp % 2 == 1:
            hito.append(1)
        else:
            hito.append(0)
        tmp //= 2
    """
    if len(hito) == 2:
        hito.append(0)
    elif len(hito) == 1:
        hito.append(0)
        hito.append(0)
    elif len(hito) == 0:
        hito.append(0)
        hito.append(0)
        hito.append(0)
    """
    if len(hito) != n:
        for j in range(n-len(hito)):
            hito.append(0)
    
    hito = hito[::-1]
    #print(hito)
    
    number = 0
    flag = True
    #print(hito)
    
    for j in range(n):
        #print(j)
        for k in range(a_list[j]):
            #正しいことを言う人
            if hito[j] == 1:
                #print(number,hito[xy[number][0]] , xy[number][1])
                if hito[xy[number][0]-1] != xy[number][1]:
                    flag = False
            number += 1
    if flag == True:
        print(sum(hito))
        exit()
        
print(0)
exit()

Submission status: Accepted

Solution code:
from itertools import combinations

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

for p in range(n):
    statement = []
    for s in range(int(input())):
        statement.append(list(map(int, input().split())))
    statements.append(statement)
    

def check_statements(honesty, statements):
    for h in range(len(honesty)):
        if honesty[h] == 1:
            for s in statements[h]:
                a, b = s
                if honesty[a-1] != b:
                    return False
    return True


def main():
    for h in range(n, 0, -1):
        for i in list(combinations(range(n), h)):
            p = [0 for _ in range(n)]
            for j in i:
                p[j] = 1
            if check_statements(p, statements):
                return h
    return 0

print(main())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    aa = [[0] * n for _ in range(n)]
    for i in range(n):
        t = I()
        ta = [LI() for _ in range(t)]
        for x,y in ta:
            if y == 0:
                aa[i][x-1] = -1
            else:
                aa[i][x-1] = 1

    r = 0
    for i in range(2**n):
        f = [(i & 2**j) > 0 for j in range(n)]
        ok = True
        for j in range(n):
            if not f[j]:
                continue
            for k in range(n):
                if aa[j][k] == 0:
                    continue
                if aa[j][k] == 1:
                    if not f[k]:
                        ok = False
                else:
                    if f[k]:
                        ok = False
            if not ok:
                break

        if ok:
            t = len([_ for _ in f if _])
            if r < t:
                r =t

    return r


print(main())

Submission status: Accepted

Solution code:
import itertools
N = int(input())
item = []
for i in range(N):
    A = int(input())
    s = []
    for ii in range(A):
        x, y = map(int, input().split())
        s.append((x, y))
    item.append(s)

Ps = itertools.product([0, 1], repeat=N)
ans = 0
for P in Ps:
    right = True
    for i, p in enumerate(P):
        if p == 1:
            for x, y in item[i]:
                if (y == 1 and P[x - 1] == 0) or (y == 0 and P[x - 1] == 1):
                    right = False
    if right:
        ans = max(ans, sum(P))

print(ans)

Submission status: Accepted

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

def main():
    n = int(input())
    said = [[]] * n
    for i in range(n):
        said[i] = [list(map(int, input().split())) for _ in range(int(input()))]

    ans = 0
    n_bit = '0' + str(n) + 'b'
    for i in range(2 ** n):
        i_bin = format(i, n_bit)
        i_bin_c = i_bin.count('1')
        if i_bin_c <= ans:
            continue

        isTrue = True
        for j in range(n):
            if i_bin[j] == '0':
                continue
            for k in said[j]:
                if int(i_bin[k[0]-1]) != k[1]:
                    isTrue = False
                    break
            if not isTrue:
                break
        if isTrue:
            ans = i_bin_c
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(raw_input())
A = []
B = []
for n in range(N):
    A_i = int(raw_input())
    honest_i = set()
    unkind_i = set()
    for i in range(A_i):
        x, y =  map(int, raw_input().split())
        if y == 0:
            unkind_i.add(x-1)
        else:
            honest_i.add(x-1)
    A.append(unkind_i)
    B.append(honest_i)

def check(cand, A, B):
    honest = {i for i,v in enumerate(cand) if v == 1}
    unkind = {i for i,v in enumerate(cand) if v == 0}
    for h in honest:
        if len(honest.intersection(A[h])) != 0:
            return False
        if len(unkind.intersection(B[h])) != 0:
            return False
    return True

best = 0
import itertools
for cand in itertools.product([0,1], repeat=N):
    if check(cand, A, B):
        count = cand.count(1)
        best = max(best, count)

print best

Submission status: Accepted

Solution code:
import bisect
import heapq
import math
from copy import copy
import sys
from queue import Queue, LifoQueue, PriorityQueue
from collections import defaultdict
from operator import itemgetter

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())

    d = defaultdict(list)
    for i in range(N):
        A = int(readline())
        for _ in range(A):
            x, y = map(int, readline().split())                
            d[i].append((x-1, y))
            
    ret = 0
    for i in range(2 ** N):
        contradiction = False
        for j in range(N):
            for x, y in d[j]:
                # 証言が正しい時のみ矛盾を考慮　証言が真偽不明な時は考えない
                if (i >> j) & 1:
                    if (i >> x) & 1:
                        if y == 0:
                            contradiction = True
                            break
                    else:
                        if y == 1:
                            contradiction = True
                            break

        if contradiction:
            continue
        else:
            ret = max(bin(i).count("1"), ret)

    print(ret)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 0
for i in range(1<<n):
    use = []
    for bit in range(n):
        if i&(1<<bit):
            use.append(bit+1)

    judge = True
    for j in use:
        for x,y in data[j-1]:
            if x in use and y == 0:
                judge = False
                break
            if x not in use and y == 1:
                judge = False
                break

    if judge:
        ans = max(ans,len(use))

print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
A = [0] * N
xy_list = [0] * N
for i in range(N):
    A[i] = int(input())
    xy = [0] * A[i]
    for j in range(A[i]):
        xy[j] = tuple(int(x) for x in input().split())
    xy_list[i] = xy

m = 0
for p in itertools.product([0, 1], repeat=N):
    for i in range(N):
        if p[i] == 0:
            continue
        for j in range(A[i]):
            x, y = xy_list[i][j]
            if p[x - 1] != y:
                break
        else:
            continue
        break
    else:
        s = sum(p)
        if s > m:
            m = s
print(m)

Submission status: Accepted

Solution code:
N = int(input())
g = [[-1]*N for i in range(N)] #何も証言していないのを-1。i番目の人がj番目の人を正直ものといっているか、不親切といっているか、なにもいってないか。

for i in range(N):
    A = int(input())
    for j in range(A):
        a,x = map(int, input().split())
        a -= 1
        g[i][a] = x
ans = 0
for i in range(1 << N):
    d=[0]*N
    for j in range(N):
        if (i>>j & 1):
            d[j] = 1
    ok = True
    for j in range(N):
        if d[j]: #正直者だと割り当てをした人を見る
            for k in range(N):
                if g[j][k] == -1: continue
                if g[j][k] != d[k]: ok = False #jの人の証言が、実際の割り当てとあっているかどうかを判断
    if ok:
        ans = max(ans, bin(i).count("1"))
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
 
N = int(input())
info = []
for i in range(N):
    A = int(input())
    for _ in range(A):
        x,y = map(int,input().split())
        info.append((i,x-1,y))
A = np.array(list(itertools.product([0,1],repeat=N)), np.bool)
for i,x,y in info:
    bl = (~A[:,i]) | (A[:,x] == bool(y))
    A = A[bl]
    
answer = A.sum(axis = 1).max()
print(answer)

Submission status: Accepted

Solution code:
def checker(bbit,listN,N):
    i = 0
    j = 0
    ng = False
    #print(N)
    #print(listN)
    #print(bin(bbit))
    while N > i :
        j=0
        checkFig = 3
        ibit = 1 << i
        while N > j :
            cbit = 1 << j
            if bbit & cbit == 0 :
                #print("A:{} {}".format(j,i))
                pass
            elif listN[j][i] == 3 :
                #print("B:{} {}".format(j,i))
                pass
            elif (listN[j][i] == 0) and (bbit & ibit != 0):
                ng = True
                break
            elif (listN[j][i] == 1) and (bbit & ibit == 0):
                ng = True
                break
            elif checkFig == 3 :
                #print("C:{} {}".format(j,i))
                checkFig = listN[j][i]
            elif checkFig != listN[j][i] :
                ng = True
                #print("D:{} {}".format(j,i))
                break
            j += 1
        if ng :
            #print(ng)
            break
        else :
            i +=1
    return (not ng)


def main():
    N = int(input())
    listA = [[3 for j in range(N)] for k in range(N)]
    n = 0
    while N > n :
        a = int(input())
        i = 0
        while a > i:
           x,y  = map(int,input().split())
           listA[n][x-1] = y
           i += 1
        n += 1
        
    honestBit = pow(2, N)-1
    honest = 0
    
    while honestBit > 0:
        ok = checker(honestBit,listA,N)
        if ok :
            okbit = honestBit
            oknum = 0
            while okbit > 0 :
                oknum += (okbit % 2) 
                okbit = okbit >> 1
            if oknum > honest :
                honest = oknum 
        honestBit -= 1
    print(honest)
    

main()

Submission status: Accepted

Solution code:
N = int(input())
A = [None]*N
x = [[None]*N for _ in range(N)]
y = [[None]*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())
        

ans =0
for num in range(2**N):
    #bit = bin(num)#正直者リスト
    flag = 1 #これが1のままならOK
    
    #N人を順に見る
    for i in range(N):
        #下からi桁目を取り出す
        if (num>>i & 1)==1:#正直者なら検討
            
            #各発言に対して，NGケースを調査
            for j in range(N):
                #xijの対応に注意，文章では1から
                if x[i][j] != None and y[i][j]!=(num>>(x[i][j]-1) & 1):
                    flag = 0
                elif x[i][j] == None:
                    break
        if flag ==0:
            break
    if flag ==1:
        ans = max(ans,bin(num).count("1"))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [None]*N
x = [[None]*N for _ in range(N)]
y = [[None]*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())
        

ans =0
for num in range(2**N):
    #bit = bin(num)#正直者リスト
    flag = 1 #これが1のままならOK
    
    #N人を順に見る
    for i in range(N):
        #下からi桁目を取り出す
        if (num>>i & 1)==1:#正直者なら検討
            
            #各発言に対して，NGケースを調査
            for j in range(N):
                #xijの対応に注意，文章では1から
                if x[i][j] != None and y[i][j]!=(num>>(x[i][j]-1) & 1):
                    flag = 0
        if flag ==0:
            break
    if flag ==1:
        ans = max(ans,bin(num).count("1"))
print(ans)

Submission status: Accepted

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

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


def judge(bit: int) -> bool:
    for i in range(N):
        if not (bit & (1 << i)):
            continue

        for x, y in testimony[i]:
            if ((bit >> x) & 1) ^ y:
                return False

    return True


def main() -> None:
    res = 0
    for bit in range(1 << N):
        count = 0
        if judge(bit):
            for i in range(N):
                if bit & 1 << i:
                    count += 1
            res = max(res, count)

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
numbers = list(map(int, input().split()))
n = numbers[0]

v = []

for i in range(n):
    numbers = list(map(int, input().split()))
    a = numbers[0]
    
    w = []
    
    for j in range(a):
        z = list(map(int, input().split()))
        w.append(z)
        
    v.append(w)
    
rezultat = 0

max_steps = 2 ** n

for i in range(max_steps):
    w = [-1] * n
    
    for j in range(n):
        if i >> j & 1:
            w[j] = 1
        else:
            w[j] = 0
    
    ok = 1
    
    for j in range(n):
        if ok == 0:
            break
        for a, b in v[j]:
            if w[j] == 1:
                a = a - 1
                if w[a] != b:
                    ok = 0
                    break
                
    if ok:
        rezultat = rezultat if rezultat > sum(w) else sum(w)
        
print(rezultat)

Submission status: Accepted

Solution code:
n = int(input())
g = [[] for i in range(n)]
for i in range(n):
    m = int(input())
    for j in range(m):
        g[i].append([int(x) for x in input().split()])
res = 0
for i in range(2 ** n):
    bit = i
    hypothesis = []
    for j in range(n):
        hypothesis.append(bit % 2)
        bit //= 2
    bit = i
    k = 0
    flag = True
    while bit > 0:
        if bit % 2 == 1:
            for s in g[k]:
                if hypothesis[s[0] - 1] != s[1]:
                    flag = False
        bit >>= 1
        k += 1
    if flag:
        if sum(hypothesis) > res:
            res = sum(hypothesis)
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    # 証言を有向グラフで管理，-1：証言なし
    graph = [[-1 for _ in range(n)] for _ in range(n)]

    for i in range(n):
        ai = int(input())

        for _ in range(ai):
            xi, yi = map(int, input().split())
            # 0-indexだと実装が楽に
            xi -= 1
            graph[i][xi] = yi

    ans = 0

    # See:
    # https://www.youtube.com/watch?v=tNyPYIhy9Ms&feature=youtu.be
    # KeyInsight：
    # あるパターンを決め打って，条件を満たすかどうかを判定する
    # 0/1で何を表現するか=>正直な人を1，不親切な人を0と割り当てる
    # 不親切な人=嘘つきではない

    # できた部分：正直な人と不親切な人をbitで割り当てて，全探索
    # できなかった部分: 正直な人と不親切な人の判定

    # bit全探索
    # ある人について，0/1を全て試す2^n通り
    for bit in range(1 << n):
        d = [0 for _ in range(n)]

        for j in range(n):
            # 0 1 0 0 1 ・・・のように，正直な人と不親切な人の集合を作成している
            # あるパターンのときにjビット目が1かどうかを判定
            if (bit >> j) & 1:
                d[j] = 1

        is_ok = True

        # 正直な人の証言が全て矛盾していないかを判断
        # 不親切な人の証言は判定しなくてもよいのがポイント
        for j in range(n):
            if d[j] == 1:
                for k in range(n):
                    # 該当する証言がない
                    if graph[j][k] == -1:
                        continue

                    # 証言とパターンの比較
                    if graph[j][k] != d[k]:
                        is_ok = False

        # 正直な人の最大値を更新
        if is_ok:
            ans = max(ans, sum(d))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    graph = [[-1 for _ in range(n)] for _ in range(n)]

    for i in range(n):
        ai = int(input())

        for _ in range(ai):
            xi, yi = map(int, input().split())
            xi -= 1
            graph[i][xi] = yi

    ans = 0

    # bit全探索
    for bit in range(1 << n):
        d = [0 for _ in range(n)]

        for j in range(n):
            if (bit >> j) & 1:
                d[j] = 1

        is_ok = True

        for j in range(n):
            if d[j] == 1:
                for k in range(n):
                    if graph[j][k] == -1:
                        continue

                    if graph[j][k] != d[k]:
                        is_ok = False

        if is_ok:
            ans = max(ans, sum(d))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
syougen={}
for i in range(n):
    a=int(input())
    syougen[i+1]=[[],[]]

    for j in range(a):
        x,y=map(int,input().split())
        if y==1:
            syougen[i+1][0].append(x)
        else:
            syougen[i+1][1].append(x)

result=0

for i in range(2**n):
    sei=set([])
    ayamari=set([])

    for j in range(n):
        if((i>>j)&1):
            sei=sei|(set(syougen[j+1][0]))|set([j+1])
            ayamari=ayamari|(set(syougen[j+1][1]))

    if sei.isdisjoint(ayamari):
        flag="true"
        cnt=0
        for j in range(n):
            if((i>>j)&1):
                cnt+=1
                if j+1 not in sei:
                    flag="fales"
                    
        if flag=="true" and cnt==len(sei):
            result=max(result,len(sei))
print(result)


#print(syougen)

Submission status: Accepted

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

N = int(input())
A = [0]*N
evidences = []
for i in range(N):
    A[i] = int(input())
    e = [[int(i) for i in input().split()] for i in range(A[i])] 
    evidences.append(e)

combs = list(itertools.product(range(2), repeat=N))
table = [2]*N
maxtrue = 0

#print(table)
for comb in combs:
    c = list(comb)
    for i in range(N):
        if c[i] == 0:
            continue
        for evids in evidences[i]:
            if c[evids[0]-1] == evids[1]:
                continue
            else:
                break
        else:
            continue
        break
    else:
        #print(c)
        if maxtrue < c.count(1):
            maxtrue = c.count(1)
print(maxtrue)

Submission status: Accepted

Solution code:
N = int(input())
syougen = [[] for _ in range(N)]
for _ in range(N):
    kosuu = int(input())
    for i in range(kosuu):
        syougen[_].append([int(x) for x in input().split(" ")])
num = 0
for i in range(2 ** N):
    bit = i
    hypothesis = []
    for _ in range(N):
        hypothesis.append(bit % 2)
        bit //= 2
    bit = i
    k = 0
    flag = True
    while bit > 0:
        if bit % 2 == 1:
            for s in syougen[k]:
                if hypothesis[s[0] - 1] != s[1]:
                    flag = False
        bit >>= 1
        k += 1
    if flag:
        if sum(hypothesis) > num:
            num = sum(hypothesis)
print(num)

Submission status: Accepted

Solution code:
n = int(input())
g = [[-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())
    g[i][x-1] = y

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

print (ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

g = [[-1]*N for i in range(N)]

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

ans = 0
for i in range(1<<N):
    d = [0]*N
    for j in range(N):
        if i>>j&1:
            d[j]=1
    ok = True
    for j in range(N):
        if d[j]:
            for k in range(N):
                if g[j][k] == -1:
                    continue
                if g[j][k] != d[k]:
                    ok=False
    if ok:
        ans = max(ans, bin(i).count("1"))

print(ans)

Submission status: Accepted

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

ans = 0

for i in range(2**n):
  ok = 1
  count = 0
  for j in range(n):
    if not ((i >> j) & 1):
      continue
    else:
      count += 1
      for k in range(len(x_arr[j])):
        if y_arr[j][k] == 0 and ((i >> x_arr[j][k]) & 1):
          ok = 0
        if y_arr[j][k] == 1 and (not ((i >> x_arr[j][k]) & 1)):
          ok = 0
  if ok:
    ans = max(ans,count)
    
print(ans)

Submission status: Accepted

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

max_honest = 0
for i in range(2 ** n):
    bin_i = format(i, '015b')[::-1]
    ok = True

    for j in range(n):
        for x, y in xys[j]:
            if bin_i[j] == "1" and y != int(bin_i[x - 1]):
                ok = False
                break
        else:
            continue
        break

    if ok:
        honest = sum(int(x) for x in bin_i)
        max_honest = max(max_honest, honest)

print(max_honest)