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())
lst = []
ans = 0
for i in range(n):
    a = int(input())
    lst.append([list(map(int,input().split())) for _ in range(a)])

for k in range(1<<n):
    target = bin(k)[2:].zfill(n)
    nk = 0
    for i in range(n):
        if target[i] == '1':
            if any(target[x-1] != str(y)  for x,y in lst[i]):
                break
            else:
                nk += 1
    else:
        ans = max(ans,nk)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = []
ans = 0
for i in range(N):
    a = int(input())
    T.append([list(map(int, input().split())) for _ in range(a)])

for bit in range(1 << N):
    target = bin(bit)[2:].zfill(N)
    nk = 0
    for i in range(N):
        if target[i] == '1':
            if any(target[x-1] != str(y) for x, y in T[i]):
                break
            else:
                nk += 1
    else:
        ans = max(ans, nk)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
tells = []
for i in range(N):
    Ai = int(input())
    for j in range(Ai):
        x,y = map(int,input().split())
        tells.append([i+1,x,y])

truth = 0
for i in range(2**N):
    x = True
    sus = list(str(bin(i))[2:].zfill(N))
    for j in range(len(tells)):
        if sus[tells[j][0]-1] == "1":
            if sus[tells[j][1]-1] != str(tells[j][2]):
                x = False
                break
    if x == True:
        truth = max(truth,sus.count("1"))

print(truth)

Submission status: Accepted

Solution code:
#入力
n=int(input())
xy=[[list(map(int,input().split())) for _ in range(int(input()))] for _ in range(n)]
#bit全探索
ans=0
for i in range(2**n):
  flag=True         
  for j in range(n):
    if (i>>j)&1:    
      for x,y in xy[j]:#j人目の証言と仮定に矛盾がないか調べる
        if (i>>(x-1))&1!=y:
          flag=False
          break
  if flag==True: 
    ans=max(ans,bin(i)[2:].count('1'))     
#出力
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = [[] for _ in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    p[i].append(list(map(int,input().split())))
ans = 0
for i in range(2**n):
  a = [(i >> j) & 1 for j in range(n)]
  flag = 1
  for k in range(n):
    if a[k]*flag == 1:
      for l in p[k]:
        if a[l[0]-1] != l[1]:
          flag = 0
  ans = max(ans,flag*sum(a))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
arr=[]
for _ in range(n):
  k=int(input())
  tmp=[list(map(int,input().split())) for _ in range(k)]
  arr.append(tmp)
ans=0
for i in range(2**n):
  tmp=format(i,'b')
  if len(tmp)<n:
    tmp='0'*(n-len(tmp))+tmp
  flag=True
  for i in range(n):
    c=int(tmp[i])
    if c==0:
      continue
    for a,b in arr[i]:
      if int(tmp[a-1])!=b:
        flag=False
        break
  if flag==True:
    ans=max(ans,tmp.count('1'))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=[]
L=[]
for i in range(n):
   a=int(input())
   A.append(a)
   D=[]
   for i in range(a):
      x,y=map(int,input().split())
      D.append((x,y))
   L.append(D)
ans=0
for i in range(2**n):
   B=[0]*n
   for j in range(n):
      if i>>j&1:
         B[j]=1
   if 1 in B:
      flag=True
      for k in range(n):
         if B[k]==1:
            for m in range(A[k]):
               if B[L[k][m][0]-1]!=L[k][m][1]:
                  flag=False
                  break
      if flag:
         ans=max(ans,sum(B))
print(ans)

Submission status: Accepted

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

ans=0
for i in range(2**n):
   B=[0]*n
   for j in range(n):
      if i>>j&1:
         B[j]=1
   if 1 in B:
      flag=True
      for k in range(n):
         if B[k]==1:
            for m in range(A[k]):
               if B[L[k][m][0]-1]!=L[k][m][1]:
                  flag=False
                  break
      if flag:
         ans=max(ans,sum(B))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

maxcnt = 0
ixy = []

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

# print(ixy)

# bit全探索
for bit in range((1 << N)):
    # 2重ループがうまく抜けられない...
    break_flag = False
    for i, x, y in ixy:
        # 対応するbitが1のとき正直者、0のとき嘘つき
        # 正直者iの証言が
        if ((bit >> i) & 1):
            # bitの状態と一致しないとき矛盾
            if ((bit >> x) & 1 != y):
                break_flag = True
                # print("break1", i, x, y)
                break
    # 嘘つきは反対の証言になるわけではなく真偽不明として無視するらしい...
    # breakしてきたときはカウントしない
    if break_flag:
        continue
    # ここまで全て矛盾がなければ立っているbitの数 (= 正直者の数) をカウント
    # 最大値を更新
    else:
        # print(bin(bit))
        maxcnt = max(maxcnt, bin(bit).count("1"))

print(maxcnt)

Submission status: Accepted

Solution code:
n=int(input())
A=[]
B=[]
for i in range(n):
   a=int(input())
   A.append(a)
   d=[]
   for j in range(a):
      x,y=map(int,input().split())
      d.append((x,y))
   B.append(d)
ans=0
for i in range(2**n):
   L=[0]*n
   for j in range(n):
      if i>>j&1:
         L[j]=1
   if 1 in L:
      flag=True
      for k in range(n):
         if L[k]==1:
            for m in range(A[k]):
               if L[B[k][m][0]-1]!=B[k][m][1]:
                  flag=False
                  break
      if flag:
         ans=max(sum(L),ans)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

m = 0

for i in range(1, 2**n):
    se = format(i, 'b').zfill(n)
    flg = True
    for j in a:
        if se[j[0]] == "1":
            if int(se[j[1]]) ^ j[2] == 1:
                flg = False
                break
    if flg is True:
        m = max([m, se.count("1")])
 
print(m)

Submission status: Accepted

Solution code:
n = int(input())

a_tests = [[-1]*n for _ in range(n)]

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

res = 0

for i in range(2 ** n):
    flag = False

    one_count = 0
    for bit in bin(i)[2:]:
        one_count += int(bit)

    if res >= one_count:
        continue

    for j in range(n):
        if int(bin(i >> (n - j - 1))[-1]) == 0:
            continue
        for k in range(n):
            if a_tests[j][k] != -1 and a_tests[j][k] != int(bin(i >> (n - k - 1))[-1]):
                flag = True
    if flag == False:
        res = one_count
    
print(res)

Submission status: Accepted

Solution code:
#python3

def main():
    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 = -1
    for i in range(1<<n):
        honest = [0 for _ in range(n)]
        for j in range(n):
            if (i>>j) & 1:
                honest[j] = 1 
        
        flag = True 
        for j in range(n):
            if honest[j] == 1:
                for k in range(n):
                    if g[j][k] == -1:
                        continue
                    if g[j][k] != honest[k]:
                        flag = False
        if flag:
            ans = max(ans, honest.count(1))

    print(ans)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


sys.setrecursionlimit(1000000)
MOD = int(1e09) + 7
INF = int(1e30)


def main():
    # sys.stdin = open("Sample.txt")
    N = Scanner.int()
    A = [[-1 for _ in range(N)]for _ in range(N)]
    for i in range(N):
        a = Scanner.int()
        for _ in range(a):
            x, y = Scanner.map_int()
            x -= 1
            A[i][x] = y
    ans = 0
    for i in range(1 << N):
        v = [0] * N
        for j in range(N):
            v[j] = (i >> j) & 1
        isOK = True
        for j in range(N):
            for k in range(N):
                if v[k] == 0:
                    continue
                if A[k][j] == -1:
                    continue
                if A[k][j] != v[j]:
                    isOK = False
        if isOK:
            ans = max(ans, v.count(1))
    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

info = [[] for i in range(n)]

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

ans = 0

for bit in range(1 << n):
    flag = True
    for i in range(n):
        if bit >> i & 1:
            # 1番目が正直者
            for x,y in info[i]:
                if (bit >> x) & 1 != y:
                    flag = False

    if flag:
        ans = max(bin(bit).count('1'), ans)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [None] * N
for i in range(N):
    a = int(input())
    data = [None] * a
    for j in range(a):
        data[j] = tuple(map(int, input().split()))
    A[i] = data

ANS = 0
for n in range(2 ** N):
    ok = True

    P = {i: bool(n & 2 ** i) for i in range(N)}

    for i in range(N):
        if P[i]:
            for j, b in A[i]:
                j -= 1
                b = bool(b)
                if b != P[j]:
                    ok = False

    if ok:
        ans = 0
        while n:
            ans += n % 2
            n //= 2
        ANS = max(ANS, ans)

print(ANS)

Submission status: Accepted

Solution code:
#ABC 147 C 「Honest or Unkind」

n=int(input())
ans=0
A=[[] for _ in range(n)]

for i in range(n):
    a=int(input())
    for j in range(a):
        A[i].append(tuple(map(int,input().split())))
        
#-------------------------------------------------------------iをn桁２進数表記（[2:]で0bを切って、zfill()で左揃えへ）
for i in range(2**n):
    ii=str(bin(i))[2:].zfill(n)
#-------------------------------------------------------------#i個目の場合が証言をみたすか調べる：2**n個の組み合わせ
    chk=True
    cur=0
 
    for j in range(n):                                        #j個目の証言を満たすか調べる        
        if ii[j]=="0":
            continue
        else:
            cur+=1                                            #Count up 
            for x,y in A[j]:                                  #turpleで(x,y)を指定する
                if y==1 and ii[x-1]=="0":                     #Aとiiを比較
                    chk=False                                 #違っていたらFalseへ
                elif y==0 and ii[x-1]=="1":
                    chk=False
    if chk:                                                   #もしChk = Trueのままだったらn個全ての証言をみたすので、これまでのマックスと比べる
        ans=max(ans,cur)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
L=[[list(map(int,input().split())) for _ in range(int(input()))] for _ in range(n)]
a=0
for i in range(1, 2**n):
  f=True
  for j in range(n):
    if (i>>j)&1==0:
      continue
    for x,y in L[j]:
      if (i>>(x-1))&1!=y:
        f=False
        break
    if not f:
      break
  if f:
    a=max(a, bin(i)[2:].count('1'))
print(a)

Submission status: Accepted

Solution code:
n = int(input())
talk = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        talk[i].append([x-1,y])
ans = 0
for i in range(1,2**n):
    flag = 0
    for j in range(n):
        if (i>>j)&1 == 1:
            for x,y in talk[j]:
                if (i>>x)&1 != y:
                    flag = 1
                    break
    if flag == 0:
        ans = max(ans,bin(i).count("1"))
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    A = []
    X = []
    Y = []
    testimony = []
    for i in range(N):
        testimony.append(XLMIIS(II()))

    def check(history):
        if len(history) < N:
            return max(check(history+[0]),check(history+[1]))
        
        for i,h in enumerate(history):
            if h == 1:
                for x,y in testimony[i]:
                    if history[x-1] != y:
                        return -1
        
        return sum(history)
        
    print(max(check([0]),check([1])))




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

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

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

Submission status: Accepted

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

m = 0
for i in range(1,2**n):
    se = format(i,'b').zfill(n)
    fl = True
    for j in a:
        if se[j[0]] == "1":
            if int(se[j[1]])^j[2] == 1:
                fl = False
                break
    if fl:
        m = max([m,se.count("1")])

print(m)

Submission status: Accepted

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

def zeroone(n):
    if n == 1:
        return [[0],[1]]
    a = zeroone(n-1)
    b = zeroone(n-1)
    for i in range(len(a)):
        a[i].append(0)
    for i in range(len(b)):
        b[i].append(1)
    a.extend(b)
    return a

answer = zeroone(n)

def is_possible(line):
    l = len(line)
    for i in range(l):
        if line[i] == 1:
            for j in range(a[i]):
                if y[i][j] != line[x[i][j] - 1]:
                    return False
    return True

max = 0
for i in range(2**n):
    if is_possible(answer[i]):
        if max < answer[i].count(1):
            max = answer[i].count(1)
print(max)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(0,N):
    a=int(input())
    b=[]
    for j in range(0,a):
        b.append(list(map(int,input().split())))
    for B in b:
        B[0]-=1
    A.append(b)
import itertools
ans=0
for i in itertools.product([-1,1],repeat=N):
    OK=True
    for j in range(0,N):
        if i[j]==-1:
            OK=True
        else:
            for a in A[j]:
                if a[1]==0:
                    if i[a[0]]==1:
                        OK=False
                else:
                    if i[a[0]]==-1:
                        OK=False
        if not OK:
            break
    if i.count(1)>ans and OK:
        ans=i.count(1)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
comments = {}

for i in range(1, n+1):
    ni = int(input())
    comments[i] = [tuple(map(int, input().split())) for _ in range(ni)]

nhonests = [0]

for ibin in (format(i, "b") for i in range(2**n, 2**(n+1))):
    ni_lie, ni = 0, 1
    
    while (not ni_lie) and ni < n+1:        
        for ci in comments[ni]:            
            if int(ibin[ni]) and ci[1] ^ int(ibin[ci[0]]):
                ni_lie += 1
            ### print(ibin, ni, int(ibin[ni]), end=" ") ###
            ### print((ci[0], ci[1]), ci[0], int(ibin[ci[0]]), end=" ") ###
            ### print((ni_lie,)) ###
            
        ni += 1
        
    if not ni_lie:
        nhonests.append(ibin.count("1") - 1)
        ### print(ibin) ###
        
print(max(nhonests))

Submission status: Accepted

Solution code:
n = int(input())
comments = {}

for i in range(1, n+1):
    ni = int(input())
    comments[i] = [tuple(map(int, input().split())) for _ in range(ni)]

nhonests = [0]

for ibin in [format(i, "b") for i in range(2**n, 2**(n+1))]:
    lie, ni = 0, 1
    ### print(ibin) ###
    
    while (not lie) and ni < n+1:          
        for ci in comments[ni]:
            if int(ibin[ni]) and ci[1] ^ int(ibin[ci[0]]):
                lie += 1
                
        ### print(comments[ni], lie) ###
        ni += 1
        
    if not lie:
        nhonests.append(ibin.count("1") - 1)
        
print(max(nhonests))

Submission status: Accepted

Solution code:
N = int(input())
A = [0]*N
x = [[0]*N for i in range(N)]
y = [[0]*N for i in range(N)]

maxsum = 0

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())

sum = 0
for i2 in range (2**N):
    i = 2**N-1-i2
    TF=[0]*N
    ans=True
    
    for j in range(N):
        if(i >> j & 1):
            TF[j]=1
    for j in range(N):

        if(TF[j] == 1):
            for k in range(A[j]):
                if(TF[x[j][k]-1] != y[j][k]):
                    ans=False
    if(ans):
        sum=0
        for j in range(N):
            if(i >> j & 1):
                sum += 1
            maxsum = max(sum,maxsum)

print(maxsum)

Submission status: Accepted

Solution code:
N=int(input())
evidence=[[[-1]*2 for i in range(N)]for j in range(N)]
for i in range (0,N):
    A=int(input())

    for j in range (0,A):
        [x,y]=list(map(int, input().split()))
        evidence[i][j]=[x,y]

for i in range (2**N):
    TF=[1]*N

    for j in range (N):
        if ((i>>j)&1):
            TF[N-j-1]=0
    
        #print(TF)

        STOP=0
        
        for k in range (0,N):

            if STOP==1:
                break
            if TF[k]==1: #k番目の人が正直者なら
                if STOP==1:
                    break
                for l in range (0,N): #k番目の人の発言を全部調べて
                    if STOP==1:
                        break
                    if evidence[k][l][1]==0: #誰かを不親切だと証言したなら
                        if TF[evidence[k][l][0]-1]!=0: #その人が正直者だったらアウト
                            STOP=1
                    if evidence[k][l][1]==1: #誰かを正直者だと証言したなら
                        if TF[evidence[k][l][0]-1]!=1: #その人が不親切だったらアウト
                            STOP=1
    
    if STOP==0:
        print(sum(TF))
        break

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline

N = int(readline())
XY = []
for i in range(N):
    a = int(readline())
    XY.append(tuple(tuple(map(int, readline().split())) for _ in range(a)))


# 正直者の人数を返す(矛盾　-> -1)
def honest():
    num = 0
    for i in range(N):
        if bit>>i & 1:
            for x, y in XY[i]:
                x -= 1
                if bit>>x & 1 != y:
                    return -1
            num += 1
    return num


max_honest = 0
for bit in range(2 ** N):
    max_honest = max(max_honest, honest())
print(max_honest)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
x=[[] for i in range(N)]
y=[[] for i in range(N)]
for i in range(N):
    A.append(int(input()))
    for j in range(A[i]):
        a,b=map(int,input().split())
        x[i].append(a)
        y[i].append(b)
ans=0
for i in range(1,2**N):
    tmp=[0]*N
    t=1
    cnt=0
    for j in range(N):
        if((i>>j)&1):
            tmp[j]=1
    for j in range(N):
        if(tmp[j]==0):
            continue
        for h in range(A[j]):
            if(tmp[x[j][h]-1]!=y[j][h]):
                t=0
                break
        cnt+=1
        if(t==0):
            cnt=0
            break
    ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n = int(input())
pattern = list(product(*[[1, 0]]*n))

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

ans = 0
for patt in pattern:
    contradiction = 0
    for e in evidence:
        if patt[e[0]] == 1:  # 証言者が正直者
            if patt[e[1]] == e[2]:  # 矛盾が生じない
                pass
            else:  # 矛盾が生じる
                contradiction = 1
                break
        elif patt[e[0]] == 0:  # 証言者が不親切な人
            pass
    if contradiction:
        continue
    else:
        ans = max(ans, patt.count(1))
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [0] * N
ts = [None] * N

for i in range(N):
    A[i] = int(input())
    t = [None] * A[i]
    for j in range(A[i]):
        t[j] = list(map(int, input().split()))
    ts[i] = t

ans = 0

for bit in range(1 << N):
    for i in range(N):
        if ((bit >> i) & 1) == 0:
            continue
        for j in range(A[i]):
            x, y = ts[i][j]
            x -= 1
            if ((bit >> x) & 1) != y:
                break
        else:
            continue
        break
    else:
        count = bin(bit).count("1")
        ans = max(count, ans)

print(ans)

Submission status: Accepted

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

ans = 0

for i in range(2**n):
    flag = 0
    for j in range(n):
        if (i >> j) & 1:#もし正直者だったら
            for k in ls[j]:#証言の確認
                if (i >> k[0])&1 != k[1]:#もし証言がおかしかったら
                    flag = 1
                    break
    if flag == 0:
        ans = max(ans, bin(i)[2:].count('1'))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = []
for i in range(n):
    a = int(input())
    l1 = []
    for j in range(a):
        x = list(map(int,input().split()))
        l1.append(x)
    l.append(l1)
al = []
for i in range(2**n):
    key = 0
    ans = 0
    rl = [-1 for i in range(n)]
    for j in range(n):
        if i//(2**(n-j-1)) == 1:
            i -= 2**(n-j-1)
            if rl[j] == 0:
                key = 1
                break
            elif rl[j] == -1:
                rl[j] = 1
                ans += 1
            for k in l[j]:
                if rl[k[0]-1] == -1:
                    rl[k[0]-1] = k[1]
                    if k[1] == 1:
                        ans += 1
                else:
                    if rl[k[0]-1] != k[1]:
                        key = 1
                        break
        else:
            if rl[j] == 1:
                key = 1
                break
            else:
                rl[j] = 0
        #print(rl)
    if key == 1:
        al.append(0)
    else:
        al.append(ans)
print(max(al))

Submission status: Accepted

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

ans = 0

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

Submission status: Accepted

Solution code:
n=int(input())
lists=[[] for _ in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        lists[i].append([x,y])
ans=0
for k in range(2**n):
    subans=0
    flag=True
    string=format(k,"0%ib"%n)
    listss=["unknown" for i in range(n)]
    for i in range(n):
        if string[i]=="1":
            #正直者だとした場合の全探索
            subans+=1
            for some in lists[i]:
                if listss[some[0]-1]=="unknown":
                    listss[some[0]-1]=some[1]
                elif listss[some[0]-1]!="unknown":
                    if listss[some[0]-1]!=some[1]:
                        flag=False
                        break

    if flag:
        flags=True
        for i in range(n):
            if  listss[i]!="unknown" and listss[i]!=int(string[i]):
                flags=False
        if flags:
            ans=max(ans,subans)

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
a=[]
cnt=[]

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

    #リスト完成      
for i in range(2**N):
    honest=[]
    hantei=[]
    for j in range(N):
        if ((i >>j)& 1):
            honest.append(j+1)
    hantei1=[[x,0] for x in honest] 
    hantei2=[[x,1] for x in honest]
    for k in honest:
        if [m for m in hantei1 if m in a[k-1]]:
            break
        for l in a[k-1]:
            
            if l[1]==1:
                if l[0] in honest:
                    continue
                else:
                    break
        else:
            continue
        break
                
    else:
        cnt.append(len(honest))
        
            
    
    
    
ans=max(cnt)  
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
p = [[] for _ in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    p[i].append(list(map(int,input().split())))
ans = 0
for i in range(2**n):
  a = [(i >> j) & 1 for j in range(n-1,-1,-1)]
  flag = 1
  for k in range(n):
    if a[k]*flag == 1:
      for l in p[k]:
        if a[l[0]-1] != l[1]:
          flag = 0
  ans = max(ans,flag*sum(a))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[0 for i in range(n)]
for i in range(n):
  ka=int(input())
  r,w=[],[]
  for k in range(ka):
    x,y=map(int,input().split())
    r.append(x-1) if y else w.append(x-1)
  l[i]=(set(r),set(w))
ans=0
for j in range(2**n):
  v=format(j,"b").zfill(n)
  R,W=set(),set()
  RR={t for t in range(n) if v[t]=="1"}
  for h in RR:
    r,w=l[h]
    R|=r
    W|=w
  WW=set(range(n))-RR
  if len(RR&W) or len(WW&R) or len(R&W) :continue
  else:ans=max(ans,len(RR))
print(ans)

Submission status: Accepted

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

ans_l=[]
for i in range(2 ** n):
    people=[]
    for j in range(n):
        if (i >> j) & 1:
            people.append(1)
        else:
            people.append(0)

    fail=False
    for num in range(len(people)):
        if people[num] == 1: # check testimony
            testi=lis[num]
            for t in testi:
                if people[t[0]-1] != t[1]: # contradict
                    fail=True
    if not fail:
        ans_l.append(sum(people))
print(max(ans_l))

Submission status: Accepted

Solution code:
n = int(input())

a = []
x = [[] for _ in range(n)]

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

# print(x)
ans = 0
for i in range(1<<n):
    
    cnt = bin(i).count("1")
    if ans > cnt:
        continue
    flag = True
    for j in range(n):
        # if i==3:
        #     print(i,j,i>>j&1,cnt)
        if i>>j & 1:
            # True if 1
            # if i==3:
                # print(i,j)
            for t in x[j]:
                # 証言:testimony
                # if i == 3:
                    # print(i,t[0]-1, i>>t[0]-1, t[1])
                if (i>>(t[0]-1) &1 ) != t[1]:
                    flag = False
                    break
        if flag == False:
            break
    if flag == True:
        # print(i) # 0 000
        ans = cnt

print(ans)