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 = []
xy = []
for i in range(N):
    A_ = int(input())
    A.append(A_)
    xy_ = []
    xy.append(xy_)
    for j in range(A_):
        xy_.append(list(map(int, input().split())))
answer = 0
for i in range(2 ** N):
    peoples = format(i, "0{0}b".format(N))
    num = peoples.count('1')
    if num <= answer:
        continue
    for j in range(len(peoples)):
        people = peoples[j]
        if people == '0':
            continue
        for x, y in xy[j]:
            if peoples[x - 1] != str(y):
                break
        else:
            continue
        break
    else:
        answer = num
print(answer)

Submission status: Accepted

Solution code:
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())))
for i in range(2**n):
  ii=str(bin(i))[2:].zfill(n)
  chk=True
  cur=0
  for j in range(n):
    if ii[j]=="0":
      continue
    else:
      cur+=1
      for x,y in A[j]:
        if y==1 and ii[x-1]=="0":
          chk=False
        elif y==0 and ii[x-1]=="1":
          chk=False
  if chk:
    ans=max(ans,cur)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import combinations

N = int(input())
testimonies = []
for _ in range(N):
    A = int(input())
    ts = defaultdict(set)
    for _ in range(A):
        x, y = map(int, input().split())
        x -= 1
        ts['honest' if y else 'not'].add(x)
    testimonies.append(ts)

for n in range(N, 0, -1):
    for honests in combinations(range(N), r=n):
        hs = set()
        ns = set()
        for i in honests:
            hs |= testimonies[i]['honest']
            ns |= testimonies[i]['not']
        if not hs & ns and not hs - set(honests) and not set(honests) & ns:
            print(n)
            break
    else:
        continue
    break
else:
    print(0)

Submission status: Accepted

Solution code:
n=int(input())
a=[[] for i in range(n)]
for i in range(n):
    c=int(input())
    for j in range(c):
        x,y = map(int, input().split())
        a[i].append([x,y])
from itertools import permutations, combinations,combinations_with_replacement,product
ans3 = 0
for ans  in product([0,1],repeat=n):
    flag = True
    for i, check in enumerate(a):
        if ans[i]==0:
            continue
        
        for x, y in check:
            if y != ans[x-1]:
                flag = False
                break
    if flag:
        ans3=max(sum(ans), ans3)
print(ans3)

Submission status: Accepted

Solution code:
n = int(input())
answers = []
for i in range(0, n):
    tmp = int(input())
    answers.append([])
    for j in range(0, tmp):
        line = input().split(" ")
        answers[i].append([int(line[0])-1, int(line[1])])

result = 0
for p in range(0, 2**n):
    flag = False
    for i in range(0, len(answers)):
        for a in answers[i]:
            if (p >> a[0]) & 1 != a[1] and (p >> i) & 1 == 1:
                flag = True
                break
        if flag:
            break
    if not flag:
        tmp_result = bin(p).count('1')
        if result < tmp_result:
            result = tmp_result
print(result)

Submission status: Accepted

Solution code:
import itertools

# load
N = int(input())
a = []
x = []
y = []
for i in range(N):
  a.append(int(input()))
  xtmp = []
  ytmp = []
  for j in range(a[i]):
    xtmp2, ytmp2 = map(int, input().split())
    xtmp.append(xtmp2)
    ytmp.append(ytmp2)
  x.append(xtmp)
  y.append(ytmp)

#print('x:%s' % x)
#print('y:%s' % y)
#print(x[0][0])

# honest?

contra = False
stop = False
for r in range(N+1):
  for v in itertools.combinations(range(N), r):
    h = [1] * N
    for t in range(len(v)):
      h[v[t]] = 0

    for i in range(N):
      for j in range(a[i]):
      	if h[i] == 1 and (h[x[i][j]-1] != y[i][j]): # contradiction
          contra = True
          #print('contra: h:%s, i:%d, j:%d, h[x[i][j]-1]:%d, y[i][j]:%d' % (h, i, j, h[x[i][j]-1], y[i][j]))
          break
      if contra:
        contra = False
        break
    else:
      stop = True
      #print('answer? h: %s' % h)
      break
  if stop:
    break
    
print(sum(h))

Submission status: Accepted

Solution code:
N = int(input())
A = list()
E = list()
for i in range(N):
    A.append(int(input()))
    evid = list()
    for j in range(A[-1]):
        target, label = input().split()
        evid.append([int(target) - 1, int(label)])
    E.append(evid)

max_honesty = 0
for i in range(2**N):
    state = [(i >> j) & 1 for j in range(N)]
    is_contrad = False
    for j in range(N):
        if state[j] == 1:
            evids = E[j]
            for e in  evids:
                target, label = e
                if label != state[target]:
                    is_contrad = True
                    break
        if is_contrad:
            break
    if not is_contrad and max_honesty < sum(state):
        max_honesty = sum(state)

print(max_honesty)

Submission status: Accepted

Solution code:
import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n = INT()
ll = [[] for _ in range(n)]
l = [0]*n

for i in range(n):
    tmp = INT()
    for j in range(tmp):
        x,y = MAP()
        ll[i].append([x-1,y])

ans = 0
for bit in range(2**n):
    ok = True
    is_honest = [(bit>>i) & 1 for i in range(n)]
    #print(is_honest)
    for i in range(n):
        if not is_honest[i]:
            continue
        for x,y in ll[i]:
            if is_honest[x]!=y:
                ok=False
    if ok:
        ans = max(ans,sum(is_honest))
print(ans)

Submission status: Accepted

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

ans=0
for k in range(2**n):
    f=1
    for i in range(n):
        if k>>i&1==0:
            continue
        for x,y in l[i]:
            if (k>>x&1)!=y:
                f=0
    if f:
        c=0
        for i in range(n):
            c+=k>>i&1
        ans=max(ans,c)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
lista = []
for n in range(N):
    listan = []
    an = int(input())
    for n in range(an):
        listxy = tuple(map(int, input().split()))
        listan.append(listxy)
    listset = tuple(listan)
    lista.append(listset)    
tuplea = tuple(lista)    
#print(lista)
ansfin = 0
for n in range(2**N):
    bin2 = list(bin(n))[2:]
    bin2.reverse()
    #print(bin2)
    l = len(bin2)
    rightwrong = set()
    #print(l)
    setright = set()
    for n in range(N):
        if n<l:
            #print(bin2[n])
            if bin2[n] == str(1):
                rightwrong.add((n+1, 1))
                lo = len(tuplea[n])
                for m in range(lo):
                    setright.add(tuplea[n][m])
            else:
                rightwrong.add((n+1, 0))
        else:
            rightwrong.add((n+1, 0))  
    #print('a')                     
    #print(setright)
    #print(rightwrong)
    if setright.issubset(rightwrong):
        ans = bin2.count(str(1))
        if ansfin>=ans:
            pass
        else:
            ansfin = ans
    #print(ans)    
print(ansfin)

Submission status: Accepted

Solution code:
n = int(input())

a = []
xys = [[] for i in range(n)]

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


ans = 0
for i in range(1,2**n):
    cont = True
    for j in range(n):
        if (i >> j) & 1 == 1:
            for x,y in xys[j]:
                if (i >> (x-1)) & 1 != y:
                    cont = False
                    break
        if not cont:
            break
    if cont:
        ans = max(ans,bin(i)[2:].count('1'))

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())

a = []
xy = []

for _ in range(n):
    a_tmp = int(input())
    a.append(a_tmp)
    xy_tmp = []
    for _ in range(a_tmp):
        xy_tmp.append(list(map(int, input().split())))
    xy.append(xy_tmp)

ans = 0
for pat in product([1, 0], repeat=n):
    sat = True
    for i, bl in enumerate(pat):
        if bl:
            for x, y in xy[i]:
                x -= 1
                if pat[x] != y:
                    sat = False

    if sat:
        cnt = sum(pat)
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

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

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

ans = 0

for i in range(0, 2**n):
    # print('\n', i, bin(i))
    isValid = True
    temp = 0

    for k in range(len(xy)):
        hMap = xy[k]
        kBit = (i >> k) & 1
        # print('k:', k, 'kBit:', kBit)
        if kBit == 1:
            # print('hMap is correct:', hMap)
            for key, value in hMap.items():
                # print(key, value, (i >> (key-1)) & 1, 'must be same')
                if not (i >> (key-1)) & 1 == value:
                    # print('paradox!')
                    isValid = False
                    break
        # else:
        #     # print('hMap is NOT correct:', hMap)
        #     for key, value in hMap.items():
        #         # print(key, value, (i >> (key-1)) & 1, 'must be different')
        #         if not (i >> (key-1)) & 1 != value:
        #             # print('paradox!')
        #             isValid = False
        #             break
    if isValid:
        for j in range(n):
            # print('Check digit:', j)
            jBit = (i >> j) & 1
            # print('bit:', jBit)
            if jBit == 1:
                temp += 1
        ans = max(ans, temp)

print(ans)

Submission status: Accepted

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

solution = 0
for i in range(1, 1<<N):
    honest = set()
    unhonest = set()
    ans = [0]*N
    cnt = 0
    while i > 0:
        if i % 2:
            honest.add(cnt)
            ans[cnt] = 1
        i //= 2
        cnt += 1

    unhonest = set(range(N)) - honest

    flag = False
    for p in range(N):
        if p in honest:
            for x, y in XY[p]:
                if y == 0:
                    if x in honest:
                        flag = True
                        break

                elif y == 1:
                    if x in unhonest:
                        flag = True
                        break
        if flag:
            break

    if flag:
        continue
    else:
        solution = max(solution, sum(ans))
    
print(solution)

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]):
    d, e = map(int, input().split())
    d -= 1
    x[i].append(d)
    y[i].append(e)
ans = 0
for i in range(2 ** n):
  s = 0
  flag = True
  for j in range(n):
    if not ((i >> j) & 1):
      continue
    else:
      s += 1
      for xx, yy in zip(x[j], y[j]):
        if ((i >> xx) & 1) != yy:
          flag = False
  if flag:
    ans = max(ans, s)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

N = int(input())
stl = []
for i in range(N):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        stl.append((i, x-1, y))
dl = np.array(list(itertools.product([0, 1], repeat=N)), np.bool)
for i, x, y in stl:
    bl = (dl[:, i] == False) | (dl[:, x] == bool(y))
    dl = dl[bl]
res = dl.sum(axis=1).max()
print(res)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

N = int(input())
stl = []
for i in range(N):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        stl.append((i, x-1, y))
dl = np.array(list(itertools.product([0, 1], repeat=N)), np.bool)
for i, x, y in stl:
    bl = np.logical_not(dl[:, i]) | (dl[:, x] == bool(y))
    dl = dl[bl]
res = dl.sum(axis=1).max()
print(res)

Submission status: Accepted

Solution code:
N=int(input())
honest=[0 for i in range(N)]
liar=[0 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:
      liar[i]|=(1<<(x-1))
    else:
      honest[i]|=(1<<(x-1))

ans=0
for i in range(2**N):
  ok=True
  for j in range(N):
    if (i>>j)&1:
      hon=honest[j]
      pat=i
      while hon>0:
        if hon&1==1 and pat&1==0:
          ok=False
          break
        hon>>=1
        pat>>=1
      li=liar[j]
      pat=i
      while li>0:
        if li&1==1 and pat&1==1:
          ok=False
          break
        li>>=1
        pat>>=1
      if not ok:
        break
  if ok:
    val=i
    cnt=0
    while val>0:
      if val&1==1:
        cnt+=1
      val>>=1
    ans=max(ans,cnt)
        
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
honest=[0 for i in range(N)]
liar=[0 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:
      liar[i]|=(1<<(x-1))
    else:
      honest[i]|=(1<<(x-1))

ans=0
for i in range(2**N):
  # 1ループ＝正直者・不親切者の1パターン＝iをビット化したもの
  ok=True
  for j in range(N):
    # j番目が正直者であるパターン
    if (i>>j)&1:
      hon=honest[j]
      pat=i
      while hon>0:
        if hon&1==1 and pat&1==0:
          ok=False
          break
        hon>>=1
        pat>>=1
      li=liar[j]
      pat=i
      while li>0:
        if li&1==1 and pat&1==1:
          ok=False
          break
        li>>=1
        pat>>=1
      if not ok:
        break
  if ok:
    val=i
    cnt=0
    while val>0:
      if val&1==1:
        cnt+=1
      val>>=1
    ans=max(ans,cnt)
        
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

N = int(input())
arr = np.empty((0, 3), int)
for i in range(N):
    for _ in range(int(input())):
        x, y = map(int,input().split())
        arr = np.vstack((arr, [i, x, y]))

bl = list(itertools.product([0,1], repeat=N))

ans = 0
for n in bl:
    flg = True
    for i,x,y in arr:
        if (n[i] != 1) or (n[x-1]==y):
            continue
        else:
            flg = False
            break

    if flg == True:
        ans = max(ans, sum(n))

print(ans)

Submission status: Accepted

Solution code:
import sys

import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
# from bisect import bisect_left, bisect_right, insort_left, insort_right
# from operator import itemgetter as ig
# sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []; mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]#NumberGrid
def grid(n): return [s_list() for _ in range(n)]

def main():
    n = si()
    ixy = [[] for _ in range(n)]
    for i in range(n):
        for a in range(int(input())):
            ixy[i].append([int(m) - 1 for m in input().split()])

    # 真：0，不親切：-1
    nums = [i for i in range(n)]

    flag = 0  # 全体の枠組みを抜けるためのflag
    ans = 0
    while ans < n and flag == 0:
        for balls in combinations(nums, ans + 1):
            balls = list(balls)  # 合計人数を調べるために使用，真だと仮定

            # 初期化する場所に注意する！！
            queue = deque()
            hash = defaultdict(lambda: -2)

            for h in balls:
                hash[h] = 0
                queue.append(h)

            sign = queue.popleft()
            brefl = 0  # そのballsでの探索を抜けるためのflag
            while brefl == 0:
                for x, y in ixy[sign]:
                    if y == -1:  # 不親切
                        if x in hash and hash[x] == 0:  # 0-> -1 ×
                            flag = 1
                            brefl = 1
                            break  # 矛盾
                        else:  # -2-> -1 ○
                            hash[x] = -1
                    else:  # 真
                        if x not in hash:  # -2-> 0 ○
                            hash[x] = 0
                            queue.append(x)
                            balls.append(x)
                        elif x in hash and hash[x] == -1:  # -1-> 0 ×
                            flag = 1
                            brefl = 1
                            break  # 矛盾

                if queue == deque():
                    break  # 探索終了
                else:
                    sign = queue.popleft()


            if len(balls) > ans and brefl == 0:
                ans = len(balls)
                flag = 0
                break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
testimony = [[] for _ in range(n)]
for i in range(n):
    a = I()
    testimony[i] = LIR(a)


ans = 0
for j in range(2 ** n - 1, -1, -1):
    flag = 0
    bit_cnt = 0
    for k in range(n):
        if j >> k & 1:
            bit_cnt += 1
            for x, y in testimony[k]:
                if y != j >> (x - 1) & 1:
                    flag = 1
                    break
            if flag:
                break
    else:
        ans = max(ans, bit_cnt)


print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

ans = 0
for i in range(1 << n):
    people = []
    t= 0
    for j in range(n):
        if (i & (1 << j)) == 0:
            t+=1
            people.append(1)
        else:
            people.append(-1)

    flg = True
    for j in range(n):
        if (i & (1 << j)) == 0:
            for k in range(len(l[j])):
                x,y = l[j][k]
                if y == 0 and people[x-1]== 1:
                    flg = False
                elif y == 1 and people[x-1] == -1:
                    flg = False

    if flg:
        ans = max(ans , t)        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

a = []
xy = [[] for i in range(n)]


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

ans = 0
for i in range(1<<(n)):
    memo = []
    cnt = 0
    for j in range(n):
        if ((i>>j)&1):
            memo.append(1)
            cnt += 1
        else:
            memo.append(0)
    
    cntn = True     
    for j in range(n):
        if memo[j] == 0:
            continue
        for k in range(a[j]):
           prs = xy[j][k][0]

           if memo[prs] != xy[j][k][1]:
               cntn = False
    if not(cntn):
        continue
    ans = max(ans,cnt)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

state = [[-1] * N for i in range(N)]
for index in range(N):
    Ai = int(input())
    for naka in range(Ai):
        x, y = map(int, input().split()) 
        state[index][x - 1] = y
        # state[index][naka] = [x, y]


# print(state)


maxx = 0
for index in range(1, 2 ** N):
    # print(index)
    person = index
    tempM = 0
    Ai = 0
    ok = 1
    while person > 0:
        if ok == 0:
            break
        if person % 2 == 1:
            tempM += 1
            for i in range(N):
                if state[Ai][i] != -1:
                    # print(str(Ai) + " " + str(i))
                    # print(str(state[Ai][i]) + " " + str((index // (2 ** i)) % 2))
                    # print()
                    if state[Ai][i] != (index // (2 ** i)) % 2:
                        ok = 0
                        break
                
        
        person //= 2
        Ai += 1
    
    if ok == 1:
        maxx = max(maxx, tempM)

print(maxx)

Submission status: Accepted

Solution code:
ans=0
shogen=[]
n=int(input())
for _ in range(n):
  t=[]
  a=int(input())
  for __ in range(a):
    h=list(map(int,input().split()))
    t.append(h)
  shogen.append(t)
for i in range(2**n):
  flag=True
  for j in range(n):
    if not flag:
      break
    if ((i>>j) & 1):
      for h in shogen[j]:
        if ((i>>h[0]-1)&1) !=h[1]:
          flag=False
  if flag:
    mnt = bin(i).count("1")
    ans=max(ans,mnt)
print(ans)

Submission status: Accepted

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

ans=0

for i in range(2**n):
  flag=True
  for j in range(n):
    if not flag:
      break
    if ((i>>j) & 1):
      for s in shogen[j]:
        if ((i>>s[0]-1)&1) !=s[1]:
          flag=False
  if flag:
    mnt = bin(i).count("1")
    ans=max(ans,mnt)
print(ans)

Submission status: Accepted

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


def check(N, v, honests, layers):
  for i in range(N):
    if (v >> i) & 1 == 0:
      continue
    elif (honests[i] & ~v) != 0:
      return False
    elif (layers[i] & v) != 0:
      return False

  return True


def main():
  N = int(input())
  honests = [0] * N
  layers = [0] * N
  result = 0

  for i in range(N):
    for _ in range(int(input())):
      x, y = map(int, input().split())
      if y == 1:
        honests[i] |= 1 << (x - 1)
      else:
        layers[i] |= 1 << (x - 1)

  for v in range(2 ** N):
    if check(N, v, honests, layers):
      result = max(sum((v >> i) & 1 for i in range(N)), result)

  print(result)


if __name__ == '__main__':
  main()

Submission status: Accepted

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

ans = 0
for i in range(1 << N):
    for p in range(N):
        f = ((i >> p) & 1 == 1)
        if not all([not f or f and (i >> (t[0]-1)) & 1 == t[1] for t in L[p]]):
            break
    else:
        ans = max(ans, str(bin(i)).count('1'))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
ls = []
for i in range(N):
  a = int(input())
  for _ in range(a):
    x,y = map(int, input().split())
    ls.append((i,x-1,y==1))
max = 0
for i in range(2**N):
  c = 0
  hon = set()
  unhon = set()
  
  for x in range(N):
    if (i>>x)&1 == 1:
      c += 1
      
  for x,y,z in ls:
    if (i>>x)&1 == 1:
      if z:
        hon.add(y)
      else:
        unhon.add(y)
        
  if len(hon & unhon) == 0:
    flag = True
    for n in range(N):
      if (i>>n)&1 == 1:
        if n in unhon:
          flag = False
          break
      else:
        if n in hon:
          flag = False
          break
    if flag and c >= max:
      max = c
      
print(max)

Submission status: Accepted

Solution code:
N = int(input())

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

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

Submission status: Accepted

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

for _ in range(N):
    a = int(input())
    comment = [[int(_) for _ in input().split()] for i in range(a)]
    C.append(comment)

ans = 0
for z in range(2 ** N):
    chk = [0] * N
    honests = []
    for b in range(N):
        if (1 << b) & z:
            honests.append(b)
            chk[b] = 1

    err = False
    for honest in honests:
        # コメントチェック
        for _i, v in C[honest]:
            i = _i - 1
            if chk[i] != v:
                err = True
                break
        if err: break
    if err: continue
    ans = max(ans, len(honests))

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
A = {}
for i in range(N):
    a = int(input())
    l = []
    for j in range(a):
        tmp = list(map(int, input().split()))
        l.append(tmp[:])
    A[i+1] = l[:]
ans = -1
for bit in range(2**N):
    l = []
    # 正直者と嘘つきの配列
    for i in range(N):
        if (bit >> i) & 1 == 1:
            l.append(1)
        else:
            l.append(0)
    
    flag = True
    for i in range(N):
        # 正直者の場合、それぞれのいうことに整合性があるかを確認する
        if (bit >> i) & 1 == 1:
            for j in range(len(A[i+1])):
                # 正直者を嘘つき(もしくは逆)を言った場合はその組み合わせで
                # 整合性が取れないので成り立たない組み合わせ
                if l[A[i+1][j][0]-1] != A[i+1][j][1]:
                    flag = False
    if flag:
        ans = max(ans, sum(l))
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
A = {}
for i in range(N):
    a = int(input())
    l = []
    for j in range(a):
        tmp = list(map(int, input().split()))
        l.append(tmp[:])
    A[i+1] = l[:]
# print(A)

ans = -1
for bit in range(2**N):
    l = []
    # 正直者と嘘つきの配列
    for i in range(N):
        if (bit >> i) & 1 == 1:
            l.append(1)
        else:
            l.append(0)
    
    flag = True
    for i in range(N):
        if (bit >> i) & 1 == 1:
            for j in range(len(A[i+1])):
                if l[A[i+1][j][0]-1] != A[i+1][j][1]:
                    flag = False
    # print(*l)
    # print(flag)
    if flag:
        ans = max(ans, sum(l))
    # if len(l) <= 2:
    #     ans = 1
print(ans)

Submission status: Accepted

Solution code:
def mainFunc():
    n = int(input())
    tesMat = [0] * (n + 1)
    
    for i in range(1, n + 1):
        tesMat[i] = [-1] * (n + 1)
        a = int(input())
        for j in range(a):
            x, y = list(map(lambda x: int(x), input().split(" ")))
            tesMat[i][x] = y
    
    ans = 0
    flag = False
    for i in range(2 ** n):
        flag = True
        honest = list(map(lambda x: int(x), list(format(i, "b").zfill(n + 1))))
        for j in range(1, n + 1):
            if honest[j] == 1:
                for k in range(1, n + 1):
                    if tesMat[j][k] == 1 and honest[k] == 0 or tesMat[j][k] == 0 and honest[k] == 1:
                        flag = False
                        break

            if not flag:
                break
        
        if flag:
            honestNumber = len(list(filter(lambda x: x == 1, honest)))
            ans = honestNumber if ans < honestNumber else ans
    
    print(ans)

mainFunc()

Submission status: Accepted

Solution code:
n=int(input())
x=[]*n;y=[]*n
for i in range(n):
  A=[]*n;B=[]*n
  for j in range(int(input())):
    a,b=map(int,input().split())
    A.append(a-1),B.append(b)
  x.append(A);y.append(B)
ans=0
for bit in range(2**n):
  T=[bit>>i&1for i in range(n)];cnt=0;f=1
  for i in range(n):
    if bit>>i&1:
      cnt+=1
      for p in range(len(x[i])):
        if T[x[i][p]]!=y[i][p]:
          f=0;break
  if f>0:ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product


def check(N, p, X):
    for i in range(N):
        if p[i] == 0:
            continue
        for j in range(N):
            if X[i][j] is not None and X[i][j] != p[j]:
                return False
    return True


def main():
    N = int(input())
    X = [[None] * N for _ in range(N)]
    for i in range(N):
        A = int(input())
        for j in range(A):
            x, y = map(int, input().split())
            X[i][x-1] = y
    ans = 0
    for p in product([0, 1], repeat=N):
        if check(N, p, X):
            ans = max(ans, sum(p))
    print(ans)


if __name__ == "__main__":
    main()