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 collections import deque
N = int(input())
table = [[] for i in range(N)]
for i in range(N):
  A = int(input())
  for j in range(A):
    x,y = map(int, input().split())
    table[i].append((x,y))
ans = 0
for i in range(2**N):
    memo = [-1]*N
    flag = 0
    tmp = 0
    H = deque()
    for j in range(N):
        if (i>>j)&1:
            tmp += 1
            if memo[j] == -1:
                memo[j] = 1
            else:
                if memo[j] != 1:
                    tmp = 0
                    flag = 1
                    break

            for x,y in table[j]:
                x -= 1
                if memo[x] == -1:
                    memo[x] = y
                else:
                    if memo[x] != y:
                        tmp = 0
                        flag = 1
                        break
            if flag == 1:
                break
        else:
            if memo[j] == -1:
                memo[j] = 0
            else:
                if memo[j] != 0:
                    tmp = 0
                    flag = 1
                    break
    ans = max(tmp,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())

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



ans = 0
for i in range(2**(N)):
    if len(str(bin(i))[2:]) < N:
        K = ["0"] * (N-len(str(bin(i))[2:])) + list(str(bin(i))[2:])
    else:
        K = list(str(bin(i))[2:])
    for j in range(N):
        
        flag = 1
        if K[j] == "0":
            pass
        else:
            for l in range(N):

                if L[j][l] == -1:
                    continue
                elif L[j][l] == 0:
                    if K[l] == "1":
                        flag = 0
                        break
                elif L[j][l] == 1:
                    if K[l] == "0":
                        flag = 0
                        break
        if flag == 0:
            break
        if j == N-1:
            ans = max(ans, K.count("1"))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * n
d = {}
ans = 0
for i in range(n):
    d[i] = []
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        d[i].append([int(_) for _ in input().split()])
for i in range(0, 2**n):
    fool = 'yes'
    bin_str = format(i, '0' + str(n) + 'b')
    # print(bin_str)
    res = {}
    for j in range(n):
        res[j] = bin_str[j]
    # print(res)
    for k in range(n):
        if res[k] == '1':
            for l in d[k]:
                x = l[0] - 1
                y = l[1]
                # print(x, y)
                if res[x] != str(y):
                    fool = 'no'
    # print(fool)
    if fool == 'yes':
        tem = 0
        for i in range(n):
            if res[i] == '1':
                tem += 1
        ans = max(ans, tem)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
flag=0
E=[]
total=0
maxi=0
for i in range(N):
    E.append([0]*N)
for i in range(N):
    M=int(input())
    for j in range(M):
        C, D = map(int, input().split())
        if D==1:
            D=2
        else:
            D=1
        E[i][C-1]+=D

#print(E)

A=[]
for i in range((2**N)):
    s=format(i,'b')
    A.append(s.zfill(N))
#print(A)

for i in range(len(A)):
    flag=0
    total=0
    S=A[i]
    #print(S)
    for j in range(len(S)):
        if S[j]=='0':
            for k in range(N):
                #print(E[j][k],S[k])
                if (E[j][k]==1 and S[k]=='0')or (E[j][k] == 2 and S[k] == '1'):
                    #print('f')
                    flag=1
    if flag==0:
        for o in range(len(S)):
            if S[o]=='0':
                total+=1
        maxi=max(maxi,total)
print(maxi)

Submission status: Accepted

Solution code:
n=int(input())
l=[[] for i in range(n)]
for i in range(n):
  a=int(input())
  for j in range(a):
    x,y=map(int,input().split())
    l[i].append([x-1,y])
ans=0
for i in range(2**n):
  z=str(format(i,('0'+str(n)+'b')))
  f=1
  for k in range(n):
    if f:
      if int(z[k]):
        for m in l[k]:
          if z[m[0]]!=str(m[1]):
            f=0
  if f:            
    ans=max(ans,z.count('1'))    
print(ans)

Submission status: Accepted

Solution code:
def is_contradict(T, H):
    for t in T:
        a = t[0]
        x = t[1]
        y = t[2]
        if int(H[a-1]) == 1 and int(H[x-1]) != y:
            return True
    return False

def main():
    N=int(input())
    T=[]
    for n in range(N):
        A=int(input())
        for a in range(A):
            x,y = map(int, input().split())
            T.append((n+1,x,y))
    
    ans = 0
    for i in range(2**N):
        s = format(i, "015b")
        s = s[15 - N:]
        if not is_contradict(T, s):
            c = s.count("1")
            if ans < c:
                ans = c
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

comb = itertools.product([0, 1], repeat=n)
ans = 0
for c in comb:
    list_c = list(c)
    flag = True
    for i in range(len(xy)):
        if list_c[i] == 1:
            for j in range(len(xy[i])):
                if xy[i][j][1] == 1:
                    if list_c[xy[i][j][0]-1] != 1:
                        flag = False
                        break
                else:
                    if list_c[xy[i][j][0]-1] != 0:
                        flag = False
                        break
    if flag:
        ans = max(ans, list_c.count(1))
print(ans)

Submission status: Accepted

Solution code:
def examC():
    N = I()
    A = [0]*N; xy = [[] for _ in range(N)]
    for i in range(N):
        A[i] = I()
        for j in range(A[i]):
            s1,s2 = LI()
            xy[i].append([s1,s2])
#    print(xy)
    loop = 2**N; differ = 2**4
    ans = 0
    for i in range(loop):
        uso = [False]*N
        honto = [False]*N
        cur = 0
        for j in range(N+1):
            if i&(2**j)==(2**j):
                cur +=1
#        print(i,cur)
        for j in range(N):
            if i&(2**j)==(2**j):
                for k in xy[j]:
                    if k[1]==0:
                        uso[k[0]-1] = True
                    elif k[1]==1:
                        honto[k[0]-1] = True
#チェック
        for j in range(N):
            if uso[j] and i&(2**j)==(2**j):
                cur = 0
                break
            if honto[j] and i&(2**j)==0:
                cur = 0
                break
        ans = max(ans,cur)
    print(ans)

    return

def examD(mod):
    N = I(); A = LI()
    d = defaultdict(int)
    for i in range(N):
        cur = A[i]
        j = 1
        while(cur>0):
            if cur&1==1:
                d[j] +=1
            j +=1
            cur >>=1
    ans = 0
    for i,j in d.items():
        ans += j*(N-j) * 2**(i-1)
        ans %=mod
    print(ans)
    return

def examE():
    return

def examF():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Submission status: Accepted

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

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

maxCnt = 0
for i in range(2 ** n):
    bin_str = format(i, 'b').zfill(n)
    trueFlg = 1
    for j in range(n):
        for k in B[j]:
            if bin_str[j] == '1':
                if int(bin_str[k[0] -1]) != k[1]:
                    trueFlg = 0
                    break
#            if bin_str[j] == '0':
#                if int(bin_str[k[0] - 1]) == k[1]:
#                    trueFlg = 0
#                    break
    if trueFlg == 1:
        maxCnt = max(maxCnt, bin_str.count('1'))

print(maxCnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
tests  = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    tests[i].extend([tuple(map(int, input().split())) for _ in range(a)])

rst = 0
chk = 2 ** n
for h in list(range(chk))[::-1]:
    h_list = ("{:0>"+str(n)+"}").format(bin(h)[2::])
    flag = True
    for i, a in enumerate(h_list):
        if a == '0':
            continue

        for x, y in tests[i]:
            ys = str(y)
            if h_list[x-1] == ys:
                continue
            else:
                flag = False
                break
        
        if not flag:
            break
    
    if flag:
        rst = h_list.count('1')
        break

print(rst)

Submission status: Accepted

Solution code:
from queue import Queue

n = int(input())
shogens = []

for people_index in range(n):
    this_shogens = []
    shogen_num = int(input())
    for _ in range(shogen_num):
        this_shogens.append(tuple(map(int, input().split())))

    shogens.append(this_shogens)

def make_pattern(number):
    pattern = [0 for _ in range(n)]
    index = 0
    while True:
        if number == 0:
            break
        else:
            pattern[index] = number % 2
            number //= 2
            index += 1
    return pattern


def ok(pattern):
    hantei = [None for _ in range(n)]
    seen_list = []
    q = Queue()
    ret = True
    for people_index in range(len(pattern)):
        if pattern[people_index] == 1:
            q.put(people_index)
            hantei[people_index] = 1

    while True:
        if q.empty():
            break
        else:
            people_index = q.get()
            if people_index in seen_list:
                continue
            else:
                seen_list.append(people_index)

            this_shogens = shogens[people_index]

            for this_shogen in this_shogens:
                people_sareta_index = this_shogen[0]-1
                shogen = this_shogen[1]

                if shogen == 1 and (people_sareta_index not in seen_list):
                    q.put(people_sareta_index)

                if hantei[people_sareta_index] == None:
                    hantei[people_sareta_index] = shogen

                if shogen != hantei[people_sareta_index]:
                    ret = False
                    break

    return ret

def main():
    max_num = 0
    num_list = []
    for value in range(pow(2, n)-1, -1, -1):
        pattern = make_pattern(value)

        shojiki_count = 0
        for p in pattern:
            if p == 1:
                shojiki_count += 1

        if not shojiki_count in num_list:
            if ok(pattern):
                max_num = max(max_num, shojiki_count)
                num_list.append(shojiki_count)

    print(max_num)
main()

Submission status: Accepted

Solution code:
n = int(input())
shougen = [[] for i in range(n)]
max_num = 0

def check(li):
    co = 0
    for i in li:
        if i == '1':
            co += 1
    return co

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


for i in range(2**n):
    flag = True
    people = str(format(i, 'b').zfill(n))
    if flag == True:
        for j in range(n):
            if people[j] == '1':
                if flag is True:
                    for k in range(len(shougen[j])):
                        to_people = shougen[j][k][0] - 1
                        if str(shougen[j][k][1]) != people[to_people]:
                            flag = False
                            break
                else:
                    break
    else:
        break
    if flag is True:
        num = check(people)
    if num > max_num:
        max_num = num

print(max_num)

Submission status: Accepted

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

n = int(input())
bit = []
for i in range(2 ** n):
    bit.append(format(i, '0{}b'.format(n)))
bit = sorted(bit, key=lambda a: -collections.Counter(a)['1'])

say = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        say[i].append([int(i) for i in input().split()])

answer = 0
for b in bit:
    failed = False
    for i, v in enumerate(b):
        if failed:
            break
        if v == '1':
            for s in say[i]:
                if int(b[s[0] - 1]) != s[1]:
                    failed = True
                    break
    if not failed:
        answer = b
        break

print(collections.Counter(b)['1'])

Submission status: Accepted

Solution code:
#coding:utf-8
import copy
from collections import deque
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True

def index(a,b):
    return str(min(a,b)) + "," +  str(max(a, b))

def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    n = II()
    xy = []
    for i in range(n):
        a = II()
        xy.append(XLMIIS(a))


    def f(a):
        i = 0
        while n != i  and a[i] != -1:
            i += 1
        if i == n:
            return 0

        b = copy.copy(a)
        b[i] = 1
        b_ans = 1
        mujun = 0
        q = deque([i])
        while len(q) != 0:
            qq = q.pop()
            for j in xy[qq]:
                if b[j[0]-1] == -1 and j[1] == 1:
                    q.append(j[0]-1)
                    b[j[0]-1] = 1
                    b_ans += 1
                elif b[j[0]-1] == -1 and j[1] == 0:
                    b[j[0]-1] = 0
                elif b[j[0]-1] != j[1]:
                    mujun = 1
                    break
        if mujun == 0:
            b_ans += f(b)
        else:
            b_ans = 0

        c = copy.copy(a)
        c[i] = 0
        c_ans = f(c)

        return max(b_ans, c_ans)


    print(f([-1]*n))







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = []
a = []
for i in range(n):
    aa = int(input())
    a.append(aa)
    c = []
    for j in range(aa):
        xy = list(map(int,input().split()))
        c.append(xy)
    s.append(c)
#print(s[0])
sy = []
ans = 0
 
def syojiki(sy,count):
    if count == n:
     #   print(sy)
        check = [[] for i in range(n)]
        for i in range(n):
            if sy[i] == 1:
                check[i].append(1)
        for i in range(n):
            if sy[i] == 1:
                for j in range(a[i]):
                    if s[i][j][1] not in check[s[i][j][0]-1]:
                        check[s[i][j][0]-1].append(s[i][j][1])
    #    print(check)
        check2 = 0
        for i in range(n):
            if len(check[i]) == 0:
                check2 += 1
            elif len(check[i]) == 1 and check[i][0] == sy[i]:
                check2 += 1
   #     print(check2)
        if check2 == n:
            global ans
            ans = max(ans,check.count([1]))
   #         print(ans)
    else:
        syojiki(sy+[0],count+1)
        syojiki(sy+[1],count+1)
 
syojiki(sy,0)
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
import sys

N = int(input())
A = [[] for _ in range(N + 1)]
B = [[] for _ in range(N + 1)]
C = [[] for _ in range(N + 1)]
num_hint = []
# hint_dict = {}
for i in range(1, N + 1):
    num_i = int(input())
    num_hint.append(num_i)
    for j in range(num_i):
        x, y = map(int, input().split())
        A[i].append((x, y))
        if y == 1:
            B[i].append(x)
        if y == 0:
            C[i].append(x)
        # if hint_dict.get(x) is None:
        #     hint_dict[x] = {0: [], 1: []}
        #     hint_dict[x][y].append(i)
        # else:
        #     hint_dict[x][y].append(i)

for i in range(N + 1, 0, -1):
    for combi in combinations(range(1, N + 1), i):
        remain = set(range(1, N + 1)) - set(combi)
        s = set()
        t = set()
        hint_dict = {}
        for j in combi:
            s |= set(B[j])
            t |= set(C[j])
            for x, y in A[j]:
                if hint_dict.get(x) is None:
                    hint_dict[x] = {0: [], 1: []}
                    hint_dict[x][y].append(i)
                else:
                    hint_dict[x][y].append(i)
        good1 = True
        for value in hint_dict.values():
            if len(value[0]) != 0 and len(value[1]) != 0:
                good1 = False
                break
        good2 = True
        if len(s & remain) != 0:
            good2 = False
        good3 = True
        if len(t & set(combi)) != 0:
            good3 = False
        if good1 and good2 and good3:
            print(i)
            sys.exit()
print(0)

Submission status: Accepted

Solution code:
N = int(input())
A = list()
x = list()
y = list()

for i in range(N):
    A_tmp = int(input())
    A.append(A_tmp)
    x_tmp = list()
    y_tmp = list()
    for k in range(A_tmp):
        tmp = [int(j) for j in input().split()]
        x_tmp.append(tmp[0])
        y_tmp.append(tmp[1])
    x.append(x_tmp)
    y.append(y_tmp)

def DFS(acc_list, depth):
    if depth < N:
        acc_list[depth] = 0
        result1 = DFS(acc_list, depth+1)
        acc_list[depth] = 1
        result2 = DFS(acc_list, depth+1)
        return max(result1, result2)

    acc_dict = dict()
    for i in range(N):
        acc_dict[i] = None

    for i in range(N):
        if acc_list[i] == 1:
            for j in range(A[i]):
                if acc_dict[x[i][j]-1] == None:
                    acc_dict[x[i][j]-1] = y[i][j]
                else: 
                    if acc_dict[x[i][j]-1] == y[i][j]:
                        pass
                    else: 
                        return 0

    flag = 1
    for i in range(N):
        if acc_dict[i] == acc_list[i]:
            pass
        else:
            if acc_dict[i] == None:
                pass
            else:
                flag = 0
    if flag == 1:
        return sum(acc_list)
    else:
        return 0

acc_list = [0]*N

result = DFS(acc_list, 0)
print(result)

Submission status: Accepted

Solution code:
N = int(input())
li = list()
for i in range(N):
    Ai = int(input())
    Alist = list()
    for j in range(Ai):
        x,y = map(int,input().split())
        Alist.append([x-1,y])
    li.append(Alist)
num =(2**(N))
while True:
    ok = True
    num -=1
    numlist = format(num, 'b')
    #print(list(numlist))
    zero = str()
    if N != len(numlist):
        for i in range(N-len(numlist)):
            zero += "0"

        numlist = zero + numlist
    #print(numlist)
    for i in range(len(numlist)):
        if numlist[i] == "1":
            for j in range(len(li[i])):
                if int(numlist[li[i][j][0]]) != li[i][j][1]:
                    ok = False
                    break
        if ok == False:
            break
    if ok == True:
        print(numlist.count("1"))
        break
    if num == 0:
        print(0)
        break

Submission status: Accepted

Solution code:
import itertools
n=int(input())
tl=[[-1]*n for _ in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        tl[i][x-1]=y
ans=0
ll=list(itertools.product(range(2),repeat=n))
for l in ll:
    for i in range(n):
        if l[i]==0:
            continue
        for j in range(n):
            if tl[i][j]<0:
                continue
            if tl[i][j]!=l[j]:
                break
        else:
            continue
        break
    else:
        ans=max(ans,sum(l))
print(ans)

Submission status: Accepted

Solution code:
import itertools

s = raw_input()
N = int(s)

A = [[-1 for i in range(N)] for j in range(N)]
#print A

for i in range(N):
    n = int(raw_input())
    for j in range(n):
        [x,y] = raw_input().split()
        x = int(x)
        y = int(y)
        #print "x=",x, "y=",y
        A[i][x-1] = y

#print A

List = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
lst = List[0:N]
#print lst

def consistency_check(lst):
    #print "lst=",lst
    for i in range(N):
        if i in lst:
            continue
        for j in range(N):
            if A[i][j] == 0 and not(j in lst):
                return 0
            if A[i][j] == 1 and j in lst:
                return 0
    return 1

for i in range(N+1):
    lierlist = list(itertools.combinations(lst,i))
    for j in range(len(lierlist)):
        if consistency_check(lierlist[j]):
            print N-i
            exit (0)

#print "wrong"
print 0 # not reach

Submission status: Accepted

Solution code:
N = int(input())
L = []
candidates = [list(bin(i)[2:].zfill(N)) for i in range(2**N)]

for i in range(N):
    A = int(input())
    said = [list(map(int,input().split())) for i in range(A)]
    L.append(said)

ans = 0
for pattern in candidates:
    tmp = 0
    flag = 1
    for j in range(N): #pattern内全て
        if pattern[j] == "1":
            for said in L[j]:
                if pattern[said[0] - 1] != str(said[1]):
                    flag = 0
        else:
            pass
    if flag == 1:
        ans = max(ans, pattern.count("1"))

print(ans)

Submission status: Accepted

Solution code:
import copy

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

def rec(condition, i):
  if i==N:
    return condition.count(1)
  _X = X[i]
  _condition = copy.copy(condition)
  through_condition = copy.copy(condition)
  through_condition[i] = 0
  if condition[i]==0:
    return rec(copy.copy(through_condition), i+1)
  for x in _X:
    if _condition[ x[0]-1 ] == -1:
      _condition[ x[0]-1 ] = x[1]
    elif _condition[ x[0]-1 ] != x[1]:
      return 0 if _condition[i]==1 else rec(copy.copy(through_condition), i+1)
  _condition[i] = 1
  return max(rec(copy.copy(through_condition), i+1), rec(copy.copy(_condition), i+1))

print( rec([-1 for _ in range(N)], 0) )

Submission status: Accepted

Solution code:
def popcnt(n):
    return bin(n).count("1")

n = int(input())
grid = []

for i in range(n):
    p = int(input())
    for j in range(p):
        array = [i] +list(map(int, input().strip().split(' ')))
        array[1] = array[1] - 1
        grid.append(array)


truth = 0
count = 0

for i in range(2**n):
    k = (bin(i)[2:]).zfill(n)
    count = 0
    for j in range(len(grid)):
        if int(k[grid[j][0]]) == 1:
            if (int(k[grid[j][1]]) == 1 and grid[j][2] == 0) or (int(k[grid[j][1]]) == 0 and grid[j][2] == 1):
                count = 1
                break
    if count == 0:
        if truth < popcnt(i):
            truth = popcnt(i)

print(truth)

Submission status: Accepted

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

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

ans = 0

#まずはbitの列挙、一つずつ探索する
for bit in range(1<<n):
    check = str(bin(bit)).count('1')
    for i in range(n):
        #各bitが1の場合は正直者とする、0の場合は関係なし
        if (bit>>i)&1 == 1 :
            #X_Y[i]の中身が正直者には1, 不明者には0が向いているかを確認
            count = 0
            for obj in X_Y[i]:
                #対象が嘘つきの場合
                if (obj[1] == 0) and (bit>>obj[0]&1 == 0):
                    count += 1
                #対象が正直者の場合
                elif (obj[1] == 1) and (bit>>obj[0]&1 == 1):
                    count += 1
                else:
                    pass

            #正直者の発言が正しい場合
            if count == A[i]:
                check -= 1
            # #正しくない場合は次のbitへ向かう
            # else:
            #     break
    #全員の成否を確かめた後に、正直者の発言がすべて正しいか判定
    if check == 0:
        can = str(bin(bit)).count('1')
        #正直者の発言が正しい場合はansを比較
        if ans <= can:
            ans = can
print(ans)

Submission status: Accepted

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

# 正直者=1, 嘘つき=0 とする
ans = []
for i in range(1<<n):
    s = ''.join(str(bin(i)).replace('0b', '')).zfill(n)
    for j in range(n):
        if s[j] == '1':
            for word in xy[j]:
                if int(s[word[0]-1]) != word[1]:
                    break
            else:
                continue
            break
    else:
        ans.append(s)
        continue

cnt = 0
for x in ans:
    k = x.count('1')
    if cnt < k:
        cnt = k
print(cnt)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
N = int(stdin.readline().rstrip())
An = []
xy = {}
count = 0
for el1 in range(N):
    ai = int(stdin.readline().rstrip())
    An.append(ai)
    Tmp = []
    for el2 in range(ai):
        tmp = [int(s) for s in stdin.readline().rstrip().split()]
        Tmp.append(tmp)
    xy[count] = Tmp
    count += 1
Checker = []
for el in range(2 ** N):
    bin(el)
    checker = list(str(bin(el)))
    del checker[0:2]
    checker = [int(s) for s in checker]
    for n in range(N - len(checker)):
        checker.insert(0, 0)
    Checker.append(checker)

res = 0
for el1 in Checker:
    pos = 0
    tes0 = []  # 0のやつを追加
    tes1 = []  # 1のやつを追加
    for el2 in el1:
        if el2 == 0:
            pos += 1
            continue
        else:
            tes1.append(pos)
            n = xy[pos]
            for el3 in n:
                if el3[1] == 1:
                    tes1.append(el3[0]-1)
                if el3[1] == 0:
                    tes0.append(el3[0]-1)
            pos += 1
    check = True
    for el2 in tes1:
        if (el1[el2] != 1):
            check = False

    if (len(set(tes0) & set(tes1)) == 0 and check):
        if (el1.count(1) >= res):
            res = el1.count(1)
print(res)

Submission status: Accepted

Solution code:
N = int(input())
tes_l = [[-1 for i in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(int(input())):
        target,TFflg = list(map(int,input().split()))
        tes_l[i][target-1] = TFflg 


ans = 0
flg = False
for k in range(2**N):
    tmpans = list(map(int,bin(k)[2:].zfill(N)))
    for i,eachtes in enumerate(tes_l):
        for j,tes in enumerate(eachtes):
            if(tmpans[i]==1):
                if(tes!=-1 and tmpans[j]!=tes):
                    flg = True
            """
            if(tes==0 and tmpans[i]==1):
                if(tmpans[j]==1):
                    continue
            elif(tes==1 and tmpans[i]==1):
                if(tmpans[j]==0):
                    continue
            """
    if(not flg):
        ans = max([sum(tmpans),ans])
    flg = False

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

N = int(input())

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

    witnesses.append(witness)

honest_binary = 2 ** N - 1
while (honest_binary > 0):
    honest_list = [int(i) for i in list(format(honest_binary, '0' + str(N) + 'b'))]

    # 証言を見ていって、honest_listと相違ないか調査
    # 見るのはhonest_listで正直認定している人だけ
    flag = False
    for i in range(len(honest_list)):
        if honest_list[i] == 0:
            continue

        witness = witnesses[i]
        for w in witness:
            (x, y) = w
            if honest_list[x] != y:
                flag = True
                break
        if flag is True:
            break
    else:
        print(honest_list.count(1))
        sys.exit()

    honest_binary -= 1

print(0)

Submission status: Accepted

Solution code:
import itertools

N = int(input())

syougen_list = []
people = [-1] * N
for i in range(N):
    a_i = int(input())
    a_i_list = []
    for j in range(a_i):
        a_i_list.append(list(map(int, input().split())))
    syougen_list.append(a_i_list)


output = 0
for i in itertools.product([1,0], repeat=N):
    legal = True
    for index, j in enumerate(i):
        if j == 1:
            syougen = syougen_list[index]
            for k in syougen:
                if i[k[0] - 1] != k[1]:
                    legal = False
                    break
    if not legal:
        continue

    match = True
    honest_syougen_list = []
    for index, j in enumerate(i):
        if j == 1:
            honest_syougen_list += syougen_list[index]
    for j in honest_syougen_list:
        if people[j[0] - 1] == -1:
            people[j[0] - 1] = j[1]
        elif people[j[0] - 1] != j[1]:
            match = False
            break
    if match:
        number = i.count(1)
        if number >= output:
            output = number

print(output)

Submission status: Accepted

Solution code:
n=int(input())

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

max_=0
one_hot=[[] for _ in range(n)]
for i in range(2**n):
  temp=i
  count=0
  for j in range(n):
    one_hot[j]=temp%2
    temp//=2
    if one_hot[j]==1:
      count+=1
  flg=True
  for j in range(n):
    for k in range(len(s[j])):
      if one_hot[j]==1:
        if one_hot[s[j][k][0]-1]!=s[j][k][1]:
          flg=False
          break
      if not flg:
        break
  if flg and max_<count:
    max_=count
  count=0
print(max_)