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:
import sys
from io import StringIO
import unittest
import os


# 実装を行う関数
def resolve():
    # 数値取得サンプル
    #   1行N項目 x, y = map(int, input().split())
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]
    n = int(input())

    testimonies = [[] for i in range(n + 1)]
    for i in range(n):
        a = int(input())
        testimonies[i+1] = [list(map(int,input().split())) for i in range(a)]

    ans = 0
    # パターン数分ループ。
    for i in range(1 << n):

        unable = False
        # 初期値:一番左の桁の値。
        # result = int(abcd[0:1])
        # パターン数(2進数)の桁数ループ。
        a = 0
        for j in range(n):
            # 嘘つきの発言は評価しない
            if not i & 1 << j:
                continue

            a += 1

            # 正直者の発言は評価する
            for testimony in testimonies[j+1]:

                # 発言の対象者の状態を取得するために必要なビットシフト数を取得
                #  = 1人目は1桁目(ビットシフト0)。2人目は2桁目(ビットシフト1)。となるので-1しておく。
                target = testimony[0] - 1
                # targetは正直だ!　と言っているがtargetが嘘つき => このパターンはありえないので次のパターンへ。
                if testimony[1] == 1 and not i & 1 << target:
                    unable = True
                    break
                # targetは嘘つきだ!　と言っているがtargetは正直 => このパターンはありえないので次のパターンへ。
                elif testimony[1] == 0 and i & 1 << target:
                    unable = True
                    break

            # ありえないパターンと判明した場合、検証を中断して次のパターンへ。
            if unable:
                break

        if unable:
            continue

        ans = max(ans, a)

    print(ans)

# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3
1
2 1
1
1 1
1
2 0"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """2
1
2 0
1
1 0"""
        output = """1"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
n = int(input())
#2**n通りの正直者を全列挙してそれを矛盾が生じないか試していき最大値を求める 競合してる証言をピック　True or False で判断する
jud = [[-1 for i in range(n)] for j in range(n)]
xy = []
ayasi = []
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        jud[i][x-1] = y
Max = 0
for i in range(2**n):
    li = []
    flag = True
    cnt = 0
    for j in range(n):
        if ((i >> j) & 1):
            li.append(1)

        else:
            li.append(0)
    for k in range(n):
        if li[k] == 1:
         for l in range(n):
             if jud[k][l] != -1:
                 if jud[k][l] != li[l]:
                     flag = False
                     break

    if flag:
        Max = max(sum(li),Max)
print(Max)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N = INT()
xy = []

for i in range(N):
	A = INT()
	xy.append([LIST() for _ in range(A)])

ans = 0
for X in product((0, 1), repeat=N):
	for j in range(N):
		if X[j] == 1:
			for x, y in xy[j]:
				if X[x-1] != y:
					break
			else:
				continue
			break
	else:
		ans = max(ans, sum(X))

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N = INT()
xy = []

for i in range(N):
	A = INT()
	xy.append([LIST() for _ in range(A)])

ans = 0
for i in range(1<<N):
	i = list("{:b}".format(i).zfill(N))
	for j in range(N):
		if i[j] == "1":
			for x, y in xy[j]:
				if y != int(i[x-1]):
					break
			else:
				continue
			break
	else:
		tmp = sum([int(x) for x in i])
		ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N = INT()
xy = []

for _ in range(N):
	A = INT()
	xy_A = []
	for _ in range(A):
		xy_A.append(LIST())
	xy.append(xy_A)

ans = 0
for X in product((0, 1), repeat=N):
	honest = [-1]*N
	for j in range(N):
		if X[j] == 0:
			if honest[j] == -1:
				honest[j] = 0
			elif honest[j] == 1:
				break
		elif X[j] == 1:
			if honest[j] == -1:
				honest[j] = 1
			elif honest[j] == 0:
				break

			for x, y in xy[j]:
				if honest[x-1] == -1:
					honest[x-1] = y
				elif honest[x-1] != y:
					break
			else:
				continue
			break
	else:
		ans = max(ans, sum(X))

print(ans)

Submission status: Accepted

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

N = int(readline())
statement = [[] for i in range(N)]
for i in range(N):
  A = int(readline())
  for j in range(A):
    x,y = map(int,readline().split())
    statement[i].append([x - 1,y])
  
# N人の誰が正直者か、全探索して、矛盾がないパターンはOK
ans = 0
for i in range(2 ** N):
  ok = True
  for j in range(N):
    if (i >> j) & 1:
      # 人jのコメントを検証
      for s in statement[j]:
        person = s[0]
        flag = s[1]
        if ((i >> person) & 1) != flag:
          # 間違ってる
          ok = False
          break
    if not ok:
      break
  if ok:
    honest = str(bin(i)).count("1")
    if ans < honest:
      ans = honest
print(ans)

Submission status: Accepted

Solution code:
import itertools
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
xy = []
for _ in range(n):
    m = int(readline())
    tmp = [list(map(int, readline().split())) for _ in range(m)]
    xy.append(tmp)
    
# 逆から
for l in sorted(itertools.product([0, 1], repeat=n),reverse=True):
    bl = True
    for i, a in enumerate(l):
        if a == 1:
            for b in xy[i]:
                if l[b[0] - 1] != b[1]:
                    bl = False
                    break
    if bl:
        print(sum(l))
        exit()
print('0')

Submission status: Accepted

Solution code:
import itertools
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
xy = []
for _ in range(n):
    m = int(readline())
    tmp = [list(map(int, readline().split())) for _ in range(m)]
    xy.append(tmp)

ans = 0

for l in list(itertools.product([0, 1], repeat=n)):
    bl = True
    for i,a in enumerate(l):
        if a == 1:
            for b in xy[i]:
                if l[b[0] - 1] != b[1]:
                    bl = False
    if bl:
        ans = max(ans, sum(l))
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction


def ternary (n, k, length):
    if n == 0:
        nums = ['0' for i in range(length)]
        nums = ''.join(nums)
        return nums
    nums = ''
    while n:
        n, r = divmod(n, k)
        nums += str(r)
    nums = nums[::-1]
    nums = nums.zfill(length)
    return nums

def main():
    num = int(input())
    say_count = []
    say_data = []
    for i in range(num):
        aaa = int(input())
        say_count.append(aaa)
        data = [list(map(int, input().split())) for i in range(aaa)]
        say_data.append(data)


    ans = 0
    for i in range(2 ** num):
        bin_data = list(map(int, ternary(i, 2, num)))
        kari_ans = bin_data.count(1)

        people_flg = [-1 for i in range(num)]
        dame_flg = 0
        for j in range(num):
            if people_flg[j] == -1:
                people_flg[j] = bin_data[j]
            else:
                if people_flg[j] != bin_data[j]:
                    dame_flg = 1

            if people_flg[j] == 0:
                continue

            for k in range(say_count[j]):
                people, flg = say_data[j][k]
                people -= 1
                if people_flg[people] == -1:
                    people_flg[people] = flg
                else:
                    if people_flg[people] != flg:
                        dame_flg = 1

            if dame_flg:
                break
        if dame_flg:
            continue
        ans = max(ans, kari_ans)

    print(ans)






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
shogen=[]
count_ans=[]
for i in range(N):
    A=int(input())
    shogen.append([list(map(int,input().split())) for i in range(A)])
#print(shogen)
def saiki(A):
    if len(A)==N:
        honest=set()
        honest_kari=set()
        unkind=set()
        count=0
        unkind_kari=set()
        for i in range(N):
            if A[i]==1:
                honest.add(i)
            else:
                unkind.add(i)
        for i in range(N):
            if i in honest:
                for j in range(len(shogen[i])):
                    if shogen[i][j][1]==0:
                        unkind_kari.add(shogen[i][j][0]-1)
                    else:
                        honest_kari.add(shogen[i][j][0]-1)
        #print(honest,honest_kari)
        for i in unkind_kari:
            if i in unkind:
                count+=1
        for i in honest_kari:
            if i in honest:
                count+=1
        if count==len(unkind_kari)+len(honest_kari):
            kari=set(list(honest)+list(honest_kari))
            #print(honest,honest_kari,count)
            count_ans.append(len(kari))

        
        return
    for i in range(2):
        A.append(i)
        saiki(A)
        A.pop()
saiki([])
print(max(count_ans))

Submission status: Accepted

Solution code:
n = int(input())
xy = [[] for i in range(n)]
maxh = 0
for i in range(n):
  a = int(input())
  for j in range(a):
    xy[i].append(list(map(int, input().split())))
for i in range(1<<n):
  tmp = [-1] * n
  try:
    for j in range(n):
      if i & (1<<j):
        if tmp[j] == -1:
          tmp[j] = 1
        elif tmp[j] == 0:
          raise
        for k, l in xy[j]:
          if tmp[k-1] == -1:
            tmp[k-1] = l
          elif tmp[k-1] != l:
            raise
      else:
        if tmp[j] == -1:
          tmp[j] = 0
        elif tmp[j] == 1:
          raise
  except:
    pass
  else:
    hoge = tmp.count(1)
    if hoge > maxh:
      maxh = hoge
print(maxh)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
setrecursionlimit(10**6)
def I(): return int(stdin.readline().rstrip())
def LI(): return list(map(int,stdin.readline().rstrip().split()))

def judge(x,y,a,bit):
    for i in range(len(a)):
        if bit&(1<<i):
            for j in range(a[i]):
                if ((bit>>x[i][j])&1)^y[i][j]:
                    return False
    return True

n = I()
a = []
x = []
y = []
for i in range(n):
    A = I()
    a.append(A)
    xt = []
    yt = []
    for _ in range(A):
        tmp = LI()
        xt.append(tmp.pop(0)-1)
        yt.append(tmp.pop(0))
    x.append(xt)
    y.append(yt)

ans = 0
length = 2**n
for i in range(length):
    result = judge(x,y,a,i)
    if result:
        ans = max(ans,bin(i).count('1'))
    
print(ans)

Submission status: Accepted

Solution code:
import numpy as np


N = int(input())
XY = []
ANS = []


for _ in range(N):
    a = int(input())
    tmp = []

    for _ in range(a):
        xy = tuple(map(int, input().split()))
        tmp.append(xy)
    XY.append(tmp)


for b in range(2 ** N):
    status = []
    for i in range(N):
        j = b >> i & 1
        status.append(j)
    status = np.array(status)

    f = 1
    ans = 0

    for i in range(N):
        j = b >> i & 1
        if not j:
            continue
        for x, y in XY[i]:
            s = status[x - 1]
            if s != y:
                f = 0
                break
        if not f:
            break

    if f:
        ans = np.sum(status)
    ANS.append(ans)


print(max(ANS))

Submission status: Accepted

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

def check(ps,honests):
    for x, y in ps:
        x -= 1
        if y == 1 and honests[x] == 0:
            return False
        if y == 0 and honests[x] == 1:
            return False
    return True
        

# 無矛盾かどうかを全探索
ans = 0
for b in range(2**n):
    honests = []
    is_ok = True
    for j in range(n):
        honests.append(b & (1<<j)>0)
    for ps,h in zip(As,honests):
        if h:
            is_ok &= check(ps,honests)
    if is_ok:
        ans = max(ans,sum(honests))
print(ans)

Submission status: Accepted

Solution code:
def main():
    xy = []
    n = int(input())
    for _ in range(n):
        a = int(input())
        xy.append([list(map(int, input().split())) for _ in range(a)])
    ans = 0
    
    for a in range(2**n):
        c = []
        for b in range(n):
            c.append(a >> b & 1)
       
        flag = True
        for i in range(n):
            if c[i] == 1:
                for x, y in xy[i]:
                    if c[x - 1] != y:
                        flag = False
                        
        if flag:
            ans = max(ans, sum(c))
    
    print(ans)
        
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
l=[[float('inf')]*n for i in range(n)]
ans=0
for i in range(n):
  a=int(input())
  for j in range(a):
    x,y=[int(s) for s in input().rstrip().split()]
    l[i][x-1]=y

for i in range(2**n):
  d=[0 for j in range(n)]
  for j in range(n):
    if i>>j & 1:
      d[j]=1
      
  flag=1
  for j in range(n):
    if d[j]==1:
      for k in range(n):
        if l[j][k]==float('inf'):
          continue
        if l[j][k]!=d[k]:
          flag=0

  if flag==1:
    ans=max(ans,sum(d))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[0]*n
x=[[] for i in range(n)]
y=[[] for i in range(n)]
for i in range(n):
  a[i]=int(input())
  for j in range(a[i]):
    tmp = list(map(int,input().split()))
    x[i].append(tmp[0])
    y[i].append(tmp[1])

# 事実をbitで表現する
res=0
for bit in range(2**n):
  p_cnt = 0
  fact = 1
  for i in range(n):
    if bit >> i & 1:
      p_cnt += 1
      for j in range(a[i]):
        if  y[i][j] ^ (bit >> x[i][j] -1) & 1:
          fact=0
          break
  if fact and res < p_cnt:
    res = p_cnt
print(res)

Submission status: Accepted

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

res = 0
for i in range(1 << n):
    p = [-1] * n
    contradiction_flag = False
    for j in range(n):
        if (i >> j) & 1:
            if p[j] == 0:
                contradiction_flag = True
                break
            p[j] = 1

            for person, h_or_u in t[j]:
                if h_or_u == 0:
                    if p[person-1] == 1:
                        contradiction_flag = True
                        break
                    p[person-1] = 0
                else:
                    if p[person-1] == 0:
                        contradiction_flag = True
                        break
                    p[person-1] = 1
        
        else:
            if p[j] == 1:
                contradiction_flag = True
                break
            p[j] = 0
    
    if not contradiction_flag:
        res = max(res, n - p.count(0))

print(res)

Submission status: Accepted

Solution code:
def solve(li):
    for i in range(n):
        if li[i] == 0:
            continue
        else:
            for name, honest in L[i]:
                if li[name-1] != honest:
                    return 0
    else:
        return li.count(1)

n = int(input())
L = []
for _ in range(n):
    a = int(input())
    A = [list(map(int, input().split())) for _ in range(a)]
    L.append(A)
ans = 0
for i in range(2 ** n):
    li = [0] * n
    for j in range(n):
        if ((i >> j) & 1 != 0):
            li[j] = 1
    ans = max(ans, solve(li))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math





n= int(input())



xandy=np.ones((n,n))

xandy=xandy*(-1)

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

max=0


for l in range(0,2**n):
    i=2**n-1-l
    flag=1
    if max<bin(i).count("1"):
        for j in range(0,n):
       
        #iを2進数表示した時kの位置ででの0-1が対応してあるか立っているか？
            if  bin( i& 2**j).count("1")>0:
                 for k in range(0,n):
                      if  xandy[j][k]!=-1 and xandy[j][k]!=(i >> k)%2:
                          flag=0 
                          break
                       
            if flag==0:
                break
        if flag==1 and max<bin(i).count("1"):
             max=bin(i).count("1")
         

print(max)

Submission status: Accepted

Solution code:
n=int(input())
patt=[]  #パターンを格納するためのリスト
for i in range(2 ** n): #全パターンを作る
  bag = []
  for j in range(n):  
    if ((i >> j) & 1):
      bag.append(1)  
    else:
      bag.append(0)
  patt.append(bag)
per=[[-1 for i in range(n)] for l in range(n)] #証言格納用のリストを作っている、発言していないものは-1
for s in range(n): #証言を二次元リストに格納するためのループ
  a=int(input())
  for t in range(a):    
    x, y = map(int, input().split())
    per[s][x-1]=y
ma=0
for i in patt: #一個ずつ、パターンをチェックするためのループ
  check=0
  for l in range(n): #各人の真偽について
    if i[l]==1: #i[l]が正しかった場合
      for t in range(n): #lさんの発言一個一個を確認する
        if per[l][t]!=i[t] and per[l][t]!=-1:
          check=-1
          break
        else:
          continue
  if check==0:
    ma=max(ma, sum(i))
        
print(ma)

Submission status: Accepted

Solution code:
n = int(input())
data = [[[],[]] for _ in range(n)]
ans = 0
for i in range(n):
    a = int(input())
    for _ in range(a):
        x,y = map(int,input().split())
        data[i][y].append(x-1)
for i in range(1,2**n):
    S1 = set([])
    S2 = set([])
    for j in range(n):
        if (i >> j) & 1:
            S1.add(j)
        else:
            S2.add(j)
    flag = True
    for i in S1:
        for j in range(2):
            if data[i][j]:
                if j == 0:
                    for k in data[i][j]:
                        if k in S1:
                            flag = False
                else:
                    for k in data[i][j]:
                        if k in S2:
                            flag = False
    else:
        if flag:
            ans = max(ans,len(S1))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
C - HonestOrUnkind2
https://atcoder.jp/contests/abc147/tasks/abc147_c

"""
import sys


from itertools import product

def solve(N, data):
    ans = 0
    for prd in product([0, 1], repeat=N):
        res = [0] + list(prd)
        is_valid = True
        for i, p in enumerate(prd, start=1):
            if p == 0:
                continue
            for x, y in data[i]:
                if y != res[x]:
                    is_valid = False
                    break
        if is_valid:
            ans = max(ans, sum(res))
    return ans


def main(args):
    N = int(input())
    data = [[] for _ in range(N+1)]
    for a in range(1, N+1):
        for _ in range(int(input())):
            x, y = map(int, input().split())
            data[a].append([x, y])
    ans = solve(N, data)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
N = int(input())
# 出力結果[[(1, 1)], [(0, 1)], []]
evidences = [[] for _ in range(N)]
for i in range(N):
    # i人目の証言A個
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        # 例1だと人1,2,3だからリストで0,1,2になる、yは0が0番目で問題ない
        evidences[i].append((x - 1, y))

result = 0
# 8パターンあって順に縦に回してく
for i in range(1, 2 ** N):
    consistent = True
    # 例題1では3桁を横に回す
    for j in range(N):
      # 例えば3個目の010をj=1ずらして0なら続ける1のフラグが立ってたら次の処理
        if (i >> j) & 1 == 0:
            continue
        # 人2が本当ならそれぞれ証言と照らし合わせて
        for x, y in evidences[j]:
            # 010の場合x=1つまり人1がy=1に対してフラグは立ってないこれは間違い
            if (i >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        # 2進数に変換して最初の0bを消す。フラグの数を数える
        result = max(result, bin(i)[2:].count('1'))
print(result)
# 000　全員嘘つき
# 001 アだけ
# 010 イだけ
# 011 アとイ
# 100 ウだけ
# 101 アとウ
# 110 イとウ
# 111 アイウ全員

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    testify = [[] for _ in range(N)]
    for i in range(N):
        A = int(input())
        for _ in range(A):
            x, y = map(int, input().split())
            testify[i].append((x, y))
    
    ans = 0
    for i in range(2**N):
        honest = set()
        for j in range(N):
            if (i>>j) & 1:
                honest.add(j)
        if len(honest) <= ans:
            continue
        liar = set(range(15)) - honest
        flag = True
        for j in honest:
            honesttmp = set()
            for s, t in testify[j]:
                if t == 1 and s-1 not in honest:
                    flag = False
                    break
                if t == 0 and s-1 in honest:
                    flag = False
                    break
        if flag:
            ans = max(len(honest), ans)
            
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
 
talk = [[] for _ in range(n)]
for i in range(n):
    tmp = int(input())
    for j in range(tmp):
        person, state = map(int, input().split())
        talk[i].append([person-1, state])
#print(talk)

from itertools import product
s = [0,1]
ptns = sorted(list(product(s, repeat=n)), reverse=1)
#print(ptns)

for i in range(len(ptns)):
    for j in range(n):
        if ptns[i][j] == 1: 
            for k in talk[j]:
                if ptns[i][k[0]] != k[1]:
                    break
            else:
                continue
            break
    else:
        print(sum(ptns[i]))
        exit()

Submission status: Accepted

Solution code:
n = int(input())
 
testimony = [[] for _ in range(n)]
for i in range(n):
    tmp = int(input())
    for j in range(tmp):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])
#print(testimony)

from itertools import product
s = [0,1]
ptns = sorted(list(product(s, repeat=n)), reverse=1)
#print(ptns)

for i in range(len(ptns)):
    for j in range(n):
        if ptns[i][j] == 1: 
            for k in testimony[j]:
                if ptns[i][k[0]] != k[1]:
                    break
            else:
                continue
            break
    else:
        print(sum(ptns[i]))
        exit()

Submission status: Accepted

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

# --------------------------
ans = 0
for bit in range(1, 2**n):
    flg = True
    # i人目の証言を検証する
    for i in range(n):
        if not flg:
            break

        # i人目が不親切の場合は検証する意味なし
        if not (bit >> i & 1):
            continue

        # i人目の各証言を確認
        for j in xy[i]:
            x = j[0]
            y = j[1]

            # 証言と矛盾していたらダメ
            # ^ : xor
            # どちらかが１どちらかが０なら、Break
            if (bit >> (x - 1) & 1) ^ y:
                flg = False
                break
    if flg:
        ans = max(ans, bin(bit).count('1'))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
 
testimony = [[] for _ in range(n)]
for i in range(n):
    tmp = int(input())
    for j in range(tmp):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])
#print(testimony)

from itertools import product
s = [0,1]
ptns = list(product(s, repeat=n))
ptns = list(reversed(ptns))
#print(ptns)

for i in range(len(ptns)):
    error = 0
    for j in range(n):
        if ptns[i][j] == 1: 
            for k in testimony[j]:
                if ptns[i][k[0]] != k[1]:
                    error = 1

    if error == 0:
        print(sum(ptns[i]))
        exit()

Submission status: Accepted

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

for i in range(n):
    tmp = int(input())
    for j in range(tmp):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])
#print(testimony)

from itertools import product
s = [0,1]
ptns = sorted(list(product(s, repeat=n)), reverse=1)
#print(ptns)

for i in range(len(ptns)):
    #honest_or_not =[-1]*(n) # [-1, -1, -1]
    error = 0
    for j in range(n):
        if ptns[i][j] == 1: 
            for k in testimony[j]:
                if ptns[i][k[0]] != k[1]:
                    error = 1

    if error == 0:
        print(sum(ptns[i]))
        exit()

Submission status: Accepted

Solution code:
#abc 147 C
import itertools
n = int(input())
word_g = []
for i in range(n):
    m = int(input())
    part_word = []
    for j in range(m):
        part_word.append(list(map(int, input().split())))
    word_g.append(part_word)
#print(word)       
state = list(itertools.product([0,1], repeat = n))  

def abc147c(n, word, i):
    word_i = []
    
    for j1 in range(n):
        if i[j1]  == 0:
            word_i.append([])
        else:
        	word_i.append(word[j1])
          
    
    check_mujun = [[] for i in range(n)]
    
    for j in word_i:
        for k in j:
            check_mujun[k[0] -1].append(k[1])
    
    
    counter = 0
    
    for x, j in enumerate(check_mujun):
        
        if len(set(j)) == 0  :
            counter += i[x]
            
        elif len(set(j)) == 1 and sum(set(j)) == i[x]:
            counter += i[x]
            
        else:
            return -1
            break
    return counter

output = 0 
for i in state:
    output = max(output, abc147c(n,word_g,list(i) ) )
    #print(i, abc147c(n,word_g,i))
print(output)

Submission status: Accepted

Solution code:
N = int(input())
 
testimony = [[] for _ in range(N)]
 
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])
        
honest = 0
for i in range(2**N):
    flag = 0
    for j in range(N):
        if (i>>j)&1 == 1: # j番目は正直と仮定
            for x,y in testimony[j]:
                if (i>>x)&1 != y: # j番目は正直だが矛盾を発見
                    flag = 1
                    break
    if flag == 0:  # 矛盾がある場合はflag == 1になる
        honest = max(honest, bin(i)[2:].count('1'))  # 1の数をカウントし最大となるものを選択
print(honest)