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

ans = 0
for i in range(2 ** n):
    peoples = []
    flag = True
    for j in range(n):
        if (i >> j & 1):
            peoples.append(1)
        else:
            peoples.append(0)
    for k in range(n):
        if peoples[k] == 1:
            words = words_list[k]
            for word in words:
                if peoples[word[0]] != word[1]:
                    flag = False
                    break
    if flag:
        ans = max(ans, sum(peoples))

print(ans)

Submission status: Accepted

Solution code:
def judge(bit, arr):
    for x, y in arr:
        if bit >> x-1 & 1 != y:
            return False
    return True

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, state])

ans = 0
for bit in range(2**N):
    flag = True
    for i in range(N):
        if bit >> i & 1 == 1:
            flag = judge(bit, testimony[i])
            if flag != True:
                break
    
    if flag:
        ans = max(ans, bin(bit).count('1'))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = [[] for x in range(N)]

for i in range(N):
    for _ in range(int(input())):
        idx, t = map(int, input().split())
        T[i].append((idx-1, t))

ans = 0
for i in range(1, 2**N):
    ok = True
    ans_t = 0
    for j in range(N):
        if (i>>j) & 1 == 0:
            continue
        ans_t += 1
        for (x,y) in T[j]:
            if (i>>x) & 1 != y:
                ok = False
                break
        if not ok:
            break
    if ok:
        ans = max(ans, ans_t)
print(ans)

Submission status: Accepted

Solution code:
# abc147_c.py
import sys
import time
import unittest
from io import StringIO

# IS_LOCAL = True  # FIXME: delete this


def resolve():
    N = int(input())
    aa = []
    for i in range(N):
        xy = {}
        aa.append(xy)
        for _ in range(int(input())):
            x, y = [int(i) for i in input().split()]
            xy[x - 1] = 1 == y
    maxsum = 0
    for comb in range(2**N - 1, -1, -1):
        sum = 0
        for i in range(N):
            if (comb >> i) & 1:
                sum += 1
                for x in aa[i].keys():
                    if aa[i][x]:
                        if not ((comb >> x) & 1):
                            break
                    else:
                        if (comb >> x) & 1:
                            break
                else:
                    continue
                break
        else:
            maxsum = max(maxsum, sum)
    print(maxsum)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def checkTLE(self, input):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin

    def debugIO(self, input):
        stdin = sys.stdin
        sys.stdin = StringIO(input)
        resolve()
        sys.stdin = stdin

    def setUp(self):
        self.startTime = time.time()

    def tearDown(self):
        t = time.time() - self.startTime
        print('%s: %.3f' % (self.id(), t), flush=True)

    def test_入力例_1(self):
        input = """3
1
2 1
1
1 1
1
2 0"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2
1
2 0
1
1 0"""
        output = """1"""
        self.assertIO(input, output)


if __name__ == "__main__":
    if "IS_LOCAL" in locals():
        suite = unittest.TestLoader().loadTestsFromTestCase(TestClass)
        unittest.TextTestRunner(verbosity=0).run(suite)
    else:
        resolve()

Submission status: Accepted

Solution code:
n = int(input())
xy = [[] for _ in range(n)]
ans = -float("inf")

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

for i in range(2**n):
	flag = False
	cnt = 0
	for j in range(n):
		if (i >> j) & 1:
			cnt += 1
			for x, y in xy[j]:
				if y == 1:
					if (i >> x & 1) == 0:
						flag = True
				elif y == 0:
					if (i >> x & 1) == 1:
						flag = True
	if not flag:
		ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = [[] for _ in range(n)]
ans = -float("inf")

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

for i in range(1 << n):
	true_or_false = [0] * n
	flag = False
	for j in range(n):
		if (i>>j)&1:
			true_or_false[n-1-j] = 1
	for i, l in enumerate(xy):
		for x, y in l:
			if true_or_false[i] == 1:
				if true_or_false[x-1] != y:
					flag = True
	if not flag:
		ans = max(ans, len([i for i in true_or_false if i == 1]))
print(ans)

Submission status: Accepted

Solution code:
def main():

    N = int(input())

    testimony_person = []
    testimony_judge = []

    for i in range(N):
        n = int(input())
        tmp_person = []
        tmp_judge = []
        
        for j in range(n):
            per, jud = map(int, input().split())
            tmp_person.append(per)
            tmp_judge.append(jud)
        
        testimony_judge.append(tmp_judge)
        testimony_person.append(tmp_person)


    max_honest = 0


    for i in range(2 ** N):
        N_honest = 0
        person_A = [0 for i in range(N)]
        person_T = [-1 for i in range(N)]
        FLAG = 1
        
        
        for j in range(N):

            bits = i >> j
            if (bits & 1):
                N_honest += 1
                person_A[j] = 1
                
                for k in range(len(testimony_person[j])):
                    p = testimony_person[j][k]
                    judge = testimony_judge[j][k]

                    if (person_T[p - 1] == -1):
                        person_T[p - 1] = judge
                    elif (person_T[p - 1] != judge):
                        FLAG = 0
                        break
        
        for i in range(N):
            if (person_T[i] != -1 and person_A[i] != person_T[i]):
                FLAG = 0
                break
        
        
        if (FLAG):
            max_honest = max(max_honest, N_honest)

    print(max_honest)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
xy = [[] for _ in range(n)]
ans = -float("inf")

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

for i in range(2**n):
	true_or_false = [0] * n
	flag = False
	for j in range(n):
		if (i>>j)&1:
			true_or_false[n-1-j] = 1
	for i, l in enumerate(xy):
		for x, y in l:
			if true_or_false[i] == 1:
				if true_or_false[x-1] != y:
					flag = True
	if not flag:
		ans = max(ans, len([i for i in true_or_false if i == 1]))
print(ans)

Submission status: Accepted

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

honest=0
binstr="0" + str(n+2) + "b"
for i in range(2**n):
	hl = list(map(int,format(i,binstr)))
	hl = hl[2:]
	
	flag=True
	
	for j,hatsu in enumerate(hatsugen):
		for hat in hatsu:
			if hat[1] != hl[hat[0]-1]:
				if hl[j] == 1:
					flag = False

	

	if flag:
		honest = max(honest,hl.count(1))

print(honest)

Submission status: Accepted

Solution code:
def solve(N, A, X, Y):
    ret = 0
    for i in range(2 ** N):
        tmp = []
        for j in range(N):
            if i >> j & 1:
                tmp.append(j)
        if not tmp:
            continue

        is_valid = True
        for a_idx in tmp:
            for idx in range(A[a_idx]):
                if (Y[a_idx][idx] and X[a_idx][idx] - 1 not in tmp) \
                        or (not Y[a_idx][idx] and X[a_idx][idx] - 1 in tmp):
                    is_valid = False
                    break
        ret = max(ret, len(tmp)) if is_valid else ret
    return ret

if __name__ == "__main__":
    N = int(input())
    A = []
    X, Y = [], []
    for _ in range(N):
        A.append(int(input()))
        tmp_x, tmp_y = [], []
        for _ in range(A[-1]):
            x, y = map(int, input().split())
            tmp_x.append(x)
            tmp_y.append(y)
        X.append(tmp_x)
        Y.append(tmp_y)
    print(solve(N, A, X, Y))

Submission status: Accepted

Solution code:
"""
有向グラフ, シフト演算
"""

n = int(input())

g = [[0]*15 for i in range(15)]

for i in range(n):
    for j in range(n):
        g[i][j] = -1 # 何も証言されていない状態を-1。入力(1or0)があればその値を代入
for i in range(n):
    m = int(input())
    for j in range(m):
        a, x = map(int, input().split())
        a -= 1
        g[i][a] = x

ans = 0
for i in range(1<<n):
    d = [0]*n
    for j in range(n):
        if i>>j&1: # iのj桁目が1か
            d[j] = 1
    ok = True
    for j in range(n):
        if d[j]:
            for k in range(n):
                if g[j][k] == -1: continue
                if g[j][k] != d[k]: ok = False
    if ok: ans = max(ans, bin(i).count('1'))

print(ans)

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
  honest = 0
  for j in range(N):
    if (i>>j) & 1 == 0:
      continue
    honest += 1
    for x,y in evidences[j]:
      if (i>>x) & 1 != y:
        consistent = False
        break
    if not consistent:
      break
  if consistent:
    result = max(result, honest)
print(result)

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:
import itertools
 
N = int(input())
 
 
As = []
xys = []
for i in range(N):
    tmp = []
    As.append(int(input()))
    for i in range(As[-1]):
        tmp.append(list(map(int, input().split())))
    
    xys.append(tmp)
 
#bit演算の準備
bit_list = list(itertools.product(range(2), repeat = N))
 
#loop
ans = 0 #ansの初期設定
for bit in bit_list:
    unkind_count = 0
    for Aindex, A in enumerate(As):
        if(bit[Aindex] == 0):
            continue #Unkindの意見は参考にしない
        for xy in xys[Aindex]:
#            print(xy)
            #真偽値を値化
            honest_to_unkind = (xy[1] == 0 and bit[xy[0]-1] == 1)
            unkind_to_honest = (xy[1] == 1 and bit[xy[0]-1] == 0)
 
            if(honest_to_unkind or unkind_to_honest):
                unkind_count +=1
    
    if(unkind_count == 0):
#       print("yatta")
        ans = max(ans, sum(bit))
 
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n = int(input())
a = []
xy = []
for i in range(n):
    a.append(int(input()))
    for j in range(a[i]):
        xy.append(list(map(int,input().split())) ) 

cnt = 0
for bit in product([0,1],repeat=n):
    fl = [1] * n #1が正直
    hantei = True
    for i,j in enumerate(bit):
        if j == 1:
            fl[i] = 0
    counter = 0
    for k in range(n):
        for l in range(a[k]):
            #証言が矛盾するか判定する #証言の回し方がおかしい
            if fl[k] == 1 and fl[xy[counter][0]-1] != xy[counter][1]:
                hantei = False
                break
            counter += 1
    if hantei:
        cnt = max(cnt,sum(fl))

print(cnt)

Submission status: Accepted

Solution code:
from itertools import product


def solve(bit):
    for i, j in enumerate(bit):
        if j == 1:
            for x, y in xy[i]:
                if bit[x - 1] != y:
                    return 0
    return sum(bit)


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

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

ans = 0
for bit in product([0, 1], repeat=n):
    ans = max(ans, solve(bit))
print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())


As = []
xys = []
for i in range(N):
    tmp = []
    As.append(int(input()))
    for i in range(As[-1]):
        tmp.append(list(map(int, input().split())))
    
    xys.append(tmp)

#bit演算の準備
bit_list = list(itertools.product(range(2), repeat = N))

#loop
ans = 0 #ansの初期設定
for bit in bit_list:
    unkind_count = 0
    for Aindex, A in enumerate(As):
        if(bit[Aindex] == 0):
            continue #Unkindの意見は参考にしない
        for xy in xys[Aindex]:
#            print(xy)
            #真偽値を値化
            honest_to_unkind = (xy[1] == 0 and bit[xy[0]-1] == 1)
            unkind_to_honest = (xy[1] == 1 and bit[xy[0]-1] == 0)

            if(honest_to_unkind or unkind_to_honest):
                unkind_count +=1
    
    if(unkind_count == 0):
#       print("yatta")
        ans = max(ans, sum(bit))

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
  flag = True
  for j in range(N):
    for k in range(A[j]):
      # 正直者の発言が矛盾しなければ良い
      if (i >> j) & 1:
        if ((i >> (x[j][k]-1)) & 1) != y[j][k]:
          flag = False
          break
  if flag:
    count = sum([int(b) for b in bin(i)[2:]])
    ans = max(ans, count)
print(ans)

Submission status: Accepted

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

maxcount = 0
for i in range(2**N):
    vi = [(i>>k) & 1 for k in range(N)]
    for j in range(N):
        ss = shougens[j]
        is_break = False
        if vi[j]:
            for x, y in ss:
                x -= 1
                if vi[x] ^ y:
                    is_break = True
                    break
        if is_break:
            break
    else:
        # iのビット1の数
        maxcount = max(maxcount, bin(i).count('1'))

print(maxcount)

Submission status: Accepted

Solution code:
n = int(input())

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

ans = 0
def judge(f):
    for i in range(n):
        if flag[i] == 1:
            for j in xy[i]:
                if f[j[0] - 1] != j[1]:
                    return False
        
    return True

for i in range(2 ** n):
    flag = [0] * n
    for j in range(n):
        if i >> j & 1:
            flag[j] = 1
    if judge(flag):
        ans = max(ans, sum(flag))
print(ans)

Submission status: Accepted

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

num_honest = 0
for i in range(2 ** n):
    honests = []
    dishonests = []
    flag = 0
    for j in range(n):
        if flag:
            break
        if i & (1 << j):
            if j not in honests and j not in dishonests:
                honests.append(j)
            elif j in dishonests:
                flag = 1
                break
            for p in depositions[j]:
                a, b = p
                if b == 1:
                    if a not in honests and a not in dishonests:
                        honests.append(a)
                    elif a in dishonests:
                        flag = 1
                        break
                else:
                    if a in honests:
                        flag = 1
                        break
                    elif a not in dishonests:
                        dishonests.append(a)
        elif j in honests:
            flag = 1
            break
        elif j not in dishonests:
            dishonests.append(j)
    if flag == 0:
        num_honest = max(num_honest, len(honests))
print(num_honest)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
shougens = []
for _ in range(N):
    A = int(input())
    s = [] 
    for _ in range(A):
        s.append(tuple(map(int, input().split())))
    shougens.append(s)

maxcount = 0
for li in itertools.product([0, 1], repeat=N):
    for man, shojiki in enumerate(li):
        ss = shougens[man]
        is_break = False
        for x, y in ss:
            x = x - 1
            if shojiki and li[x] != y:
                # 現在のパターンと矛盾した場合
                is_break = True
                break
            
        if is_break:
            break
    else:
        # iのビット1の数
        maxcount = max(maxcount, sum(li))

print(maxcount)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import sys
import math

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())

# honest_claims[claimer] = a list of honest persons who claimee claims
honest_claims = [0 for _ in range(N)]
unkind_claims = [0 for _ in range(N)]

for i in range(N):
    A = int(input())
    for _ in range(1,A+1):
        j,claim = list(map(int, input().split()))
        if claim == 1:
            honest_claims[i] |= 1<<(j-1)
        else:
            unkind_claims[i] |= 1<<(j-1)

#print([bin(i) for i in honest_claims])
#print([bin(i) for i in unkind_claims])

def get_unkind_claim(honests):
    unkinds = 0
    i = 0
    for _ in range(N):
        if honests & 1 > 0:
            unkinds |= unkind_claims[i]
        honests = honests >> 1
        i += 1
    return unkinds

def get_honest_claim(honests):
    honest_claim = 0
    i = 0
    for _ in range(N):
        if honests & 1 > 0:
            honest_claim |= honest_claims[i]
        honests = honests >> 1
        i += 1
    return honest_claim

def count_1(honests):
    count = 0
    while(honests>0):
        if honests & 1 > 0:
            count += 1
        honests = honests >> 1
    return count

max_honests = 0

for honests in range(1,2**N):
    unkind_claim = get_unkind_claim(honests)
    honest_claim = get_honest_claim(honests)
    if unkind_claim & honests > 0:
        continue
    if (honest_claim | honests) > honests:
        continue
    else:
        max_honests = max(max_honests, count_1(honests))

print(max_honests)

Submission status: Accepted

Solution code:
n = int(input())
XY = []
for _ in range(n):
    a = int(input())
    XY.append([list(map(int, input().split())) for __ in range(a)])
ans = 0
for i in range(1, 2 ** n):
    S = []
    F = []
    for j in range(n):
        if i >> j & 1:
            S.append(j + 1)
        else:
            F.append(j + 1)
    consistent = True
    for s in S:
        xy = XY[s - 1]
        for x, y in xy:
            if y == 1 and x in F: consistent = False
            if y == 0 and x in S: consistent = False
    if consistent:
        ans = max(ans, len(S))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

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

ans = 0
for bit in product([0, 1], repeat=n):
    f = 0
    for i, j in enumerate(bit):
        if j == 1:
            for x, y in xy[i]:
                if bit[x - 1] != y:
                    f = 1
                    break
    if f == 0:
        ans = max(ans, sum(bit))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

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

ans = 0
for bit in product([0, 1], repeat=n):
    f = 0
    for i, j in enumerate(bit):
        if j == 1:
            for x, y in xy[i]:
                if bit[x - 1] != y:
                    f = 1
    if f == 0:
        ans = max(ans, sum(bit))
print(ans)

Submission status: Accepted

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

ans = 0


for i in range(1 << N):
    ansi = 0
    flag = True
    for j in range(N):
        peoplei = 0
        if (i & 1 << j):
            peoplei = 1
            ansi += 1
        for k in range(N):
            if (i & 1 << k):
                if(people[k][j] != -1 and people[k][j] != peoplei):
                    flag = False

    if flag:
        ans = max(ans, ansi)


print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
n = int(input())
a = []
xy = []
for _ in range(n):
    tmp_a = int(input())
    tmp_xy = [[int(i) for i in readline().split()] for _ in range(tmp_a)]
    a.append(tmp_a)
    xy.append(tmp_xy)
    
from itertools import product

ans_list = []

for comb in product([1,0], repeat=n):
    lie_list = [-1]*n
    flag = True
    for i in range(n):
        if comb[i] == 1:
            if lie_list[i] == -1:
                lie_list[i] = 1
            elif lie_list[i] == 1:
                pass
            elif lie_list[i] != 1:
                flag = False
                break
            for x,y in xy[i]:
                if lie_list[x-1] == -1:
                    lie_list[x-1] = y
                elif lie_list[x-1] == y:
                    pass
                elif lie_list[x-1] != y:
                    flag = False
                    break
        else:
            if lie_list[i] == -1:
                lie_list[i] = 0
            elif lie_list[i] == 0:
                pass
            elif lie_list[i] != 0:
                flag = False
                break
    if flag:
        ans_list.append(sum(comb))

if ans_list:
    print(max(ans_list))
else:
    print(0)

Submission status: Accepted

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

ans = 0
for p in itertools.product([0, 1], repeat=n):
    for ll in l:
        if p[ll[0]] == 1 and p[ll[1]] != ll[2]:
            break
    else:
        ans = max(ans, sum(p))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
XY = []
honest_count = []

for i in range (N):
    a = int(input())
    A.append(a)
    inter = []
    for x in range(a):
        xy = list(map(int, input().split()))
        inter.append(xy)
    XY.append(inter)

for i in range(2 ** N):
    pt = [0] * N
    ck = 1
    for j in range(N):
        if (i >> j) & 1:
            pt[N - j - 1] = 1

    for k in range(N): # k人目が正直者の場合チェック
        if pt[k] == 1:
            for l in range(A[k]):
                if XY[k][l][1] != pt[XY[k][l][0] - 1]:
                    ck = 0
    if ck == 1:
        honest_count.append(sum(pt))


print(max(honest_count))

Submission status: Accepted

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

ans = 0
for p in itertools.product([0, 1], repeat=n):
    for ll in l:
        if p[ll[0]] == 1 and p[ll[1]] != ll[2]:
            break
    else:
        ans = max(ans, sum(p))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
say = {}
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        xy.append(list(map(int,input().split())))
    say[i] = xy
ans = 0
for i in range(2 ** n):
    c = [0 for i in range(n)]
    p = 0
    for j in range(n):
        # 順に右にシフトさせ最下位bitのチェックを行う
        if ((i >> j) & 1):
            # フラグが立っていた時の処理
            c[j] = 1
    #print(c)
    for j in range(n):
        # 順に右にシフトさせ最下位bitのチェックを行う
        if ((i >> j) & 1):
            # フラグが立っていた時の処理
            if c[j] == -1 or c[j] == 1:
                c[j] = 1
            else:
                p = 1
                #print(j,1)
                break
            for k in say[j]:
                if c[k[0]-1] == -1:
                    c[k[0]-1] = k[1]
                elif c[k[0]-1] != k[1]:
                    p = 1
                    #print(j)
                    break
        #print(c,i)
        if p == 1:
            break
    if p == 0 and ans < c.count(1):
        ans = c.count(1)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [[] for _ in range(n)]
for i in range(n):
    a_ = int(input())
    for _ in range(a_):
        a[i].append(list(map(int, input().split())))
ans = 0
for i in range(1, 2**(n)):
    b = str(bin(i, )[2:]).zfill(n)
    t = True
    for idx, j in enumerate(b):
        if not t: break
        if j == "0": continue
        for a_i in a[idx]:
            if b[a_i[0]-1] != str(a_i[1]):
                t = False
                break
    if t:
        ans = max(ans, b.count("1"))
print(ans)

Submission status: Accepted

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

mx = 0

#bit探索
bit = 2**n
for i in range(bit):
    muzyun = 0
    dist = [False for i in range(n)]
    for j in range(n):
        if ((i>>j) & 1):
            dist[j] = True
    for j in range(n):
        if ((i>>j) & 1):
            tnt = lis[j]
            for k in tnt:
                if k[1] ==1 and dist[k[0]-1] == False:
                    muzyun = 1
                if k[1] ==0 and dist[k[0]-1] == True:
                    muzyun = 1
    if muzyun ==0:
        mx = max(dist.count(True),mx)

print(mx)

Submission status: Accepted

Solution code:
N = int(input())
check = list()
for i in range(N):
    a = int(input())
    tmp = list()
    for j in range(a):
        tmp.append(list(map(int,input().split())))
    check.append(tmp)
lis = ["0"*(N-len(format(i,"b")))+format(i,"b") for i in range(2**N)]

result = 0
for i in lis:
    checker = 1
    for j in range(len(i)):
        if checker == 0:
            break
        if i[j] =="1":
            for k in range(len(check[j])):
                if i[check[j][k][0]-1] != str(check[j][k][1]):
                    checker = 0
                    break
        
    if checker ==1 and result < i.count("1"):
        result = i.count("1")
print(result)

Submission status: Accepted

Solution code:
from itertools import product
#初期入力
N = int(input())
testimony ={j:[-1 for i in range(N)] for j in range(1,N+1)}
A=[]
for i in range(1,N+1):
    a = int(input())
    A.append(a)
    for j in range(a):
        x,y = list(map(int, input().split()))
        testimony[i][x-1] =y

#各人が正直か不親切かを仮定する。仮定(Assumption)が矛盾するか、判定を全探索

assumption_correct =[]
for assumption in product([1,0], repeat=N):
    count_2=0
    for i in range(N):      #証言する人        
        if assumption[i] ==1:
            count =0 
            for j in range(N):  #証言受けた人 
                         
                if testimony[i+1][j] ==assumption[j]:
                    count +=1
            if count == A[i]:
                count_2 +=1
    if count_2 ==sum(assumption):
        assumption_correct.append(sum(assumption))
print(max(assumption_correct))

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools

import math
import itertools

# -1 no ans
# 1 syoziki
# 0 hu sinsetu

N = int(input())
ans = [[-1] * N for i in range(N)]


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


def is_ok(num):
    # -1 not decided
    # 1 syoziki
    # 0 husinsetu
    people = []
    for i in range(N):
        if (num >> i) & 1:
            people.append(1)
        else:
            people.append(0)


    for i in range(N):
        if people[i] == 1:
            for j in range(N):
                if ans[i][j] == 1 and people[j] != 1:
                    return False
                if ans[i][j] == 0 and people[j] != 0:
                    return False
    return True


    # people = [-1] * N
    # for i in range(N):
    #     # i is syoziki
    #     if((num >> i) & 1):
    #         if(people[i] == 0):
    #             return False
    #         people[i] = 1
    #         for j in range(N):
    #             if(ans[i][j] == 1):
    #                 if(people[j] == 0):
    #                     return False
    #                 people[j] = 1
    #             if(ans[i][j] == 0):
    #                 if(people[j] == 1):
    #                     return False
    #                 people[j] = 0
    #     else:
    #         if(people[i] == 1):
    #             return False
    #         people[i] = 0

    # return True


def countBit(num):
    ori = num
    count = 0
    while(num > 0):
        if(num & 1):
            count += 1
        num = num >> 1
    return count


out = 0

for i in range(1 << N):
    if(is_ok(i)):
        out = max(out, countBit(i))

print(out)