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:

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


# show_flg = False
show_flg = True

p = None
XY = None
N = None


def dfs(XY, cur, ans_list):
    if cur == N:
        # show(ans_list, len([i for i in ans_list if i != 0]))
        return len([i for i in ans_list if i != 0])

    flag = True
    _ans_list = [i for i in ans_list]
    for xy in XY[cur]:
        if _ans_list[xy[0]-1] == -1 or _ans_list[xy[0]-1] == xy[1]:
            _ans_list[xy[0]-1] = xy[1]
        else:
            flag = False

    ret0 = 0
    ret1 = 0

    if flag:
        if _ans_list[cur] == -1 or _ans_list[cur] == 1:
            _ans_list[cur] = 1
            ret0 = dfs(XY, cur+1, _ans_list)

    _f_ans_list = [i for i in ans_list]
    # _f_ans_list[cur] = 0
    if _f_ans_list[cur] == -1 or _f_ans_list[cur] == 0:
        _f_ans_list[cur] = 0
        ret1 = dfs(XY, cur+1, _f_ans_list)

    return max(ret0, ret1)


def main():
    global p
    global XY
    global N
    N = I()
    XY = [[] for i in range(N)]
    p = [[] for i in range(N+1)]

    for i in range(N):
        a = I()
        for j in range(a):
            x, y = MI()
            XY[i].append((x, y))
            p[x].append(y)

    # print(XY)
    print(dfs(XY, 0, [-1] * N))
    # flag = True
    # for i in range(1, len(p)):
    #     if len(p[i]) == 1 and p[i][0] == 0:
    #         flag = flag and True
    #     else:
    #         flag = flag and False

    # if flag:
    #     print(1)
    #     return

    # ans = 0
    # for i in range(1, len(p)):
    #     # print(sum(p[i]), len(p[i]))
    #     if sum(p[i]) == len(p[i]):
    #         ans += 1

    # print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    # input
    n = int(input())

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

    # calc
    ans = 0
    flag = False
    for num in range(1, 2**n):
        num = bin(num)[2:].rjust(n, '0')
        for i in range(len(li)):
            if num[i] == '1':
                for j, key in enumerate(li[i]):
                    if num[key-1] != str(li[i][key]):
                        flag = True
                        break
                if flag:
                    flag = False
                    break
        else:
            # print(num, ans)
            ans = max(num.count('1'), ans)
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
p = [[] for j in range(n)]
for i in range(n):
    ai = int(input())
    for j in range(ai):
        xij, yij = map(int, input().split())
        p[i].append([xij -1, yij])
cands = []
ans = 0
def bits(l):
    if len(l) == n:
        cands.append(l)
        return
    bits(l + [0])
    bits(l + [1])
bits([])
for cand in cands:
    f = 0
    for i, man in enumerate(cand):
        if man:
            for x, y in p[i]:
                if cand[x] != y:
                    f = 1
                    break
        if f:
            break
    if not f:
        ans = max(ans, sum(cand))
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict
import itertools
 
d = defaultdict(list)
N = int(stdin.readline().rstrip())
p = [[0,1] for i in range(N)]
 
for i in range(N):
    A = int(stdin.readline().rstrip())
    for j in range(A):
        x,y = [int(x) for x in stdin.readline().rstrip().split()]
        d[i].append((x,y))
ans = 0
 
for ind,i in enumerate(itertools.product(*p)):
    cnt = 0
    flag = True
    for m in range(N):
        if i[m] == 1:
            for j,k in d[m]:
                if i[j-1] != k:
                    flag = False
            if flag:
               cnt += 1
        else:
            continue
    if flag:
       ans = max(ans,cnt)
    cnt = 0
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [0] * N
data = [[] for _ in range(N)]
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        new = list(map(int,input().split()))
        new[0] -= 1
        data[i].append(new)

m = -1
for n in range(2**N):
    nn = n
    cur = [0] * N
    for i in range(N):
        cur[i] = nn % 2
        nn = nn // 2
    s = sum(cur)
    if s <= m:
        continue
    det = 1
    for i in range(N):
        if cur[i] == 0:
            continue
        for j in range(A[i]):
            if data[i][j][1] != cur[data[i][j][0]]:
                det = 0
                break
        if det == 0:
            break
    if det == 1:
        m = s
    #print(cur,s,det)

#print(data)
print(m)

Submission status: Accepted

Solution code:
from itertools import product

def main():
    n = int(input())
    a = []
    ls = []
    ans = 0
    for _ in range(n):
        ai = int(input())
        a.append(ai)
        ls.append([tuple(map(int, input().split())) for i in range(ai)])
    ptns = list(product([0,1], repeat=n))
    for ptn in ptns:
        flag = 0
        lsls = list(ptn)
        for j in range(n):
            if ptn[j] == 1:
                for i in range(a[j]):
                    if ls[j][i][1] == 1 and lsls[ls[j][i][0]-1] == 1:
                        lsls[ls[j][i][0]-1] *= ls[j][i][1]
                    elif ls[j][i][1] == 0 and lsls[ls[j][i][0]-1] == 0:
                        lsls[ls[j][i][0]-1] *= ls[j][i][1]
                    else:
                        flag = 1
        if flag == 0:
            if list(ptn) == lsls:
                if ans < sum(ptn):
                    ans = sum(ptn)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

flg = False
for _ in range(N):
    a = int(input())
    comment = [[int(_) for _ in input().split()] for i in range(a)]
    if a:
        flg=True
    C.append(comment)
if not flg :
    print(N)
    exit()


def bit_tbl2(length):
    _format = "{:0" + str(length) + "b}"
    for i in range(int('1' * length, 2) + 1):
        yield _format.format(i)


ans = 0
for b in bit_tbl2(N):
    # print(b)
    syo = [-1] * (N + 1)
    flg = False

    for i in range(N):
        if b[i] == '1':
            syo[i+1] = 1

    for i in range(N):
        if b[i] != '1': continue

        for x, y in C[i]:
            if y == 1 and syo[x] != 1:
                flg = True
                break
            if syo[x] != -1 and y != syo[x]:
                flg = True
                break
            syo[x] = y

        if flg: break

    if not flg:

        v = 0
        for x in syo:
            if x == 1: v += 1
        # print(v)

        ans = max(ans, v)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

word = []

for i in range(N):
  A = int(input())
  B = []
  for i in range(A):
    x = list(map(int, input().split()))
    B.append(x)
  word.append(B)
answer = 0
for i in range(2**N):
  check = True
  a = format(i, 'b').zfill(N)
  count = 0
  for j in range(len(a)):
    if a[j] == "1":
      count += 1
      for x, y in word[j]:
        if not int(a[x-1]) == y:
          check = False
  if check == True:
    answer = max([answer, count])
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
A = [0] * N
B = []
for n in range(N):
    A[n] = int(input())
    bn = []
    for i in range(A[n]):
        x, y = map(int, input().split())
        bn.append((x-1, y))
    B.append(bn)

ans = 0
# bit & (1 << n) で n 番目の 0,1
for bit in range(1 << N):
    ok = [False] * N
    for n in range(N):
        if ((bit >> n) & 1) == 1:
            if all([((bit >> B[n][i][0]) & 1) == B[n][i][1] for i in range(A[n])]):
                ok[n] = True
        else:
            ok[n] = True
    if all(ok):
        ans = max(ans, sum(list(map(int, format(bit, "b")))))

print(ans)

Submission status: Accepted

Solution code:
import sys
n = int(input())
a_dict = {i : {0 : [i], 1:[]} for i in range(n)}
for i in range(n):
    a = int(sys.stdin.readline().strip())
    for j in range(a):
        x, y = [int(i) for i in sys.stdin.readline().split()]
        x -= 1
        if y == 1:
            a_dict[i][0].append(x)
        else:
            a_dict[i][1].append(x)
best = 0
for i in range(1 << n):
    true_set = set()
    false_set = set()
    _i = bin(i)[2:].zfill(n)
    for j, k in enumerate(_i[::-1]):
        if k == "1":
            t = a_dict[j][0]
            f = a_dict[j][1]
            if true_set.intersection(set(f)) or false_set.intersection(set(t)):
                true_set = {}
                break
            true_set.update(t)
            false_set.update(f)
    res = "".join(["0" if i not in true_set else "1" for i in range(n)])[::-1]
    res = len(true_set) if res == _i else 0
    best = max(best, res)
print(best)

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
anslist = []
ret = []
for i in range(N):
    A = int(input())
    tmp = []
    for j in range(A):
        X = list(input().split())
        tmp.append(X)
    anslist.append(tmp)

for i in range(2**N):
    ans = 0
    op = []
    for j in range(N):
        if ((i >> j) & 1) == 1:
            op.append("1")
        else:
            op.append("0")
    
    flag = 0
    for j in range(N):
        if op[j] == "1":
            for k in anslist[j]:
                if op[int(k[0])-1] != k[1]:
                    flag = 1
    if flag == 0:
        ret.append(op.count("1"))

print(max(ret))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
A = []
for i in range(N):
	tmp = []
	n = INT()
	shougen = []
	for j in range(n):
		shougen = MAP()
		tmp.append(shougen)
	A.append(tmp)

cand = []
for i in range(2**N):
	shojiki = [0]*N
	for j in range(N):
		if (i>>j & 1):
			shojiki[N-j-1]=1
	cand.append(shojiki)
# print(cand)

ans = []
for c in cand:
	list = [-1]*(N+1)
	success = True
	ones = [a for idx,a in enumerate(A) if c[idx]==1]
	for idx,a in enumerate(ones):
		for aa in a:
			if list[aa[0]] == -1:
				list[aa[0]] = aa[1]
			else:
				if list[aa[0]]!=aa[1]:
					success=False
	for k in range(len(c)):
		if c[k]==1 and list[k+1]==0:
			success = False
		if c[k]==0 and list[k+1]==1:
			success = False
	if success:
		#print(c, list)
		ans.append(sum(c))
	
#print(ans)
if ans:
	print(max(ans))
else:
	print(0)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
A = [[] for i in range(N)]

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

for i in range(N):
    B = itertools.combinations(range(N), i)
    for b in B:
        state = [1] * N
        for bb in b:
            state[bb] = 0
        flag = True
        for j in range(N):
            if j in b:
                continue
            for (x, y) in A[j]:
                if state[x] != y:
                    flag = False
        if flag:
            print(N - i)
            exit()
print(0)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
input = sys.stdin.readline
N = int(input())
A = [i for i in range(N)]
XY = [[] for n in range(N)]

for n in range(N):
    A[n] = int(input().strip())
    for a in range(A[n]):
        x, y = [int(x) for x in input().strip().split()]
        XY[n].append((x, y))

ans = 0
def check(honests, A, XY, N):
    #print('in check(honests: {})'.format(honests))
    honest = [0] * N
    for h in honests:
        honest[h] = 1
    f = True
    for nn in range(N):
        if nn not in honests:
            continue
        #print('nn = {}'.format(nn))
        xy = XY[nn][:]
        #print('  honest={}'.format(honest))
        for x, y in xy:
            if x-1 in honests and y == 0:
                #print('x = {}, break'.format(x))
                f = False
                break
            elif honest[x-1] != y:
                #print('xxxx')
                f = False
                break
        #print('  honest={}'.format(honest))
        if not f:
            break
    else:
        return True
    return False

for n in range(N, 0, -1):
    for honests in combinations(range(N), n):
        if check(honests, A[:], XY[:], N):
            print(n)
            exit()
else:
    print(0)

Submission status: Accepted

Solution code:
N = int(input())
A = [dict() 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
    A[i][x] = y

# print(A)
res = 0
for i in range(1,2 ** N):
  i_bin = bin(i)[2:]
  i_bin = i_bin.zfill(N)
  p = [0] * N
  for j in range(N):
    p[j] = int(i_bin[j])
  isPossible = True
  for j in range(N):
    x = i_bin[j]
    if x == '1':
      for k, v in A[j].items():
        if p[k] != v:
          isPossible = False
          break
  if isPossible:
    res = max(res, sum(p))

print(res)

Submission status: Accepted

Solution code:
def sol():
    n=int(input())
    w=[[] for i in range(n)]
    for i in range(n):
        a=int(input())
        for j in range(a):
            x,y=map(int,input().split())
            w[i].append((x,y))
    #print(w)
    ans=0
    for i in range(1<<n):
        x="0"*15+bin(i)[2:]
        x=x[-n:]
        f=1
        z=list(x)
        f=1
        for p,q in enumerate(w):
            #print(p,q)
            #break
            if z[p]=='1':
                for r in q:
                    if (x[r[0]-1]=='1' and r[1]==1) or (x[r[0]-1]=='0' and r[1]==0):
                        pass
                    else:
                        f=0
        if f:
            ans=max(ans,z.count('1'))
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
N = int(input())
lst = []
for i in range(N):
    a = int(input())
    xy = [[int(x) for x in input().split()] for _ in range(a)]
    lst.append(xy)
ans = 0
for i in range(1, 2**N):
    f = 1
    tmp = [i >> j & 1 for j in range(N)]
    cnt = sum(tmp)
    for i, yi in enumerate(tmp):
        if (yi == 0): continue
        if any([tmp[x-1] != y for x, y in lst[i]]):
            f = 0
            break
    if (f): ans = max(cnt, ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N = int(input())
sug=[]
#print(sug)
for i in range(N):
  sug.append([])
  A = int(input())
  for j in range(A):
    sug[i].append(list(map(lambda x: int(x),input().split())))
#print(sug)
  
bi = [1,0]
x = itertools.product(bi,repeat=N)
max_honest=0
for i in x:
  #print(i)
  flag=True
  for idx in range(N):
    if i[idx]==1:
      for candidate in sug[idx]:
        if i[candidate[0]-1] != candidate[1]:
          flag=False
          break
      if not flag:
        continue
  if not flag:
    continue
  if max_honest<sum(i):
    max_honest=sum(i)
print(max_honest)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
xy=[[] for i in range(n)]
ans=0 #最大値が答え

for i in range(n):
    aa=int(input())
    a.append(aa)
    for j in range(aa):
        xx,yy=map(int,input().split())
        xy[i].append([xx-1,yy])
#print(xy)

for i in range(pow(2,n)): 
    who=[0]*n #最初はみんな嘘つき
    count=0
    syoujiki=0
    for j in range(n-1,-1,-1): #誰が正直か
        if (i>>j)&1:
            who[count]=1
            syoujiki+=1
        count+=1
    #print(i)
    #print(who)
    check=0
    for j in range(n):
        if who[j]==0: #嘘つきなら無視
            continue
        num=a[j]#正直者jの情報量
        for k in range(num):
            if who[xy[j][k][0]]!=xy[j][k][1]:
                check=1
                break
        if check==1:
            break
    if check==0 and syoujiki>ans:
        ans=syoujiki
print(ans)
#print(xy)

Submission status: Accepted

Solution code:
n=int(input())

xy_list=[]
a_list=[]
for i in range(n):
    a=int(input())
    a_list.append(a)
    xy=[]
    for j in range(a):
        xy.append(input().split(" "))

    xy_list.append(xy)

maxn=0
b=[0]*n
for i in range(2**n):
    b=str(format(i,'b').zfill(n))
    out=0
    for j in range(n):
        if b[j]=="0":continue
        for k in range(a_list[j]):
            x=int(xy_list[j][k][0])
            y=str(xy_list[j][k][1])

            if b[x-1]!=y:
                out=1
                break
        
        if out==1:
            break
    
    if out == 0:
        maxn=max(maxn,b.count("1"))

print(maxn)

Submission status: Accepted

Solution code:
n=int(input())
a_list_sum = []
for i in range(n):
    a_tmp=int(input())
    a_list_tmp=[list(map(int,input().split())) for _ in range(a_tmp)]
    a_list_sum_tmp=[]
    a_list_sum_tmp.append(a_tmp)
    a_list_sum_tmp.append(a_list_tmp)
    a_list_sum.append(a_list_sum_tmp)
    
import itertools
L = [0, 1] #生成する数字
bit_list = list(itertools.product([0, 1], repeat=n))

for i in range(len(bit_list)):
    count = 0
    for j in range(len(a_list_sum)):
        if bit_list[i][j] == 1:
#             print(a_list_sum[j][1])
            for k in range(len(a_list_sum[j][1])):
                person_id = a_list_sum[j][1][k][0] - 1
                is_honest = a_list_sum[j][1][k][1]
                if bit_list[i][person_id] != is_honest:
                    count += 1
    if count == 0:
        ans = sum(bit_list[i])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
data = [0 for i in range(N+1)]
A = [[[int(j) for j in input().split()] for i in range(int(input()))] for k in range(N)]
#print(A)
count = 0



while data[-1] != 1:
    g = 0
    #print(data)
    for i,j in enumerate(data):
        #print(i)
        if j == 1:
            for k in A[i]:
                if k[1] != data[k[0]-1]:
                    g = 1
                    #print(k[1],data[k[0]-1])
    if g == 0:
        count = max(sum(data),count)
    data[0]+=1
    for i,j in enumerate(data):
        if j == 2:
            data[i],data[i+1]=0,data[i+1]+1
            
print(count)

Submission status: Accepted

Solution code:
n=int(input())
shogen=[]
a=[]
max=0
#正直者が1、不親切が0

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

for i in range(2**n):#全探索
	shojiki=[]
	for l in reversed(range(n)):
		shojiki.append(i//(2**l))
		i=i%(2**l)
	ninzu=0
	kekka=1
	#judge=[-1 for j in range(n)]
	for j in range(n):#全員調べる
		if shojiki[j]==1:
			ninzu+=1
			for k in range(a[j]):#j人目について
				# if judge[shogen[j][k][0]-1]==-1:
					# judge[shogen[j][k][0]-1]=shogen[j][k][1]
				# elif judge[shogen[j][k][0]-1]!=shogen[j][k][1]:
					# kekka=0
				if shojiki[shogen[j][k][0]-1]!=shogen[j][k][1]:
					kekka=0
					break
			if kekka==0:
				break
	if kekka==0:
		ninzu=0
	if ninzu>max:
		max=ninzu

print(max)

Submission status: Accepted

Solution code:
N = int(input())
xy = []
for i in range(N):
    t = []
    A = int(input())
    for l in range(A):
        t.append(list(map(int,input().split())))
    xy.append(t)
ans = 0
for i in range(2**N):
    p = []
    for l in range(N):
        if ((i >> l) & 1) == 1:
            p.append(1)
        else:
            p.append(0)
    c = 0
    if sum(p) > ans:
        for l in range(N):
            if p[l] != 0:
                for j in xy[l]:
                    if p[j[0] - 1] != j[1]:
                        c = 1
        if c == 0 and p != [1,1,1]:
            ans = sum(p)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
N = int(input().strip())
shogen = [[-1 for _ in range(N)] for j in range(N)]
for i in range(N):
    size = int(input().strip())
    for j in range(size):
        k, tf = map(int, input().strip().split())
        k -= 1
        shogen[i][k] = tf

def dfs(bp, k):
    if k == N:
        # 矛盾なら0 そうでないならbp = Trueの数を返す
        for i in range(N):
            if not bp[i]:
                continue
            for j in range(N):
                if shogen[i][j] == 1 and not(bp[j]):
                    return 0
                if shogen[i][j] == 0 and bp[j]:
                    return 0
        cnt = 0
        for i in range(N):
            if bp[i]:
                cnt += 1
        return cnt
    """
    #　矛盾チェック
    mujun = False
    for j in range(N):
        if j == k:
            for l in range(N):s
                if shogen[k][l] == 0
        else:
            if shogen[j][k] == 0:
                mujun = True
                break

    """
    bp[k] = True
    tmp1 = dfs(bp, k + 1)
    bp[k] = False
    tmp2 = dfs(bp, k + 1)

    return max(tmp1, tmp2)

tmp_bp = [False] * N
ans = dfs(tmp_bp, 0)
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8

#data = list(map(int, input().split(" ")))

def check_honest(bits):
    honest = [-1 for _ in range(n)]
    for j in range(n):
        if bits[j] == "1":
            if honest[j] == 0:
                return False
            honest[j] = 1
            for ans in all[j]:
                if honest[ans[0] - 1] == -1:
                    honest[ans[0] - 1] = int(ans[1])
                elif honest[ans[0] - 1] != int(ans[1]):
                    return False
        else:
            if honest[j] == 1:
                return False
            honest[j] = 0
    else:
        return True
    
    
n = int(input())

all = []
for _ in range(n):
    total_ans = int(input())
    answers = []
    for _ in range(total_ans):
        answers.append(list(map(int, input().split(" "))))
    all.append(answers)


for i in reversed(range(2 ** n)):
    bits = str(bin(i))[2:].zfill(n)
    if check_honest(bits):
        print(bits.count("1"))
        break
else:
    print("0")

Submission status: Accepted

Solution code:
import copy

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

#print(xy)

tr = [[]]
for i in range(N):
    tr[0].append(-1)
#print(tr)
    
for i in range(len(xy)):
    for j in xy[i]:
        this_tr = []
        for k in tr:
            if j[1] == 1:
                if k[j[0]-1] != 0 and k[i] != 0:
                    #print("A")
                    this_k = copy.deepcopy(k)
                    this_k[j[0]-1] = 1
                    this_k[i] = 1
                    this_tr.append(this_k)
            else:
                if k[j[0]-1] != 1 and k[i] != 0:
                    #print("B")
                    this_k = copy.deepcopy(k)
                    this_k[j[0]-1] = 0
                    this_k[i] = 1
                    this_tr.append(this_k)
            if k[i] != 1:
                #print("C")
                this_k = copy.deepcopy(k)
                this_k[i] = 0
                this_tr.append(this_k)
        tr = copy.deepcopy(this_tr)
        #print(tr)
            
#print(tr)
max_c = 0
for i in tr:
    count = 0
    for j in i:
        if j == 1 or j == -1:
            count += 1
    max_c = max(max_c ,count)
print(max_c)

Submission status: Accepted

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


ans = 0
# print(singi)
for i in range(2 ** N):
    singi = [-1] * (N + 1)
    bin_ = bin(i)[2:].zfill(N)
    flag = True
    for j in range(1, N + 1):
        sin = int(bin_[j - 1])
        person = j
        num = A[j-1]
        questions = XY[j - 1]

        if sin == 0:
            continue

        if singi[j] == -1:
            singi[j] = sin
        else:
            if singi[j] != sin:
                flag = False

        for k in range(num):
            hito, honto = questions[k]
            if singi[hito] == -1:
                singi[hito] = honto
            else:
                if singi[hito] != honto:
                    flag = False

    if flag is True:
        singi = singi[1:]
        for b, s in zip(list(bin_), list(singi)):
            b = int(b)
            s = int(s)
            if (b == 1 and s == 0) or (b == 0 and s==1):
                flag = False
        if flag is True:
            ans = max(ans, singi.count(1))
print(ans)

Submission status: Accepted

Solution code:
def check_valid(flag):
    for i, m in mentions.items():
        if not (flag & (1 << i)):
            continue
        for j, honest in m.items():
            if honest and flag & (1 << j):
                continue
            if not honest and not (flag & (1 << j)):
                continue
            return False
    return True


n = int(input())
mentions = {}
for i in range(1, n + 1):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        if i not in mentions:
            mentions[i] = {x: y}
        else:
            mentions[i][x] = y
res = 0
for i in range(1, 1 << n + 1):
    if check_valid(i):
        temp = 0
        for j in range(1, n + 1):
            if i & (1 << j):
                temp += 1
            res = max(res, temp)
print(res)

Submission status: Accepted

Solution code:
N = int(input())
# N = 15なので全探索
say = []
for i in range(N):
    j = int(input())
    tmp = []
    for _ in range(j):
        tmp.append(list(map(int, input().split())))
    say.append(tmp)

# 15人に対し親切か不親切かをすべて場合分け　O(2**15=30000)
import itertools
all_man = []
for x in itertools.product([0, 1], repeat=N):
    all_man.append(x)
    
ans = []
for man in all_man:
    flag = False
    for i, man_i in enumerate(man):
        if man_i == 0:
            continue
        else:
            # この正直者の証言をとってくる
            for say_i in say[i]:
                x, y = say_i
                if man[x-1] != y:
                    # 矛盾
                    flag = True
    if flag:
        continue
    else:
        ans.append(man)
tmp = []
for i in ans:
    tmp.append(sum(i))
print(max(tmp))

Submission status: Accepted

Solution code:
N = int(input())
testi = {}
for i in range(N):
    T = []
    for a in range(int(input())):
        T.append(list(map(int, input().split())))
    testi[i+1] = T

ans = 0
for i in range(2**N):
    hypo = list(bin(i)[2:].zfill(N))
    num = hypo.count("1")
    for j, h in enumerate(hypo):
        if h == "1":
            for t in testi[j+1]:
                if hypo[t[0]-1] != str(t[1]):
                    break
            else:
                continue
            break
    else:
        if num > ans:
            ans = num

print(ans)

Submission status: Accepted

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

def be_honset(man, honests):
    for i in range(N):
        #正直者だけで考える
        if i+1 in honests:
            for j in range(A[i]):
                if says[i][j][1] == 0 and says[i][j][0] in honests:
                    return False 
                if says[i][j][1] == 1 and says[i][j][0] not in honests:
                    return False
                
    return True

for i in range(N):
    A[i] = int(input())
    say = []
    for j in range(A[i]):
        say.append([int(i) for i in input().split()])
    says[i] = say
    
max_num = 0

for i in range(1 << N):
    honests = []
    exist = True
    for j in range(N):
        if ((i>>j) & 1) == 1:
            honests.append(j+1)
    
    #　存在しないならFalse
    for h in honests:
        if not be_honset(h, honests): 
            exist = False
            break
        
    if not exist: continue
    num = len(honests)
    if num > max_num: max_num = num
    
print(max_num)

Submission status: Accepted

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

def res(n):
    t = []
    for i in range(15):
        if n%2 != 0:
            t.append(i)
        n = n // 2
    return t

def judge(t):
    r = [-1] * N
    while(len(t) > 0):
        c = t.pop(0)
        if r[c] == -1:
            r[c] = 1
        elif r[c] == 0:
            return False
        for x, y in l[c]:
            if r[x] > -1 and r[x] != y:
                return False
            elif r[x] == -1:
                r[x] = y
                if y == 1 and (x not in t):
                    t.append(x)
    return True

count = 0;
for num in range(2**N):
    o = res(num)
    if judge(o[:]):
        count = max(count, len(o))

print(count)

Submission status: Accepted

Solution code:
def tobin(num, pos):
    try:
        return int(format(num, 'b')[-(pos)])
    except:
        return 0

N = int(input())
shogens = {}
for person in range(1, N+1):
    Ai = int(input())
    inlist = []
    for i in range(Ai):
        x, y = map(int, input().split())
        inlist.append((x,y))
    shogens[person] = inlist

truth = [0]

for num in range(2**N):
    katei = []
    for pos in range(1, N+1):
        katei.append(tobin(num, pos))
    tf = True
    
    for person in range(1, N+1):
        if tf == False:
            break
        shogen = shogens[person]
        for tpl in shogen:
            if katei[person-1] == 1:
                if tpl[1] != katei[tpl[0]-1]:
                    tf = False
                    break
    if tf:
        truth.append(katei.count(1))
print(max(truth))