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

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

MAX = 0
for i in range(2 ** n):
    for index, t in enumerate(testimonies):
        if (i >> index) & 1:
            contradict = False
            for x, y in t:
                if (i >> (x - 1)) % 2 == y:
                    continue
                else:
                    contradict = True
                    break
            if contradict:
                break
    else:
        honest = 0
        while i:
            i = i & (i - 1)
            honest += 1
        MAX = max(MAX, honest)
print(MAX)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

N = int(input())
evid = [[] for _ in range(N)]

for i in range(N):
  a = int(input())
  for _ in range(a):
    x, y = map(int, input().split())
    evid[i].append((x-1,y))
    
ans = 0
for bit in range(1<<N):
  cnt = 0
  ok = True
  for i in range(N):
    if not bit>>i & 1:
      continue
    for x, y in evid[i]:
      if y==1 and not bit>>x & 1:
        ok = False
        break
      if y==0 and  bit>>x & 1:
        ok = False
        break
    if ok:
      cnt += 1
    else:
      break
  else:
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import re
n=int(input())
A=[]
for i in range(n):
    word=["."]*n
    for j in range(int(input())):
        x,y=map(int,input().split())
        word[x-1]=str(y)
    A.append(word)

ans=0
for i in range(2**n):
    num=format(i, "b").zfill(n)
    flag,cnt=1,0
    for j,k in enumerate(num):
        search=re.search(r"".join(A[j]),num)
        if search!=None and k=="1":
            cnt +=1
        elif (search==None and k=="1") or (search!=None and k=="0"):
            flag=0
            break
    if flag:ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import re
n=int(input())
A=[]
for i in range(n):
    B=["."]*n
    for x,y in [list(map(int,input().split())) for k in range(int(input()))]:
        B[x-1]=str(y)
    A.append("".join(B))

ans=0
for i in range(2**n):
    num=format(i,"b").zfill(n)
    cnt,flag=0,1
    for k,j in enumerate(num):
        result=re.search(r"".join(A[k]),num)
        if result!=None and j=="1":
            cnt +=1
        elif (result!=None and j=="0") or (result==None and j=="1"):
            flag=0
            break
    if flag:ans=max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import re
n=int(input())
A=[]
for i in range(n):
    B=["."]*n
    for x,y in [list(map(int,input().split())) for k in range(int(input()))]:
        B[x-1]=str(y)
    A.append("".join(B))
ans=0
for i in range(2**n):
    num=format(i,"b").zfill(n)
    cnt,flag=0,1
    for k,j in enumerate(num):
        result=re.search(r"".join(A[k]),num)
        if result is not None and j=="1":
            cnt +=1
        elif (result is not None and j=="0") or (result is None and j=="1"):
            flag=0
            break
    if flag:ans=max(ans,cnt)
print(ans)

Submission status: Accepted

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

def count_honest(bits):
    honest = [(bits >> i) & 1 for i in range(n)]
    for i in range(n):
        if not honest[i]:
            continue
        for k, v in d[i].items():
            if honest[k] != v:
                return 0
    return sum(honest)


print(max([count_honest(i) for i in range(2**n)]))

Submission status: Accepted

Solution code:
n = int(input())
ms = []
say = []
for i in range(n):
    m = int(input())
    ms.append(m)
    say.append([])
    for j in range(m):
        p,q = list(map(int, input().split()))
        say[i].append([p,q])

# ms =  [2, 2, 2]
# say = [[[2, 1], [3, 0]], [[3, 1], [1, 0]], [[1, 1], [2, 0]]]

def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

ans = 0
for i in range(2**n):
    flag = 1
    nowbit = bitlist(i,n)
    for j in range(n):
        for k in range(ms[j]):
            if nowbit[j]==1:
                if say[j][k][1] != nowbit[say[j][k][0]-1]:
                    flag = 0
    if flag == 1:
        ans = max(ans, sum(nowbit))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

A_ary = []
for _ in range(N):
  A = int(input())
  ans_ary = []
  for _ in range(A):
    x, y = map(int, input().split())
    ans_ary.append([x, y])
  A_ary.append(ans_ary)

counts = []
for n in range(2 ** N):
  
  contExists = False
  for i, a in enumerate(A_ary):
    if not((n >> i) & 1):
      continue
    for xy in a:
      shift_num = xy[0] - 1
      if (((n >> shift_num) & 1) != xy[1]):
        contExists = True
        break

    if (contExists == True):
      break
  
  if (contExists == True):
    continue
  else:
    counts.append(bin(n).count("1"))

print(max(counts))

Submission status: Accepted

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

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

def check(mask,lst):
    cnt = 0
    for i in range(n):
        if mask & (1<<i):
            cnt += 1
            for (p,TF) in lst[i]:
                if mask&(1<<p) != TF<<p:
                    return 0
    return cnt
    
ans = 0
for mask in range(1<<n):
    c = check(mask,lst)
    ans = max(ans,c)    
print(ans)

Submission status: Accepted

Solution code:
import itertools

n=int(input())
a=[[] for i in range(n)]
#print(a)

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

#print(a)
ls=tuple(range(1,n+1))
res=0
for i in range(1,n+1):
    for s in list(itertools.combinations(ls,i)):
        c=list(s)
        my_bool=True
        for j in c:
            for k in range(len(a[j-1])):
                if a[j-1][k][1]==0:#lier
                    if a[j-1][k][0] in c:
                        my_bool=False
                        break
                else:
                    if not a[j-1][k][0] in c:
                        my_bool=False
                        break
            if not my_bool:
                break
        if my_bool:
            #print(c)
            res=max(res,len(c))
print(res)

Submission status: Accepted

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


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

    max_H = 0
    for i in range(2**N):
        bin = format(i, '015b')[::-1]
        ok = True

        for j in range(N):
            for x, y in XY[j]:
                if bin[j] == '1' and y != int(bin[x - 1]):
                    ok = False
                    break
                else:
                    continue
                break
        if ok:
            H = sum(int(x) for x in bin)
            max_H = max(max_H, H)
    print(max_H)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def put(a, k, v):
    if k in a:
        if a[k] != v:
            return False
    else:
        a[k] = v
    return True


def check(n, t, i):
    a = {}
    m = 0
    for j in range(n):
        honest = i >> j & 1
        m += honest
        if not put(a, j+1, honest):
            return 0
        if honest:
            for (k, h) in t[j+1].items():
                if not put(a, k, h if honest else 1 - h):
                    return 0
    return m


def solve(n, t):
    print(max([check(n, t, i) for i in range(1 << n)]))


def main():
    t = {}
    n = int(input())
    for i in range(n):
        a = int(input())
        t[i+1] = {}
        for j in (range(a)):
            x, y = map(int, input().split())
            t[i+1][x] = y
    solve(n, t)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

honest = []
for i in range(n):
    a = int(input())
    honest.append({})
    for j in range(a):
        x,y = map(int, input().split())
        honest[i][x-1] = y
ans = 0
for i in range(1<<n):
    tmp = 0
    hon = 0
    for j in range(n):
        if 1<<j & i == 0:
            continue
        for k,v in honest[j].items():
            if (1<<k & i) != v<<k:
                break
        else:
            tmp += 1
            hon |= 1<<j
    if hon == i and tmp > ans:
        # print(bin(i), bin(tmp), 1<<1 & i, )
        ans = tmp
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
a=[]
x=[]
y=[]

for i in range(n):
    a0=ii()
    a.append(a0)
    xtemp=[]
    ytemp=[]
    for j in range(a0):
        x0,y0=mii()
        x0-=1
        xtemp.append(x0)
        ytemp.append(y0)
    x.append(xtemp)
    y.append(ytemp)

ans=0
for i in product([0,1], repeat=n):
    arr=list(deepcopy(i))


    #嘘つきは0 正直だと1 0だと反転 1だとそのまま
    temp=0
    for j in range(n):
        
        if i[j]==1:
            for k in range(a[j]):
                if i[x[j][k]]!=y[j][k]:
                    temp=1

    if temp==0:
        ans=max(ans,sum(arr))
    #ans=max(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

testimony_list = [[] for _ in range(N)]
for i in range(N):
    Ai = int(input())
    for j in range(Ai):
        x, y = map(int, input().split(' '))
        testimony_list[i].append((x, y))

def judge(bit):
    for i in range(N):
        if not (bit & (1<<i)):
            continue
        for x, y in testimony_list[i]:
            if y == 1 and not (bit & (1<<(x-1))):
                return False
            if y == 0 and (bit & 1<<(x-1)):
                return False
    return True

max_num = 0
for bit in range(1<<N):
    res = judge(bit)
    if res == True:
        num = 0
        for i in bin(bit)[2:][::-1]:
            if int(i) == 1:
                num += 1
        max_num = max(max_num, num)
print(max_num)

Submission status: Accepted

Solution code:
N = int(input())
syougen = []
for i in range(N):
    s = []
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        s.append((x-1, y))
    syougen.append(tuple(s))
# print(syougen)
ans = 0
for i in range(2**N):
    real = []
    flg = True
    for j in range(N):
        if ((i >> j) & 1):
             real.append(j)
    for hito in real:
        for x, y in syougen[hito]:
            if (y == 0 and x in real) or (y == 1 and x not in real):
                flg = False
                break
    if flg:
        ans = max(ans, len(real))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
say = []
a = []
ans = 0
for i in range(n):
    ai = int(input())
    a.append(ai)
    say.append([])
    for j in range(ai):
        xi, yi = map(int, input().split())
        say[i].append((xi, yi))
for i in range(2**n):
    trueman = []
    mujun = False
    for j in map(int, list("0"*(n - len(bin(i)[2:])) + bin(i)[2:])):
        trueman.append(j)
    for j in range(n):
        if trueman[j] == True:
            for k in range(a[j]):
                if say[j][k][1] == 1:
                    if trueman[say[j][k][0]-1] == 0:
                        mujun = True
                if say[j][k][1] == 0:
                    if trueman[say[j][k][0]-1] == 1:
                        mujun = True
    if not mujun:
        ans = max(ans, sum(trueman))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 累乗 #####
# pow(x, y, z) -> x**y % z

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
def main():
	N = inputInt()
	A = []
	for i in range(N):
		tmp = inputInt()
		tmpSet = []
		for j in range(tmp):
			x,y = inputMap()
			tmpSet.append((x,y))
		A.append(tmpSet)

	ans = 0
	for i in range(1,2**N):
		cnts = -1
		ii = i
		syouziki = []
		flg = True
		for j in range(1,N+1):
			target = ii % 2
			ii = ii // 2
			cnts += 1
			if target == 1:
				syouziki.append(cnts)

		for j in syouziki:
			for k in A[j]:
				x,y = k
				x = x-1
				if y == 1:
					if x in syouziki:
						pass
					else:
						flg = False
						break
				else:
					if x in syouziki:
						flg = False
						break
					else:
						pass
			if flg == False:
				break
		if flg == True:
			tmp = len(syouziki)
			if tmp > ans:
				ans = tmp

	print(ans)




#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# special thanks :
#  https://nagiss.hateblo.jp/entry/2019/07/01/185421
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
# nCr mod m
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

# mを法とするaの乗法的逆元
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# nHr mod m
# 問題によって、combination()を切り替えること
def H(n, r, mod=10**9+7):
	# comb = Combination(n+r-1, mod)
	# return comb(n+r-1, r)
    return combination(n+r-1, r, mod)

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

if __name__ == "__main__":
	main()

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 _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        v[i].append((x-1,y))

res = 0
for bit in range(1<<N):
    if judge(bit):
        conut = 0
        for i in range(N):
            if bit & (1<<i):
                conut += 1
        res = max(res, conut)
print(res)

Submission status: Accepted

Solution code:
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
# from functools import reduce

# a, b = [int(v) for v in input().split()]


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

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

        table.append(ary)

    def check(bit):
        for i in range(N):
            if (bit & (1 << i)) == 0:
                continue
            for x, y in table[i]:
                if y == 1 and bit & (1 << x) == 0:
                    return False
                if y == 0 and bit & (1 << x) != 0:
                    return False
        return True

    def search(i, bit):
        if i == N:
            if not check(bit):
                return 0
            return sum(1 for i in range(N) if (bit & (1 << i)) != 0)

        count1 = search(i + 1, bit)
        count2 = search(i + 1, bit | (1 << i))
        return max(count1, count2)

    count = search(0, 0)
    print(count)


main()

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):
        xy[i].append(list(map(int, input().split())))
#print(xy)
bit=[]#1が正直0が嘘
ans=0
def bit_search(bit):
    global ans
    if len(bit)==n:#2**n文の組み合わせを調べる加圧10を交互に入れるためのif
        for i in range(n):
            jugh=bit[i]
            if jugh==1:
                for j in xy[i]:
                    x,y=j
                    if bit[x-1]==0:
                        if y==1:
                            return 
                    else:
                        if y==0:
                            return 
        ans=max(ans,sum(bit))
    else:
       #再起化することによって最初にbitの配列を作る必要性をなくした
        bit_search(bit+[0])
        bit_search(bit+[1])
bit_search(bit)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())
x = []
y = []
for i in range(n):
    xx = []
    yy = []
    for i in range(int(input())):
        arr = [int(i) for i in input().split()]
        xx.append(arr[0])
        yy.append(arr[1])
    x.append(xx)
    y.append(yy)

max_honest = 0
for honest in product([0,1], repeat=n):
    if sum(honest) < max_honest:
        continue
    for i, h in enumerate(honest):
        if h:
            for xx, yy in zip(x[i], y[i]):
                if honest[xx-1] != yy:
                    break
            else:
                continue
            break
    else:
        max_honest = sum(honest)

print(max_honest)

Submission status: Accepted

Solution code:
n = int(input())

def func(x):
  res = []
  for i in range(n):
    res.append(x%2)
    x //= 2
  return res

test = {}
for i in range(n):
  A = int(input())
  test[i+1] = []
  for a in range(A):
    x,y = map(int,input().split())
    test[i+1].append((x,y))

ans = 0
for i in range(2**n):
  people = func(i)
  for i in range(n):
    if people[i]:
      for x,y in test[i+1]:
        if people[x-1] == y:
          continue
        else:
          break
      else:
        continue
      break
  else:
    ans = max(sum(people),ans)
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc147/tasks/abc147_c
# ビット全探索を自作ライブラリでやり直し
# 仮定している不親切な人と、実際に証言で言及されている不親切な人が一致するなかで最大の正直者の場合が答え
# 具体的には、仮定をおく→正直ものの証言を集める→仮定に反する証言がある場合は矛盾
# 矛盾するときは無視、矛盾しないときの人数を記録していく。


def iter_p_adic(p, length):
    '''
    連続して増加するp進数をリストとして返す。lengthはリストの長さ
    return
    ----------
    所望のp進数リストを次々返してくれるiterator
    '''
    from itertools import product
    tmp = [range(p)] * length
    return product(*tmp)


import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


N = read_a_int()
objection = []
for _ in range(N):
    a = read_a_int()
    hatugenn = read_tuple(a)
    objection.append(hatugenn)


def is_ok(katei):
    # 正直もの ==1であるlist kateiから、矛盾するかしないかを返す
    syoujiki = set()  # 仮定した正直者の集合
    for i, k in enumerate(katei):
        if k == 1:
            syoujiki.add(i)
    for s in syoujiki:
        # 発言の収集
        for x, y in objection[s]:
            x -= 1  # 0based-index
            if y == 0:
                if x in syoujiki:
                    return False  # 不親切な人と言われ仮定と矛盾
            else:
                if x not in syoujiki:
                    return False  # 正直者と発言しているが、仮定は正直者ではないとしていて矛盾
    return True


ans = 0
for katei in iter_p_adic(2, N):
    # bit全探索
    if is_ok(katei):
        ans = max(ans, sum(katei))
print(ans)

Submission status: Accepted

Solution code:
def count(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n >>= 1
    return cnt


N = int(input())

shogen = [[] for _ in range(N)]

for i in range(N):
    a = int(input())
    for _ in range(a):
        shogen[i].append(list(map(int, input().split())))
ans = 0
for i in range(1 << N):
    ok = True
    for j in range(N):
        if not (i & (1 << j)):
            continue
        for s in shogen[j]:
            if ((i >> (s[0] - 1)) & 1) ^ s[1]:
                ok = False
    if ok:
        ans = max(ans, count(i))
print(ans)

Submission status: Accepted

Solution code:
def count(n):
    if n == 0:
        return 0
    return count(n >> 1) + (n & 1)


N = int(input())

shogen = [[] for _ in range(N)]

for i in range(N):
    a = int(input())
    for _ in range(a):
        shogen[i].append(list(map(int, input().split())))
ans = 0
for i in range(1 << N):
    ok = True
    for j in range(N):
        if not (i & (1 << j)):
            continue
        for s in shogen[j]:
            if ((i >> (s[0] - 1)) & 1) ^ s[1]:
                ok = False
    if ok:
        ans = max(ans, count(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
def inputS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines  

N  = int(input())
XY = [[] for _ in range(N)] # 証言者

for i in range(N):
  A = int(input())
  for _ in range(A):
    ind, bl = map(int, input().split())
    XY[i].append((ind-1, bl))

ans = 0
for bit in range(1<<N):
  cnt = 0
  ok = True
  for i in range(N):
    # i 人目が「不親切」だったら、証言はすべて無意味
    if not bit >> i & 1:
      continue
    # 証言通りかそれぞれ確認
    for x, y in XY[i]:
      # y = 1 なのに「不親切」だったらダメ      
      # y = 0 なのに「正直者」だったらダメ
      if bit >> x & 1 ^ y:
        ok = False
        break
    if ok:
      cnt += 1
    else:
      break
  else:
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
def check(x, y, t):
    if t[x] == -1 or t[x] == y:
        return True
    return False


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

ans = 0
for p in range(2**n):
    b = p
    cnt = 0
    t = [-1] * (n + 1)
    for i in range(n):
        honest = b & 1
        b >>= 1
        if honest:
            if check(i+1, 1 ,t):
                t[i+1] = 1
                cnt += 1
            else:
                cnt = -10**5
                continue
            for x, y in r[i]:
                if t[x] == -1 or t[x] == y:
                    t[x] = y
                else:
                    cnt = -10**5
                    break
            else:
                continue

            break
        else:
            if check(i+1, 0, t):
                t[i+1] = 0
            else:
                cnt = -10**5
    ans = max(cnt, ans)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
A = []
for _ in range(n):
  j = int(input())
  tmp = []
  for _ in range(j):
    x, y = map(int, input().split())
    tmp.append([x, y])
  A.append(tmp)
A = np.array(A)
# print(A)

ans = 0
for i in range(1, pow(2, n)):
  person = [-1 for _ in range(n)]

  b = [int(j) for j in list(format(i, 'b').zfill(n))]
  # print('b', b)
  indices = [i for i, x in enumerate(b) if x == 1]
  state = A[indices]
  # print(state)
  flag_contradiction = False
  for d in state:
    for e in d:
      x, y = e
      # print(b, x-1, y)
      if b[x-1] != y:
        # print('flag')
        flag_contradiction = True
        break
    if flag_contradiction:
      break
  if not flag_contradiction:
    ans = max(ans, sum(b))
  # print(ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
 
n=int(sys.stdin.readline())
dic={}
#辞書作成
for i in range(n):
    a=int(sys.stdin.readline())
    dic[i+1]={}
    for _ in range(a):
        b=list(map(int,sys.stdin.readline().split()))
        dic[i+1][b[0]]=b[1]
 
#最大人数求める。
max=0
for i in range(2**n):
    out=[0]*n
    a=2**(n-1)
    num=0
    #2進数に変換
    for j in range(n):
        if i>=a:
            out[j]=1
            i-=a
            num+=1
        a=a//2
    #判定
    if num>max:
        ju=1
        for j in range(n):
            if out[j]==1:
                for k in dic[j+1].keys():
                    if dic[j+1][k]==out[k-1]:
                        continue
                    else:
                        ju=0
                        break
                if ju==0:
                    break
        if ju==1:
            max=num
print(max)

Submission status: Accepted

Solution code:
import sys

n=int(sys.stdin.readline())
dic={}
#辞書作成
for i in range(n):
    a=int(sys.stdin.readline())
    dic[i+1]={}
    for _ in range(a):
        b=list(map(int,sys.stdin.readline().split()))
        dic[i+1][b[0]]=b[1]

#最大人数求める。
max=0
for i in range(2**n):
    out=[0]*n
    a=2**(n-1)
    num=0
    #2進数に変換
    for j in range(n):
        if i>=a:
            out[j]=1
            i-=a
            num+=1
        a=a//2
    #判定
    if num>max:
        ju=1
        for j in range(n):
            if out[j]==1:
                for k in dic[j+1].keys():
                    if dic[j+1][k]==out[k-1]:
                        continue
                    else:
                        ju=0
                        break
                if ju==0:
                    break
        if ju==1:
            max=num
print(max)

Submission status: Accepted

Solution code:
def flagcount(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count
n=int(input())
g=[[-1]*n for _ in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        g[i][x-1]=y
ans=0
for bit in range(1<<n):
    d=[]#
    for x in range(n):
        if bit&1<<x:
            d.append(1)
        else:
            d.append(0)
    flag=1
    for i in range(n):
        if d[i]:
            for j in range(n):
                if g[i][j]==-1:
                    continue
                if g[i][j]!=d[j]:
                    flag=0
    if flag:
        ans=max(ans,flagcount(bit))     
print(ans)

Submission status: Accepted

Solution code:
# coding: UTF-8
import itertools
import numpy as np

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

# 何人目かを正直者か優しくない人かを判断するためのnp.array
A = np.array(list(itertools.product([0, 1], repeat=N)), np.bool)

for i, x, y in Info:
    bl = (~A[:, i]) | (A[:, x] == bool(y))
    A = A[bl]
answer = A.sum(axis=1).max()
print(answer)

Submission status: Accepted

Solution code:
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(2**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)