Problem:


Score : 300 points

Problem Statement

There are N people numbered 1 to N. Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.

Person i gives A_i testimonies. The j-th testimony by Person i is represented by two integers x_{ij} and y_{ij}. If y_{ij} = 1, the testimony says Person x_{ij} is honest; if y_{ij} = 0, it says Person x_{ij} is unkind.

How many honest persons can be among those N people at most?

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}

Output

Print the maximum possible number of honest persons among the N people.

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.

Sample Input 2

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

Sample Output 2

0

Assuming that one or more of them are honest immediately leads to a contradiction.

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



Sample input:
3
1
2 1
1
1 1
1
2 0


Sample output:
2

Submission status: Accepted

Solution code:
import itertools
n = int(input())
xy = [0 for _ in range(n)]
for i in range(n):
    ai = int(input())
    xy[i] = [list(map(int , input().split())) for _ in range(ai)]

#print(xy)
#print(xy[0])
#print(xy[0][0])
ans = 0
for i in itertools.product([0, 1], repeat=n):
    ok = True
    cnt = sum(i)
    for j in range(n):
        xyj = xy[j]
        if i[j] == 1:
            for xyk in xyj:
                if xyk[1] == 1:
                    if i[xyk[0]-1] == 0:
                        ok = False
                elif xyk[1] == 0:
                    if i[xyk[0]-1] == 1:
                        ok = False
    #print(ok, i)
    if ok:
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

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

res = 0
for i in range(1<<n):
    flg = True
    cnt = 0
    for j in range(n):
        if ( i >>j & 1 ) == 1:
            cnt += 1
    for j in range(n):
        if ( i >>j & 1 ) == 1:
            for x,y in prf[j]:
                if y == 0 and ( i >> x & 1 ) == 1:
                    flg = False
                if y == 1 and ( i >> x & 1 ) == 0:
                    flg = False
    if flg:
        res = max(res, cnt)
print(res)

Submission status: Accepted

Solution code:
N = int(input())

A = []

x = []
y = []

for i in range(N):
    temp = int(input())
    A.append(temp)
    temp3 = []
    temp4 = []
    for j in range(temp):
        temp1,temp2 = map(int,input().split())
        temp3.append(temp1)
        temp4.append(temp2)
    x.append(temp3)
    y.append(temp4)

res = 0

for i in range(2 ** N):
    isOK = True
    honest = 0
    for j in range(N):
        if ((i >> j) & 1):
            honest += 1
            for k in range(A[j]):
                if (((i >> (x[j][k]-1)) & 1) ^ y[j][k]):
                    isOK = False
    if isOK:
        res = max(res,honest)

print(res)

Submission status: Accepted

Solution code:
from itertools import combinations
import numpy as np
n = int(input())

testimonies = []

for i in range(n):
    A_i = int(input())
    testimonies.append([])
    for j in range(A_i):
        x_ij, y_ij = map(int, input().split())
        testimonies[i].append([x_ij-1, y_ij])

ans = 0
for i in range(n):
    i = n - i
    contradiction = True
    for honests in combinations(range(n), i):
        contradiction = False
        for testimony in [testimonies[i] for i in honests]:
            for x, y in testimony:
                if (y == 1 and x not in honests) or (y == 0 and x in honests):
                    contradiction = True
                    break
        if not contradiction:
            print(i)
            exit()

print(0)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [[] for _ in range(N)]
for i in range(N):
    a = ri()
    l = []
    for j in range(a):
        x, y = rl()
        l.append((x, y))
    A[i] = l

answer = 0

for i in range(2 ** N):
    honest = [False] * (N+1)
    bool = True
    for j in range(N):
        if ((i >> j) & 1):
            honest[N - j] = True
    for k in range(1, N+1):
        if honest[k] == True:
            #k番目の人は正直者
            for x, y in A[k-1]:
                if y == 1 and honest[x] == False:
                    bool = False
                    break
                if y == 0 and honest[x] == True:
                    bool = False
                    break
    if bool and sum(honest) > answer:
        answer = max(answer, sum(honest))

print(answer)

Submission status: Accepted

Solution code:
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))
ans=0
for i in range(1<<n):
    x="0"*15+bin(i)[2:]
    z=[int(i) for i in x[-n:]]
    f=1
    for p,q in enumerate(w):
        if z[p]==1:
            for r in q:
                if (z[r[0]-1]!=r[1]):
                    f=0
    if f:
        ans=max(ans,z.count(1))
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def countSetBits(n): 
    count = 0
    while (n): 
        count += n & 1
        n >>= 1
    return count 

def main():
    N = I()
    mat = [[-1 for __ in range(N)] for _ in range(N)]
    for i, _ in enumerate(range(N)):
        A = I()
        for __ in range(A):
            targ, b = LI()
            mat[i][targ - 1] = b
    ans = 0
    for bit in range(1 << N):
        err = False
        for j in range(N):
            honest_man = (bit & (1<<j))
            if honest_man:
                for k in range(N):
                    r = mat[j][k]
                    if r == -1:
                        continue
                    if r == 0:
                        if bit & (1<<k):
                            err = True
                    if r == 1:
                        if not bit & (1<<k):
                            err = True
        if not err:
            ans = max(ans, countSetBits(bit))
    print(ans)

    '''
    for bit in range(1 << N):
        truth = [-1 for _ in range(N)]
        err = False
        for i in range(N):
            honest_man = (bit & (1<<(N-1-i)))
            if honest_man:
                for j in range(len(mat[i])):
                    con = mat[i][j]
                    targ_ix = j
                    if con != -1:
                        if truth[targ_ix] != con:
                            if truth[targ_ix] != -1:
                                err = True 
                        if (bit & (1<<(N-1-targ_ix))) != con:
                            print('i: {0:{fill}3b}'.format(i, fill='0'))
                            print('bit: {0:{fill}3b}'.format(bit, fill='0'))
                            print("1<<(N-1-targ_ix): {0:{fill}3b}".format(bit & (1<<(N-1-targ_ix)), fill='0'))
                            print("con: ", con)
                            err = True
                        truth[targ_ix] = con
        if not err:
            ans = max(ans, countSetBits(bit))
    '''
main()

Submission status: Accepted

Solution code:
n=int(input())
comments=[]
for i in range(n):
    num=int(input())
    comment=[]
    for j in range(num):
        comment.append(list(map(int,input().split(" "))))
    comments.append(comment)

ans=0
for i in range(2**n):
    evidences={}
    people=list(str(format(i,'b').zfill(n)))
    conflict=False
    for idx,person in enumerate(people):
        if person=='1':
            for comment in comments[idx]:
                evidences.setdefault(comment[0],[]).append(comment[1])
    for key,value in evidences.items():
        personality = int(people[key-1])
        if value.count(personality) != len(value):
            conflict=True
            break
    if not conflict:
        ans=people.count('1')
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(list)
N = int(input())
s = []
for i in range(N):
    c = int(input())
    for _ in range(c):
        a,b = map(int, input().split())
        d[i].append((a-1,b))
ans = 0

# print(d)
for i in range(2**N):
    bins = format(i,"016b")[::-1]
    # 各bitに対して確認作業
    cnt = 0
    for i,b in enumerate(bins):
        if b == "1": #i番目の人が正直者のとき
            cnt += 1
            # 言った内容を聞く
            ls = d[i]
            flg = True
            for a,b in ls:
                # 言った内容と、事実が合っていない
                if int(b) != int(bins[a]):
                    flg = False
                    break
            if not flg:
                cnt = 0
                break
        
    ans = max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def countSetBits(n): 
    count = 0
    while (n): 
        count += n & 1
        n >>= 1
    return count 

def main():
    N = I()
    mat = [[-1 for __ in range(N)] for _ in range(N)]
    for i, _ in enumerate(range(N)):
        A = I()
        for __ in range(A):
            targ, b = LI()
            mat[i][targ - 1] = b
    ans = 0
    for bit in range(1 << N):
        err = False
        for j in range(N):
            honest_man = (bit & (1<<j))
            if honest_man:
                for k in range(N):
                    r = mat[j][k]
                    if r == -1:
                        continue
                    if (bit >> k) & 1 != r:
                        err = True
        if not err:
            ans = max(ans, countSetBits(bit))
    print(ans)

    '''
    for bit in range(1 << N):
        truth = [-1 for _ in range(N)]
        err = False
        for i in range(N):
            honest_man = (bit & (1<<(N-1-i)))
            if honest_man:
                for j in range(len(mat[i])):
                    con = mat[i][j]
                    targ_ix = j
                    if con != -1:
                        if truth[targ_ix] != con:
                            if truth[targ_ix] != -1:
                                err = True 
                        if (bit & (1<<(N-1-targ_ix))) != con:
                            print('i: {0:{fill}3b}'.format(i, fill='0'))
                            print('bit: {0:{fill}3b}'.format(bit, fill='0'))
                            print("1<<(N-1-targ_ix): {0:{fill}3b}".format(bit & (1<<(N-1-targ_ix)), fill='0'))
                            print("con: ", con)
                            err = True
                        truth[targ_ix] = con
        if not err:
            ans = max(ans, countSetBits(bit))
    '''
main()

Submission status: Accepted

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

A = 0
for i in range(2**n):
  flag = 0
  ans = 0
  num = list(format(i, '0{}b'.format(n)))
  for j, k in enumerate(num):
    if k == "1":
      ans += 1
      for l, m in zip(x[j], y[j]):
        if num[l-1] != "{}".format(m):
          flag = 1
          break
    if flag == 1:
      break
  if flag == 0:
  	A = max(A,ans)
print(A)

Submission status: Accepted

Solution code:
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))
ans=0
for i in range(1<<n):
    x="0"*15+bin(i)[2:]
    z=[int(i) for i in x[-n:]]
    f=1
    for p,q in enumerate(w):
        if z[p]==1:
            for r in q:
                if (z[r[0]-1]!=r[1]):
                    f=0
    if f:
        ans=max(ans,z.count(1))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
statements = [[] for i in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        statements[i].append(tuple(map(int, input().split())))

ans = 0
for bits in range(1 << N):
    for i in range(N):
        if not bits & (1 << i):
            continue
        ok = True
        for j, type in statements[i]:
            if bits & (1 << (j-1)) != (type << (j-1)):
                ok = False
                break
        if not ok:
            break
    else:
        ans = max(ans, bin(bits).count('1'))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
for _ in range(n):
    a=int(input())
    ll=[]
    for i in range(a):
        x,y=map(int,input().split())
        x-=1
        ll.append((x,y))
    l.append(ll)
ans=0
for k in range(2**n):
    f=1
    c=0
    for i in range(n):
        if ((k>>i)&1)==0:
            continue
        for x,y in l[i]:
            if ((k>>x)&1)!=y:
                f=0
                break
    if f:
        for i in range(n):
            c+=((k>>i)&1)

        ans=max(ans,c)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
xy = []
ans = 0
for i in range(N):
    A = int(input())
    l = []
    for j in range(A):
        x, y = map(int, input().split())
        l.append([x, y])
    xy.append(l)
# print(xy)

#bit全探索
#bitたつ→正直者
#bitたたない→不親切もの
for i in range(2 ** N):
    tmp = [0 for _ in range(N)]
    flag = True
    cnt = 0
    for j in range(N):
        if i >> j & 1:
            #正直者
            tmp[j] = 1
            cnt += 1
    for j in range(N):
        if tmp[j] == 1:
            A = xy[j]
            for k in A:
                _x = k[0] - 1
                _y = k[1]
                if tmp[_x] != _y:
                    flag = False
    if flag:
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

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

import itertools
import numpy as np

N = int(readline())
XY = [[] for _ in range(N)]
for i in range(N):
    A = int(readline())
    for _ in range(A):
        x,y = map(int,readline().split())
        XY[i].append((x-1,y))

A = np.array(list(itertools.product([0,1],repeat=N)),np.bool)
for i in range(N):
    for x,y in XY[i]:
        bl = (~A[:,i]) | (A[:,x] == bool(y))
        A = A[bl]

answer = A.sum(axis = 1).max()
print(answer)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = (int(i) for i in input().split())
            G[i].append((x-1, y))
            # 人iは人xのことをyと言っている

    ans = 0
    for bit in range(1 << N):
        cur = 0
        good = True  # 矛盾がない
        for i in range(N):
            if bit & (1 << i):
                # 人iは正直者
                cur += 1
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 1:
                        continue
                    elif not(bit & (1 << j)) and y == 0:
                        continue
                    elif (bit & (1 << j)) and y == 0:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
                        break
            else:
                # 人iはうそつき
                for j, y in G[i]:
                    if (bit & (1 << j)) and y == 0:
                        continue
                    elif not(bit & (1 << j)) and y == 1:
                        continue
                    elif (bit & (1 << j)) and y == 0:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
                        break
        # print(bit, ":", good)
        if good:
            ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def f():
    N = int(input())
    A = []
    
    for n in range(N):
        templist = []
        for a in range(int(input())):
            templist.append(list(map(int, input().split())))
        A.append(templist)
    
    # print(A)
    J = [0]
    maxlen = len(str(bin(2**len(A)-1).replace('0b','')))
    for j in reversed((range(2**len(A)))):
        tempb = str(bin(j).replace('0b',''))
        for i in range(maxlen - len(tempb)):
            tempb = '0'+tempb
        # ここでパターン仮置き確定
        tempj = list(map(int, list(tempb)))
        counter = 0
        for jj in range(len(tempj)):
            if tempj[jj] == 1: # 正直者の場合
                # 証言の数だけループを回す
                shocounter = 0
                for s in range(len(A[jj])):
                    if tempj[A[jj][s][0]-1] != A[jj][s][1]:# 本当は違う
                        break
                    else:
                        shocounter += 1
                if shocounter == len(A[jj]):
                    counter += 1
            else:
                # 証言の数だけループを回す
                shocounter = 0
                for s in range(len(A[jj])):
                    if tempj[A[jj][s][0]-1] == A[jj][s][1]:# 本当はあってる
                        continue
                    else:
                        shocounter += 1
                if shocounter > 0:
                    counter += 1
        if counter == len(A):
            J.append(tempj.count(1))
    
    list.sort(J, reverse=True)        
    return print(J[0])
    
f()

Submission status: Accepted

Solution code:
n = int(input())
lst = [(bin(i)[2:]).zfill(n) for i in range(2**n)]
ans = 0
A_list = []
xy_list = []
for i in range(n):
    a = int(input())
    A_list.append(a)
    for j in range(a):
        x,y = map(int,input().split())
        xy_list.append([x,y])
for i in range(len(lst)):
    choose = lst[i]
    one_count = choose.count("1")
    a_count = 0
    flag = True
    for num, j in enumerate(A_list):
        a_count += j
        for k in range(a_count-j, a_count):
            x,y = xy_list[k][0],xy_list[k][1]
            if choose[num] == "1" and choose[x-1] != str(y):
                flag = False
                break
    if flag:
        ans = max(ans,one_count)
print(ans)

Submission status: Accepted

Solution code:
n_person = int(input())
infomations_all = [[tuple(map(int, input().split())) for _2 in range(int(input()))] for _1 in range(n_person)]

opinions = [[-1] * n_person for _ in range(n_person)]
for person, infomations_of_each_person in enumerate(infomations_all):
    for infomation in infomations_of_each_person:
        target, isHonest = infomation
        opinions[person][target - 1] = isHonest

BreakOut = type("BreakOut", (Exception, ), {})
ans = 0
for tf_bits in range(2 ** n_person):
    hypothesis = list(map(int, format(tf_bits, "0%db" % n_person)))
    try:
        for person in range(n_person):
            if hypothesis[person]:
                for hyp, opi in zip(hypothesis, opinions[person]):
                    if not (opi == -1 or hyp == opi):
                        raise BreakOut
    except BreakOut:
        pass
    else:
        ans = max(ans, sum(hypothesis))

print(ans)

Submission status: Accepted

Solution code:
import bisect
from itertools import chain, combinations
from math import ceil, floor, sqrt

def powerset(iterable):
    s = list(iterable)
    # return chain.from_iterable(combinations(s, r) for r in range(len(s)+1, -1, -1))
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))

N = int(input())
lN = [n for n in range(N)]
lxy = [[] for _ in range(N)]
for i in range(N):
    ai = int(input())
    for _ in range(ai):
        xij, yij = list(map(int, input().split()))
        xij -= 1
        lxy[i].append((xij, yij))

# iter all of powersets inverse
ans = 0
for s in powerset(lN):
    # print(s) # assumed polite
    flag = True
    tmp = len(s)
    for elem in s:
        # print(lxy[elem])
        for xi, yi in lxy[elem]:
            if xi in s and yi == 0 or xi not in s and yi == 1:
                # if xi in s != (yi == 0):
                # print(elem, xi, yi)
                flag = False
    if flag:
        ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
remarks = []
for i in range(N):
    w = []
    for j in range(int(input())):
        w.append(list(map(int, input().split())))
    remarks.append(w)
     
def power2(n):
    if n == 1:
        return [[1], [0]]
    res = []
    for l in power2(n-1):
        res.append([1] + l)
        res.append([0] + l)
    return res
 
ans = 0
patterns = power2(N)

for p in patterns:
    flag = True
    for i, remark in enumerate(remarks):      
        if p[i] == 0: #不親切者の発言を無視
            continue
        else:
            for w in remark:
                if p[w[0]-1] != w[1]: #発言の矛盾を判定:
                    flag = False 
                    break
                # print(w)
    if flag: #すべての発言で矛盾がなかった場合
        ans = max(ans, p.count(1))
 
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy
from pprint import pprint

# If you use recursive call, uncomment this code
sys.setrecursionlimit(10**6)

def main():
    global result,aa,N
    N = int(input())
    aa = []
    for _ in range(N):
        aaa = []
        na = int(input())
        for _ in range(na):
            x,y = map(int,input().split())
            aaa.append((x-1,y))
        aa.append(aaa)

    ans = 0
    for bm in range(1<<N):
        inconsisted = False
        #print("---")
        #print("{:08b}".format(bm))
        for i in range(N):
            #print("\t",i)
            if not bm & 1<<i:
                continue
            for x,y in aa[i]:
                if (bm & 1<<x) ^ y<<x:
                    inconsisted = True
                    break
            if inconsisted:
                break
        if inconsisted:
            continue
        tmp = 0
        for i in range(N):
            tmp += bm>>i & 0b1
        ans = max(ans,tmp)
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
lst = [(bin(i)[2:]).zfill(n) for i in range(2**n)]
num_list = []
A_list = []
xy_list = []
for i in range(n):
    a = int(input())
    A_list.append(a)
    for j in range(a):
        x,y = map(int,input().split())
        xy_list.append([x,y])
for i in range(len(lst)):
    choose = lst[i]
    one_count = choose.count("1")
    a_count = 0
    flag = True
    for num, j in enumerate(A_list):
        a_count += j
        for k in range(a_count-j, a_count):
            x,y = xy_list[k][0],xy_list[k][1]
            if choose[num] == "1" and choose[x-1] != str(y):
                flag = False
                break
    if flag:
        num_list.append(one_count)
    else:
        num_list.append(0)
print(max(num_list))

Submission status: Accepted

Solution code:
from itertools import combinations

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

ans = 0
i = N
mens = list(range(1, N+1))
while i > 0:
  mujun = True
  for honests_id in combinations(mens, i):
    mujun = False
    for h in honests_id:
      for x, y in shogens[h-1]:
        if y == 1 and not x in honests_id or y == 0 and x in honests_id:
          mujun = True
          break
      if mujun:
        break
    if not mujun: 
      break
  if not mujun:
    break
  i -= 1
print(i)

Submission status: Accepted

Solution code:
n = int(input())
l = []
ans = 0
check = True
for _ in range(n):
    m = int(input())
    l.append([list(map(int, input().split())) for _ in range(m)])
for i in range(2 ** n):
    bin_i = format(i, 'b').rjust(n, "0")
    check = True
    for k in range(n):
        for x in range(len(l[k])):
            if bin_i[k] == "1":
                if (bin_i[l[k][x][0] - 1] == "1") and (l[k][x][1] == 0):
                    check = False
                elif (bin_i[l[k][x][0]-1] == "0") and (l[k][x][1] == 1):
                    check = False
    if check:
        ans = max(ans, bin_i.count("1"))
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

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

ans = 0
for i in range(2**N):
    assumption = [int(num) for num in bin(i)[2:].rjust(N, '0')]
    appropriate = True
    for j, p in enumerate(assumption):
        if p == 1:
            for s in statements[j]:
                if assumption[s[0] - 1] != s[1]:
                    appropriate = False
                    break
        else:
            continue

    if appropriate and ans < assumption.count(1):
        ans = assumption.count(1)

print(ans)

Submission status: Accepted

Solution code:
def Is_honest(x, honest, n):
    for i in range(n):
        honest[i] = (x%2 == 1)
        x //= 2


def checker(honest, da, n):
    for i in range(n):
        if honest[i]:
            size = len(da[i])
            for j in range(size):
                ok = (da[i][j][1] == 1)
                if honest[da[i][j][0]]^ok:
                    return False
    return True

def counter(honest):
    ret = 0
    for i in honest:
        if i:
            ret += 1
    return ret

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

ans = 0
honest = [False for i in range(n)]
m = 2 ** n

for i in range(m):
    Is_honest(i, honest, n)
    if checker(honest, da, n):
        ans = max(ans, counter(honest))

print(ans)

Submission status: Accepted

Solution code:
import itertools
N = int(input())

# shougen[i]: i番目の人の証言リスト
shougen=[]

for i in range(N):
  Ai = int(input())
  s = []
  for j in range(Ai):
    x, y = map(int, input().split())
    s.append((x-1, bool(y)))
  shougen.append(s)

#print(shougen)

ans=0

# 正直者、嘘つき者のすべての組み合わせを作成
combinations = itertools.product((True, False), repeat=N)
for is_honest in combinations:
  isOK = True # 矛盾があるかないかを表すフラグ
  # この組み合わせ(is_honest) において、
  # すべての人の発言に矛盾がないか調べる
  for i in range(N):
    if is_honest[i]:
      # i番目の人間が正直者の時,
      # i番目の人間の証言と組み合わせに矛盾があったら
      # 矛盾ありフラグを立てる
      for x, y in shougen[i]:
        if is_honest[x] != y:
          isOK = False
          break
  if isOK:
    # この組み合わせ(is_honest) において、
    # 矛盾が存在しない場合は、この組み合わせにおける正直者の人数を数えて
    # 最大値をとっていく
    ans = max(ans, sum(is_honest))

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=[]
for i in range(n):
    A.append([])
    for j in range(int(input())):
        A[i].append(list(map(int,input().split())))
for i in range(n,-1,-1):
    s=(1<<i)-1
    while s<1<<n:
        x=s&(-s)
        y=s+x
        flag=False
        for j in range(n):
            if s>>j & 1:
                for k in range(len(A[j])):
                    if (A[j][k][1]!=1 and (s>>(A[j][k][0]-1))&1==1) or (A[j][k][1]==1 and ((s>>(A[j][k][0]-1))&1)==0):
                        flag=True
                        break
            if flag:
                break
        if flag!=True:
            print(i)
            exit()
        s = ((s & ~y) // x) >> 1 | y

Submission status: Accepted

Solution code:
N = int(input())
Nloop = N + 1
A = [[0] * Nloop for _ in range(Nloop)]

for i in range(1, Nloop):
    Acount = int(input())
    for _ in range(Acount):
        x, y = map(int, input().split())
        if y == 1:
            A[i][x] = 1
        else:
            A[i][x] = -1

honest_loop = 2 ** N
is_honest = [False] * Nloop

ans = 0

for i in range(1, honest_loop):
    for l in range(1, Nloop):
        is_honest[l] = (i >> (l - 1) & 1 == 1)

    honest_check = True
    for l in range(1, Nloop):
        # lの人が正直者のとき
        if is_honest[l]:
            # lの人から見てjの人は正直者か？
            for j in range(1, Nloop):
                if A[l][j] == 1:
                    if not is_honest[j]:
                        honest_check = False
                elif A[l][j] == -1:
                    if is_honest[j]:
                        honest_check = False
                if not honest_check:
                    break
        if not honest_check:
            break

    if honest_check:
        ans = max(sum(is_honest), ans)

print(ans)

Submission status: Accepted

Solution code:

N = int(input())


es = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for n in range(A):
        x,y = map(int, input().split())
        es[i].append((x-1,str(y)))


# それぞれの人が正直かどうかについて全探索する
ans = 0
for i in range(2**N):
    bnum = (bin(i)[2:]).zfill(N)

    f = True
    for j in range(N):
        # j番目のひとが正直なら
        if bnum[j] == "1":
            # 人jの証言について調べる
            for x,y in es[j]:
                # 証言内容と仮定した正直かどうか(bnumのこと)に矛盾があるなら飛ばす
                #print(j,x,y,bnum[x])
                if bnum[x] != y:
                    f = False
    #print(bnum, f)
    if f:
        ans = max(ans, bnum.count("1"))
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
matrix = [[0 for i in range(N)] for j in range(N)]
for n in range(N):
    A = int(input())
    for a in range(A):
        array = [int(i) for i in input().split()]
        matrix[n][array[0]-1] = 1 if array[1] == 1 else -1
l = [True,False]
from itertools import product
for pattern in product(l,repeat=N):
    able = True
    for i,p in enumerate(pattern):
        if p:
            for a,b in zip(matrix[i],pattern):
                if (b==True and a==-1) or (b==False and a == 1):
                    able = False
                    break
            if able == False:
                break
        else:
            pass
    if able == True:
        break
print(sum(pattern))