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())
A = [0]*N
X = []
for i in range(N):
    A[i] = int(input())
    t = []
    for j in range(A[i]):
        t.append(tuple(map(int, input().split())))
    X.append(t)
    
ans = 0
for i in range(2**N):
    Flg = True
    cnt = 0
    for j in range(N):
        if((i>>j)&1): 
            for m in range(A[j]):
                x, y = X[j][m]
                if((i>>(x-1))&1 != y):
                    Flg = False
                    break
    if(Flg):
        ans = max(ans, bin(i).count("1"))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * 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]):
        k, l = map(int, input().split())
        x[i].append(k)
        y[i].append(l)

def dfs(cur, l):
    global ok
    if cur == n:
        ok = True
        for i in range(n):
            if l[i]==1 and any([l[x[i][j]-1]!=y[i][j] for j in range(a[i])]):
                ok = False
        return sum(l) if ok else 0
    else:
        l1 = l[:]
        l1[cur] += 1
        return max(dfs(cur+1, l), dfs(cur+1, l1))

print(dfs(0, [0]*n))

Submission status: Accepted

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

for i in range(n): #証言者 i人目
    a = int(input())
    for j in range(a): #i人目の証言者のj番目の証言
        x, y = map(int, input().split())
        xy[i].append([x, y])

for b in range(1 << n): #設定上、正直者か不親切かの全パターンを探索
    cnt = bin(b).count("1") #正直者設定の人数をカウント
    judge = True
    for i in range(n):
        if judge == False:
            break
        if b & (1 << i) != 0: #i番目の証言者が正直者設定の場合
            for x, y in xy[i]:
                if y == 1 and b & (1 << x - 1) == 0:
                    #証言:正直者、設定:不親切の場合
                    judge = False
                if y == 0 and b & (1 << x - 1) != 0:
                    #証言:不親切、設定:正直者の場合
                    judge = False
    if judge == True:
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = [[] for i in range(n)]

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

ans = 0

for b in range(1 << n): # 正直者か不親切か全ての設定パターンを作る。
    cnt = bin(b).count("1")
    judge = True
    for j in range(n):
        if judge == False: #矛盾があれば、ループを止める。
            break
        if b & (1 << j) != 0: # j番目の人が正直者設定なら進む。
            for x, y in l[j]:
                if y == 1 and b & (1 << x - 1) == 0: # 証言:正直者、設定:不親切の場合
                    judge = False
                if y == 0 and b & (1 << x - 1) != 0: # 証言:不親切、設定:正直者の場合
                    judge = False
    if judge == True:
        ans = max(cnt, ans)
print(ans)

Submission status: Accepted

Solution code:
def judge(bit):
    for i in range(N):
        if not(bit & (1 << i)):
            continue
        for xy in v[i]:
            x = xy[0] 
            y = xy[1]
            if y == 1 and not(bit & (1 << x)):
                return False
            if y == 0 and (bit & (1 << x)):
                return False
    return True

N = int(input())
v = []
for i in range(N):
    A = int(input())
    array = []
    for i in range(A):
        a,b = map(int, input().split())
        a-=1 
        array.append((a,b))
    v.append(array)

res = 0
for bit in range(1 << N):
    if judge(bit):
        count = bin(bit).count("1")
        res = max(res, count)
    
print(res)

Submission status: Accepted

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

person = [0]*(N)
c = 0

for i in range(2 ** N):
  person = [0]*(N)
  for j in range(N):
    if ((i >> j) & 1):
      person[j] = 1
  cc = sum(person)
  for j in range(N):
    if person[j] == 1:
      for k in range(A[j]):
        p = xy[j][k]
        if person[p[0]-1] != p[1]:
          #out!
          cc = 0
  c = max(c,cc)  


print(c)

Submission status: Accepted

Solution code:
import copy
from itertools import permutations, product

n = int(input())
al = []
xyl = []
for i in range(n):
    a = int(input())
    al.append(a)
    tl = []
    for j in range(a):
        t = [int(i) for i in input().split()]
        tl.append(t)
    xyl.append(tl)

l = [i for i in product([0, 1], repeat=n)]

ans_list = []

for ll in l:
    ans_flag = 1
    for i in range(n):
        flag = 1
        for j in range(al[i]):
            if ll[xyl[i][j][0]-1] != xyl[i][j][1]:
                flag = 0
        if flag != ll[i]:
            ans_flag = 0
    if ans_flag == 1:
        ans_list.append(copy.deepcopy(ll))

ans = 0
for i in ans_list:
    k = i.count(1)
    if ans < k:
        ans = k

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = [[] for i in range(n)]

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

ans = 0

for b in range(1 << n): # 1をn桁分、左にシフト(2進数)
    cnt = bin(b).count("1")
    ok = True
    for j in range(n):
        if ok == False:
            break
        if b&(1 << j) != 0:
        # 論理積(同じ桁のビットで共通の桁があればok)
        # j番目の人が正直者設定であれば、先に進む
            for x, y in xy[j]: # j人目の人の証言
                if y == 1 and b&(1 << x - 1) == 0:
                # 正直者と証言された人が正直者設定でない場合
                    ok = False
                if y == 0 and b&(1 << x - 1) != 0:
                # 不親切と証言された人が不親切設定でない場合
                    ok = False
    if ok == True:
        ans = max(cnt, ans)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
people=[]
test=[]
for i in range(N):
    a=int(input())
    bufs=[list(map(int,input().split())) for _ in range(a)]
    test.append(bufs)
#print(test)
num=0
for i in range(pow(2,N)):
    flag=1
    flag2=1
    truthtable=[0]*N
    honestunkind=[-1]*N
    for j in range(N):
        if (i>>j)&1:
            truthtable[j]=1
    #print(truthtable)#正直者なら0,嘘つきなら1のtable
    for j in range(N):
        if truthtable[j]==0:
            for k in test[j]:
                people=k[0]-1
                horu=k[1]
                if honestunkind[people]==-1:
                    honestunkind[people]=(horu+truthtable[j]+1)%2
                else:
                    if honestunkind[people]!=(horu+truthtable[j]+1)%2:
                        flag=0
                        break
            if flag==0:
                break
    if flag==1:
        for j in range(N):
            if (truthtable[j]!=honestunkind[j])and(honestunkind[j]!=-1):
                flag2=0
                break
        if flag2==1:
            #print(truthtable,honestunkind)
            num=max(num,truthtable.count(0))
        #print(num,truthtable)
print(num)

Submission status: Accepted

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

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

res = 0
for i in range(2 ** N):
    cnt = 0
    for j in range(N):
        ok = True
        if i >> j & 1:
            cnt += 1
            for k in range(len(xy[j])):
                if (i >> (xy[j][k][0] - 1) & 1) != xy[j][k][1]:
                    ok = False
                    break
        if ok == False:
            cnt = 0
            break
    res = max(res, cnt)
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
chk = [[set(),set()] for _ in range(n)]
for o in range(n):
  a = int(input())
  for i in range(a):
    x,y = [int(i) for i in input().split()]
    if y == 0:
      chk[o][0].add(x-1)
    if y == 1:
      chk[o][1].add(x-1)
    
chk = tuple(chk)
answer = 0
for i in range(2**n):
  b = format(i,'b')
  b = b.zfill(n)[::-1]
  chk_0 = set()
  chk_1 = set()
  p = []
  for j in range(n):
    if b[j] == '1':
      p.append(j)
      chk_1.add(j)
    if b[j] == '0':
      chk_0.add(j)
  for i in p:
    if not chk[i][0] <= chk_0:
      break
    if not chk[i][1] <= chk_1:
      break
    if i == p[len(p)-1]:
      answer = max(answer,len(p))
      
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
chk = [[set(),set()] for _ in range(n)]
for o in range(n):
  a = int(input())
  for i in range(a):
    x,y = [int(i) for i in input().split()]
    if y == 0:
      chk[o][0].add(x-1)
    if y == 1:
      chk[o][1].add(x-1)
    
chk = tuple(chk)
answer = 0
for i in range(2**n):
  b = format(i,'b')
  b = b.zfill(n)[::-1]
  chk_0 = set()
  chk_1 = set()
  p = []
  for j in range(n):
    if b[j] == '1':
      p.append(j)
      chk_1.add(j)
    if b[j] == '0':
      chk_0.add(j)
  #print(b,p,chk_0,chk_1)
  for i in p:
    #print(chk[i][0],chk[i][1])
    if not chk[i][0] <= chk_0:
      break
    if not chk[i][1] <= chk_1:
      break
    if i == p[len(p)-1]:
      #print('!')
      answer = max(answer,len(p))
      
print(answer)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    tl = [[-1] * n for _ in range(n)]  # Testimonies list.
    for i in range(n):
        ts = int(input())
        for _ in range(ts):
            x, y = [int(x) for x in input().split()]
            x -= 1
            tl[i][x] = y  # i says that x is y.
    ans = set()
    for i in range(2 ** n):
        pl = [i >> d & 1 for d in range(n)]
        possible = True
        for k, p in enumerate(pl):
            if not possible:
                break
            if p != 1:
                continue
            # is honest.
            for j, t in enumerate(tl[k]):
                if t == -1:
                    continue
                if t != pl[j]:
                    possible = False
                    break
        if possible:
            ans.add(bin(i).count('1'))
    return max(ans)


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N=int(input())

g=[[-1 for n in range(N)] for m in range(N)]

for n in range(N):
    A=int(input())
    for m in range(A):
        x,y=map(int,input().strip().split())
        g[x-1][n]=y

def c(n,N,base):
    S=[0 for i in range(N)]
    for i in range(N):
        S[i]=n%base
        n=n//base
    return S


def honest_judge(S,g):
    honest=True
    for n in range(len(S)):
        if S[n]==1:
            for i in range(N):
                if g[i][n]!=-1 and g[i][n]!=S[i]:
                    honest=False
        if honest==False:
            break
    return honest

MAX=0
for n in range(2**N):
    S=c(n,N,2)
    if honest_judge(S,g)==True:
        if sum(S)>=MAX:
            MAX=sum(S)

print(MAX)

Submission status: Accepted

Solution code:
n=int(input())
xy=[[] for i in range(n)]
for i in range(n):
  a=int(input())
  for j in range(a):
    x,y=map(int,input().split())
    xy[i].append([x,y])
ans=0
for b in range(1<<n):
  cnt=bin(b).count("1")
  ok=True
  for j in range(n):
    if not ok:break
    if b&(1<<j):
      for x,y in xy[j]:
        if y==1 and b&(1<<x-1)==0:ok=False
        if y==0 and b&(1<<x-1):ok=False
  if ok:
    ans=max(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
xy=[[] for i in range(n)]
for i in range(n):
  a=int(input())
  for j in range(a):
    x,y=map(int,input().split())
    xy[i].append([x,y])
ans=0
for b in range(1<<n):
  cnt=bin(b).count("1")
  if cnt<=ans:continue
  for j in range(n):
    if b&(1<<j):
      for x,y in xy[j]:
        if y==1 and b&(1<<x-1): continue
        if y==0 and b&(1<<x-1)==0: continue
        break
      else:
        continue
      break
  else:
    ans=cnt
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    for j in range(n):
        if ((i >> j) & 1) == 1:
            for k,l in a[j]:
                if ((i >> (k-1)) & 1) != l:
                    break
            else:
                continue
            break
    else:
        ans = max(ans,bin(i).count('1'))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = []
for k in range(N):
    t = []
    for l in range(int(input())):
        x, y = map(int,input().split())
        t.append([x-1,y])
    L.append(t)
ans = 0
for k in range(2**N):
    t = []
    for d in range(N):
        if (k>>d)&1:
            t.append(d)
    flag = 1
    for e in t:
        for f in L[e]:
            if f[0] in t and f[1] == 0:
                flag = 0
                break
            if f[0] not in t and f[1] == 1:
                flag = 0
                break
    ans = max(ans,flag*len(t))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for i in range(n):
    x=int(input())
    b=[[int(i) for i in input().split()] for i in range(x)]
    a.append(b)

ans=0

for i in range(2**n):
    status=[True]*n
    for j in range(n):
        if ((i>>j)&1):
            status[j]=False
    
    judge=[None]*n
    contradiction=False
    
    for x,person in enumerate(a):
        if status[x]==False:
            continue
        for testimony in person:
            if testimony[1]==1: 
                if judge[testimony[0]-1]!=False and status[testimony[0]-1]==True:
                    judge[testimony[0]-1]=True
                else:
                    contradiction=True
            else:
                if judge[testimony[0]-1]!=True and status[testimony[0]-1]==False:
                    judge[testimony[0]-1]=False
                else:
                    contradiction=True

    if contradiction==False:
        ans=max(ans,status.count(True))
print(ans)

Submission status: Accepted

Solution code:
#入力
n = int(input())
A = []
for i in range(n):
  A.append([])
  A[i].append(int(input()))
  for j in range(A[i][0]):
    A[i].append([int(_) for _ in input().split()])
    
def bit_count(num):
  cc = 0
  while num:
    cc += num & 1
    num >>= 1
  return cc

#bit全探索
res = 0
for bit in range(2 ** n):
  for i in range(n): #i番目の人の発言について検証
    if ((bit >> i) & 1) == 0: #i番目の人が正直者かそうでないか
      continue
    for j in range(A[i][0]):
      x, y = A[i][j+1]
      if (bit >> (x-1)) & 1 != y:
        break
    else:
      continue
    break
  else:
    res = max(res, bit_count(bit))
print(res)

Submission status: Accepted

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

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

ans = 0
for p in range(1 << n):
    cnt = 0
    is_not = False
    for i in range(n):
        if p >> i & 1:
            cnt += 1
            for ti in t[i]:
                x, y = ti
                if (p >> x & 1) != y:
                    is_not = True
                    cnt = 0
                    break
        if is_not:
            break
    ans = max(ans, cnt)
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())

ans = 0
 
for i in range(2**N):
    bit = bin(i)[2:].zfill(N)
    checked = 1
    for j in range(N):
        if bit[j] == "1":
            for k in range(A[j]):
                if int(bit[x[j][k] - 1]) != y[j][k]:
                    checked = 0
                    break
    if checked == 1:
        ans = max(ans, bit.count("1"))
 
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)]

#input
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

# 1: 正直者 0: 不親切
for i in range(2**N):
    bit = bin(i)[2:].zfill(N)
    # 検証
    checked = 1
    for j in range(N):
        if bit[j] == "1":  # j が正直者のとき
            for k in range(A[j]):
                if int(bit[x[j][k] - 1]) != y[j][k]:
                    checked = 0
                    break
    if checked == 1:
        ans = max(ans, bit.count("1"))

print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

#0埋め　桁合わせ
def digit(n, r):
    n = str(n)
    l = len(n)
    for i in range(r - l):
        n = '0' + n
    return n

def solv(i):
    global honest, flag
    tmp = []
    for j in range(len(arr[i])):
        if honest[arr[i][j][0] - 1] == arr[i][j][1]:
            pass
        else:
            flag = False
            break

n = INT()
arr = []
for _ in range(n):
    a = INT()
    arr.append([LIST() for _ in range(a)])
ans = 0
for i in range(2 ** n):
    bitstr = digit(bin(i)[2:], n)
    honest = [int(i) for i in bitstr]
    flag = True
    for j in range(n):
        if honest[j]:
            solv(j)
        if not flag:
            break
    debug(flag, honest)
    if flag:
        ans = max(ans, honest.count(1))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

S = []
for _ in range(N):
    A = int(input())
    S.append([tuple(map(int, input().split())) for _ in range(A)])

def sol(state):
    for i, A in enumerate(S):
        if (state & (1 << i)) == 0:
            continue
        for j, s in A:
            if ((state & (1 << (j - 1))) != 0) != (s != 0):
                return 0
    return sum(map(int, bin(state)[2:]))

ans = 0
for state in range(1 << N):
    ans = max(ans, sol(state))
print(ans)

Submission status: Accepted

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

result = [0]
for i in range(1, 2**n):
    h = format(i, "0"+str(n)+"b")
    c = [int(j) for j in list(h)]
    checker = True
    for j in range(n):
        if c[j]:
            for x, y in a[j]:
                if c[x-1]!=y:
                    checker = False
                    break
    if checker:
        result.append(c.count(1))
print(max(result))

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    G=[[] for _ in range(N)]
    for i in range(N):
        A=int(input())
        for _ in range(A):
            x,y=map(int, input().split())
            x=x-1
            G[i].append((x,y))

    ans=0
    for p in range(1<<N):
        s=[0]*N
        tmp=0
        for i in range(N):
            if p&(1<<i):
                s[i] = 1
                tmp+=1
        for i in range(N):
            if s[i]==0: continue
            for x,y in G[i]:
                if s[x]!=y: break
            else:
                continue
            break
        else:
            ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    t = [-1]*n
    flag = True
    cnt = 0
    for j in range(n):
        if (i >> j) & 1:
            cnt += 1
            t[j] = 1
        else:
            t[j] = 0
    for j in range(n):
        if (i >> j) & 1:
            for x, y in X[j]:
                if t[x] != y:
                    flag = False
    if flag:
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

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

ans = 0
for b in range(1<<N):
    cnt = bin(b).count('1')
    if cnt <= ans: continue
    for i in range(N):
        if b&(1<<i):
            for x,y in xys[i]:
                if y==1 and b&(1<<x): continue
                if y==0 and b&(1<<x)==0: continue
                break
            else:
                continue
            break
    else:
        ans = cnt
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
people=[None]*n
for i in range(n):
  a=int(input())
  people[i]=[tuple(map(int,input().split())) for k in range(a)]
ans=0
for i in range(2**n):
  shoujiki=[]
  div=i
  flg=0
  for j in range(n)[::-1]:
    s=div//(2**j)
    div%=2**j
    if s:shoujiki.append(j)
  for k in shoujiki:
    for lk in people[k]:
      if (lk[0]-1 in shoujiki and lk[1]==0) or (lk[0]-1 not in shoujiki and lk[1]==1):flg=1
  if not flg:
    if len(shoujiki)>ans:ans=len(shoujiki)
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2 ** N):
    S = format(i, 'b').zfill(N)
    flag = True
    for j in range(N):
        if S[j] == '1':
            for x, y in M[j]:
                if S[x - 1] != y:
                    flag = False
    if flag:
        ans = max(ans, S.count('1'))
print(ans)

Submission status: Accepted

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

def main():
    ans = 0
    N = int(input())
    test = []
    for _ in range(N):
        A = int(input())
        temp = [tuple(map(int, input().split())) for _ in range(A)]
        test.append(temp) 
    
    # bit full search
    print()
    for bit in range(1<<N):
        isOK = True
        for i in range(N):
            if bit & (1<<i):
                for j, flag in test[i]:
                    j -= 1
                    if flag ^ ((bit>>j) & 1):
                        isOK = False
                        break
        if isOK:
            ans = max(ans, bin(bit).count("1"))
    
    print(ans)

            
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

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

honest = 0

# bit全探索
for i in range(2 ** N):
    flag = True
    for j in range(N):
        if ((i >> j) & 1) == 1:
            # bitが立っている箇所に対して処理。つまり,人jが正直者だとしたとき、
            # その人の発言と、矛盾していないか判定
            for x, y in status[j]: # 人jの証言            
                if ((i >> x) & 1) != y:
                    flag = False
                    break
    if flag:
        honest = max(honest, bin(i)[2:].count('1'))  # 0bが先頭につくため

print(honest)

Submission status: Accepted

Solution code:
N = int(input())
honest = []
unkind = []

for _ in range(N):
    h_state = []
    u_state = []
    for __ in range(int(input())):
        x, y = map(int, input().split())
        if y == 1:
            h_state.append(x-1)
        else:
            u_state.append(x-1)
    honest.append(h_state)
    unkind.append(u_state)

ans = 0
    
for pattern in range(1 << N):
    for person in range(N):
        is_honest = pattern & 2**person > 0
        if not is_honest:
            continue
        doubt = False
        for tar in honest[person]:
            if not pattern & 2**tar > 0:
                doubt = True
        
        for tar in unkind[person]:
            if pattern & 2**tar > 0:
                doubt = True
        
        if doubt:
            break
        
    else:
        count = 0
        for person in range(N):
            if pattern & 2**person:
                count += 1
        ans = max(ans, count)

print(ans)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
N = int(input())
A = [0]*N
says = [[-1]*(N+1) for _ in range(N+1)]
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        x,y = inputlist()
        says[i+1][x] = y

suma = sum(A)

ans = 0

for i in range(2**N):
    bn = bin(i)
    bn = bn[2:]
    if len(bn) < N:
        for s in range(N-len(bn)):
            bn = '0' + bn
    flag = True
    for x in range(N):
        if bn[x] == '1':
            for y in range(N):
                if says[x+1][y+1] == -1:
                    continue
                if says[x+1][y+1] != int(bn[y]):
                    flag = False
                    break

    if flag:
        c = 0
        for i in range(N):
            if bn[i] == '1':
                c+=1
        ans = max(c,ans)

print(ans)

Submission status: Accepted

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

can_be = []
for i in itertools.product('01', repeat=n):
    people = tuple(map(int, i))
    contradiction = 0
    for j in range(n):
        if people[j] == 0:
            continue
        for k, x in statements[j]:
            if people[k] == x:
                continue
            contradiction = 1
            break
        if contradiction:
            break
    else:
        can_be.append(people)

ans = 0
for p in can_be:
    ans = max(ans, p.count(1))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A, x, y = [], [], []
for i in range(N):
    A.append(int(input()))
    x_, y_ = [], []
    for j in range(A[i]):
        x__, y__ = map(int, input().split())
        x_.append(x__ - 1)
        y_.append(y__)
    x.append(x_)
    y.append(y_)
ans = 0
for i in range(2 ** N):
    t = 1
    for j in range(N):
        if not i & (1 << j):
            continue
        for a, b in zip(x[j], y[j]):
            if b == 1 and not i & (1 << a):
                t = 0
                break
            if b == 0 and i & (1 << a):
                t = 0
                break
        if not t:
            break
    if t:
        ans = max(ans, bin(i).count("1"))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n=int(input())
d=defaultdict(list)

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

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

res=0
for i in range(1<<n):
    bf=False
    for j in range(n):

        if (i>>j)&1 == 1:
            for x,y in d[j]:
                if (i>>x)&1 != y: 
                    bf=True
                    break
            if bf:break 

    if not bf:
        count=0
        for m in range(n):
            if (i & (1 << m)) : count+=1
            res=max(res,count)
        # res=max(res,bin(i).count("1"))

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict

n=int(input())
d=defaultdict(list)

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

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

res=0
for i in range(1<<n):
    bf=False
    for j in range(n):

        if (i>>j)&1 == 1:
            for x,y in d[j]:
                if (i>>x)&1 != y: 
                    bf=True
                    break
            if bf:break 

    if not bf:
        # count=0
        # for m in range(n):
        #     if (i & (1 << m)) : count+=1
        #     res=max(res,count)
        res=max(res,bin(i).count("1"))

print(res)

Submission status: Accepted

Solution code:
from itertools import product as pro

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

ans = 0
for l in pro([0, 1], repeat=n):
    for i, t in enumerate(l):
        if t == 1:
            if not all(l[x-1] == y for x, y in xy[i]):
                break
    else:
        ans = max(ans, sum(l))

print(ans)

Submission status: Accepted

Solution code:
from itertools import product as pro

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

ans = 0
for l in pro([0, 1], repeat=n):
    for i, t in enumerate(l):
        if t == 1:
            if not all(l[x-1] == y for x, y in xy[i]):
                break
    else:
        ans = max(ans, sum(l))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
state_ls_ls = [0] * n
a_ls = [0] * n
for i in range(n):
    a = int(input())
    a_ls[i] = a
    state_ls = [list(map(int, input().split())) for _ in range(a)]
    state_ls_ls[i] = state_ls

num_pat = 2 ** n
ans = 0
for i in range(num_pat):
    pattern = [0] * n
    for j in range(n):
        if ((i>>j)&1):
            # 1は正直者
            pattern[j] = 1
    # 以下矛盾ないか検証
    TF = True
    # patternで「正直」がいたら検証
    for k in range(n):
        if pattern[k] == 1:
            for l in range(a_ls[k]):
                st_person, st_kind = state_ls_ls[k][l]
                st_person -= 1
                if pattern[st_person] != st_kind:
                    TF = False
    if TF:
        ans = max(ans, pattern.count(1))
print(ans)