Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

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

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

0

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

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



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


Sample output:
2

Submission status: Accepted

Solution code:
N = int(input())
XYList = []
for i in range(N):
    A = int(input())
    XY = []
    for j in range(A):
        XY.append(list(map(int, input().split())))
    XYList.append(XY)
maxSum = 0
for i in range(2**N):
    sum = 0
    for j in range(N):
        if i >> j & 1:
            honest = True
            for XY in XYList[j]:
                if ((i >> (XY[0]-1)) & 1) != XY[1]:
                    honest = False
                    break
            if honest:
                sum += 1
            else:
                sum = 0
                break
    if maxSum < sum:
        maxSum = sum
print(maxSum)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()

    statements = []
    for _ in range(N):
        a = II()
        statement = []
        for _ in range(a):
            hatugen = LI()
            statement.append(hatugen)
        statements.append(statement)

    ans = 0
    for i in range(2**N):
        flag = True
        i_str = format(i, f"0{N}b")
        for n in range(N):
            if i_str[n] == '0':
                continue

            for statement in statements[n]:
                target = statement[0]
                seisitu = statement[1]

                if i_str[target - 1] != str(seisitu):
                    flag = False

        if flag:
            tmp = 0
            for n in range(N):
                tmp += int(i_str[n])

            ans = max(ans, tmp)

    print(ans)


main()

Submission status: Accepted

Solution code:
n = int(input())
ls = [0]*n
param_list = [0]*2**n
for i in range(2**n):
    l = [False]*n
    for id_r, row in enumerate(ls):
        if i & (2 ** id_r) >0:
            l[id_r] = True
    param_list[i] = l 


for i in range(n):
    A = int(input())
    for k in range(A):
        a,b = map(int, input().split())
        b = (1==b)
        new_param =[]
        for d in param_list:
            if d[i]:
                if d[a-1] == b:
                    new_param.append(d)
                    pass
                else:
                    #print(2)
                    pass
            else:
                new_param.append(d)
                #if d[a-1] is b:
                    #print(3)
                    #pass
                #else:
                    #print(4)
                    #new_param.append(d)
                    #pass
            
        param_list = new_param
        #print(param_list)
            
ans = 0    
for d in param_list:
    ans = max(ans, d.count(True))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

bit_lst = list(product(range(2), repeat=N)) #N桁のビット

ans = 0
for bit in bit_lst:
    f = True #このbitの証言が無意味になったらFalse
    for a in range(N):
        #1人ずつ順番に聞く : a人目の証言
        if f:
            for b in range(A[a]):
                #b個目の証言
                if bit[a] == 1:
                    #この人が正直者なとき
                    if lst[a][b][1] != bit[lst[a][b][0]-1]:
                        #正直者の証言と現実が食い違う
                        f = False
                        break
                else:
                    #正直者ではないとき
                    break
    if f:
        ans = max(ans, sum(bit))
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    comment = []

    for i in range(1, N + 1):
        A = int(input())
        for j in range(1, A + 1):
            c = [i]
            c.extend(list(map(int, input().split())))
            comment.append(c)

    ans = 0
    for i in range(1, 2**N):
        flg = True
        for h, t, c in comment:
            #発言者が正直者か
            if i & (1 << h - 1):
                #発言が適切か
                if ((i >> t - 1) & 0b1) ^ c:
                    flg = False
                    break
        
        if flg:
            tmp = 0
            for j in range(N):
                if i & (1 << j):
                    tmp += 1
            
            ans = max(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())

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

#print(statements)
ans=0

for honest in range(1<<N):
  flag=True
  for j in range(N):
    statement=statements[j]
    for x,y in statement:
      if (honest&(1<<j))>>j ==1:
        flag*=((honest&(1<<x))>>x ==y)


    #print(flag)
  if flag==True:
    honests.append(honest)

n_honests=[]
for honest in honests:
  n_honest=0
  for i in range(N):
    n_honest+=(honest&(1<<i))>>i
  n_honests.append(n_honest)

print(max(n_honests))

Submission status: Accepted

Solution code:
n = int(input())
ls = [[] for _ in range(n)]
di = []
for p in range(n):
    a = int(input())
    ls[p] = [list(map(int,input().split())) for _ in range(a)]
for i in range(2**n):
    new = []
    for j in range(n):
        if (i>>j)&1:
            new.append(j)
    di.append(new)
flag = True
mx = 0
for l in di:
    flag = True
    for k in l:
        for s in ls[k]:
            a,b = s[0],s[1]
            if ((a-1 not in l)and (b == 1)) or ((a-1 in l) and (b == 0)):
                flag = False
                break
        if flag == False:
            break
    if flag == True:
        if len(l) > mx:
            mx = len(l)     
print(mx)

Submission status: Accepted

Solution code:
n = int(input())
all = 1<<n
statement = []
for i in range(n):
    A = int(input())
    statement.append([])
    for j in range(A):
        x, y = map(int, input().split())
        statement[i].append([x-1, y])
ans = 0
for i in range(all):
    ok = True
    num = 0
    for j in range(n):
        if i & 1<<j:
            num += 1
            for s in statement[j]:
                if (i & 1<<s[0]) != (s[1]<<s[0]):
                    ok = False
    if ok:
        ans = max(ans, num)
print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(input())
P = [[] for _ in range(N)]
for i in range(N):
    a = int(input())
    for _ in range(a):
        x, y = map(int, sys.stdin.readline().split())
        P[i].append((x - 1, y))

ans = 0
for pattern in range(1 << N):
    ok = True
    count = 0
    for i in range(N):
        if pattern & (1 << i):
            count += 1
            for x, y in P[i]:
                if y == 1:
                    if not pattern & (1 << x):
                        ok = False
                        break
                else:
                    if pattern & (1 << x):
                        ok = False
                        break
        if not ok:
            break
    if ok:
        ans = max(ans, count)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

a_list = []
person_list = []
syogen_list = []
ans = 0

for i in range(0, n):
    w = []
    v = []
    a = int(input())
    for j in range(0, a):
        x,y = map(int,input().split())
        w.append(x)
        v.append(y)
    person_list.append(w)
    syogen_list.append(v)
#print(person_list)
#print(syogen_list)

for bit in range(1 << n):
    break_flag = 0
    bit_1_cnt = 0
    for i in range(n):
        if break_flag:
            break
        if (bit >> i) & 1: #人iが正直
            for j in range(len(syogen_list[i])):
                if syogen_list[i][j] != ((bit>>(person_list[i][j]-1))&1): #矛盾　：　正直としているのに証言が食い違えばbreak
                    break_flag = 1
                    break
            bit_1_cnt += 1
        if break_flag==0 and i==n-1:
            ans = max(ans, bit_1_cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

a_list = []
person_list = []
syogen_list = []
ans = 0

for i in range(0, n):
    w = []
    v = []
    a = int(input())
    for j in range(0, a):
        x,y = map(int,input().split())
        w.append(x)
        v.append(y)
    person_list.append(w)
    syogen_list.append(v)
#print(person_list)
#print(syogen_list)

for bit in range(1 << n):
    break_flag = 0
    bit_1_cnt = 0
    for i in range(n):
        if break_flag:
            break
        if (bit >> i) & 1: #人iが正直
            for j in range(len(syogen_list[i])):
                if syogen_list[i][j] != ((bit>>(person_list[i][j]-1))&1): #矛盾　：　正直としているのに証言が食い違えばbreak
                    break_flag = 1
                    break
            bit_1_cnt += 1
#                if j == len(syogen_list[i])-1:
#                    bit_1_cnt += 1
        if break_flag==0 and i==n-1:
            ans = max(ans, bit_1_cnt)
            #ans = max(ans, bin(bit).count("1"))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

a_list = []
person_list = []
syogen_list = []
ans = 0

for i in range(0, n):
    w = []
    v = []
    a = int(input())
    for j in range(0, a):
        x,y = map(int,input().split())
        w.append(x)
        v.append(y)
    person_list.append(w)
    syogen_list.append(v)
#print(person_list)
#print(syogen_list)

for bit in range(1 << n):
    break_flag = 0
    bit_1_cnt = 0
    for i in range(n):
        #print(bin(bit))
        if break_flag:
            break
        if (bit >> i) & 1: #人iが正直
            for j in range(len(syogen_list[i])):
                if syogen_list[i][j] != ((bit>>(person_list[i][j]-1))&1): #矛盾　：　正直としているのに証言が食い違えばbreak
                    break_flag = 1
                    #print("1_break",bit>>(person_list[i][j]-1))
                    break
#                if j == len(syogen_list[i])-1:
#                    bit_1_cnt += 1
        if break_flag==0 and i==n-1:
            #ans = max(ans, bit_1_cnt)
            ans = max(ans, bin(bit).count("1"))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

a_list = []
person_list = []
syogen_list = []
ans = 0

for i in range(0, n):
    w = []
    v = []
    a = int(input())
    for j in range(0, a):
        x,y = map(int,input().split())
        w.append(x)
        v.append(y)
    person_list.append(w)
    syogen_list.append(v)
#print(person_list)
#print(syogen_list)

for bit in range(1 << n):
    break_flag = 0
    bit_1_cnt = 0
    for i in range(n):
        #print(bin(bit))
        if break_flag:
            break
        if (bit >> i) & 1: #人iが正直
            for j in range(len(syogen_list[i])):
                if syogen_list[i][j] != ((bit>>(person_list[i][j]-1))&1): #矛盾　：　正直としているのに証言が食い違えばbreak
                    break_flag = 1
                    #print("1_break",bit>>(person_list[i][j]-1))
                    break
#                if j == len(syogen_list[i])-1:
#                    bit_1_cnt += 1
#        else: #人iが嘘つき
#            for j in range(len(syogen_list[i])):
#                if syogen_list[i][j] == ((bit>>(person_list[i][j]-1))&1):
#                    break_flag = 1
#                    #print("0_break")
#                    break
        if break_flag==0 and i==n-1:
            #ans = max(ans, bit_1_cnt)
            ans = max(ans, bin(bit).count("1"))
            #print(bin(bit), bit_1_cnt)
            #print("correct")
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XY = []
for _ in range(N):
    A = int(input())
    xy = []
    for _ in range(A):
        x, y = map(int, input().split())
        x -= 1
        xy.append((x, y))
    XY.append(xy)
ans = 0
for s in range(1<<N):
    for i in range(N):
        if s>>i&1:
            for x, y in XY[i]:
                if s>>x&1 != y:
                    break
            else:
                continue
            break
    else:
        ans = max(ans, bin(s).count("1"))
print(ans)

Submission status: Accepted

Solution code:
import itertools

#a=itertools.product([0,1],repeat=N)

N = int(input())
AAA = [[] for i in range(N)]

for i in range(N):
    A = int(input())
    for j in range(A):
        AAA[i].append([int(k) for k in input().split()])


for ifkind in itertools.product([1,0],repeat=N):
    consistent = True
    for i,A in enumerate(AAA):
        if ifkind[i]==1:
            for x,y in A:
                x=x-1
                if ifkind[x]!=y:
                    consistent = False
    if consistent==True:
        print(sum(ifkind))
        break

Submission status: Accepted

Solution code:
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        # self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        # for i in range(1, self.h+1):
        #     for j in range(1, self.w+1):
        #         cx, cy = j, i
        #         for dx, dy in move_eight:
        #             nx, ny = dx + cx, dy + cy

def judge(id, sho, n):
    hito = [0]
    for i in range(n):
        if id % 2 == 1:
            hito.append(1)
        else:
            hito.append(0)
        id //= 2

    for i, h in enumerate(hito):
        if i == 0:
            continue
        if h == 1:
            for x, y in sho[i-1]:
                if hito[x] != y:
                    return -1

    return sum(hito)


def solve():
    n = getN()

    sho = []
    for i in range(n):
        a = getN()
        tmp = []
        for j in range(a):
            tmp.append(getList())
        sho.append(tmp)

    ans = -1
    for i in range(1<<n):
        ans = max(ans, judge(i, sho, n))

    print(ans)


def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
N=int(input())
ans=0
speech_l=[[] for _ in range(N)]
for i in range(N):
    tmp=int(input())
    for j in range(tmp):
        speech_l[i].append(list(map(int,input().split())))
for i in range(2**N):
    sw=0
    l=[1]*N
    tmp=N
    for j in range(N):
        if ((i >> j)&1):
            tmp-=1
            l[j]=0
    for j in range(N):
        if l[j] == 1:
            for k in speech_l[j]:
                if l[k[0]-1] != k[1]:
                    sw=1
    if sw==0:
        ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
def solve():
    # 標準入力部分
    N = int(input())  # len(person)
    A = []
    x = []
    y = []
    i = 0
    for i in range(N):
        A.append(int(input()))
        x.append([])
        y.append([])
        for j in range(A[i]):
            x_temp, y_temp = list(map(int, input().split()))
            x[i].append(x_temp)
            y[i].append(y_temp)
    
    # N人を正直者，不親切な人と仮定して矛盾せずに存在しうる正直者の最大人数を求める．
    honest_num = 0
    honest_num_new = 0
    for b in range(2**N):
        consistent = True
        case = format(b, '0'+str(N)+'b')
        # 矛盾があるか確認する処理, n-bit目が'1'のとき，n番目の人は正直者
        i = 0
        for i in range(N): # i番目の人の証言を検証
            for z in zip(x[i], y[i]): #z[0]（person[i]）がz[1]（正直者，不親切な人）であるという証言
                if case[i] == "1":
                    if case[z[0]-1] != str(z[1]):
                        consistent = False
        if consistent:
            # 矛盾がないとき，正直者の数を求める処理
            honest_num_new = case.count("1")
        # これまでの最大の人数と比較して，正直者が多いほうを採用
        honest_num = max(honest_num, honest_num_new)
    print(honest_num)



if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n=int(input())
sy=[[-1]*n for _ in range(n)]
ans=[0]
for j in range(n):
  for i in range(int(input())):
    x,y=map(int,input().split())
    sy[j][x-1]=y
for i in range(2**n):
  c=[]
  for j in range(n):
    c.append((i>>j)&1)  
  d=0  
  for i in range(n):
    if c[i]==1:
      for j in range(n):
        if sy[i][j]==-1:
          continue
        elif sy[i][j]==c[j]:
          continue
        else:
          d+=1
          break
    else:
      continue
  if d==0:
    ans.append(sum(c))
print(max(ans))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
xy=[]
ans=0

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

for i in range(2**N):

    # tfに正直フラグを格納
    tf=[0]*N
    for j in range(N):
        if (i>>j)&1:
            tf[j]=1

    # N人分の整合性確認
    marubatu = 1
    for j in range(N):
        # j番目が不親切なら見る意味なし
        if tf[j]==0:
            continue

        # 正しくなかったらtfの組み合わせおかしい　ので次の組み合わせに移る
        for k in range(len(xy[j])):
            if tf[xy[j][k][0]-1]!=xy[j][k][1]:
                marubatu = 0
                break

    if marubatu == 1:
        ans=max(ans,sum(tf))

print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())

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

ans_ls = list(itertools.product([0,1], repeat=N))

max_ans = 0
for ans in ans_ls:
    flg = True
    for i in range(len(ans)):
        if ans[i]==1:
            for xy in xy_ls[i]:
                if ans[xy[0]-1] == xy[1]:
                    pass
                else:
                    flg = False
                    break
    if flg == True:
        max_ans = max(max_ans,sum(ans))

print(max_ans)

Submission status: Accepted

Solution code:
N = int(input())
ListN=[0]
List = []
res =0
flag = True
mid =0
n =0
for i in range(N):
  k = int(input())
  n += k
  ListN.append(n)
  for j in range(k):
    List.append(list(map(int, input().split())))
#print(List)
for bits in range(2**N):
  mid=0
  flag= True
  for j in range(N):
    #print(bits,j,((bits>>j) & 1))
    if((bits>>j) & 1): 
      mid+= 1
      #print(ListN[j],ListN[j+1])
      for k in range(ListN[j],ListN[j+1]):
        mynum = bits
        #print(bits,List[k][0],(mynum>>List[k][0])&1, List[k][1])
        if ((mynum>>List[k][0]-1)&1) != List[k][1]:
          flag = False
          break
  #print(bits,flag,mid)
  if flag:
    res = max(res,mid)
print(res)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
a = deque()
a_num = 0
b =deque()
c = deque()
for i in range(N):
  a_num = int(input())
  a.append(a_num)
  k,p=0,0
  x = [0]*N
  b_num=deque()
  for i in range(a_num):
    k,p = map(int,input().split())
    b_num.append(k-1)
    x[k-1]=p
  b.append(b_num)
  c.append(x)
max_num = 0   
for i in range(2**N):
  two = format(i,"015b")
  two = two[::-1]
  flag=True
  for i,k in enumerate(two):
    if flag == False:
      break
    if i<N:
      if k =="1":
        for l in range(a[i]):
          for j in b[i]:
            #print(b[i],c[i][j],two[j])
            if c[i][j]!=int(two[j]):
              flag =False
              break
          if flag ==False:
            break
        if flag == False:
          break
    
    else:
      break
  if flag == True:
    #print(two)
    max_num = max(max_num,two.count("1"))  
print(max_num)

Submission status: Accepted

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

# 下からi桁目のbitが1->人iは正直
# 下からi桁目のbitが0->人iは不親切
# 不親切な人の証言は無視して良い

ans = 0
for i in range(2**N):
    for j in range(N):
        flag = 0
        if (i >> j) & 1:
            for k in range(A[j][0]):
                l = A[j][1][k][0]
                m=A[j][1][k][1]
                # print(i,j,k,(l,m),(i >> (l-1)))
                if not (i >> (l-1)) & 1 == A[j][1][k][1]:
                    flag = 1
                    break
            if flag == 1:
                break
    else:
        # print(bin(i))
        ct = 0
        for l in range(N):
            ct += ((i >> l) & 1)
        ans = max(ans, ct)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
query = []
ans = 0

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

for i in range(1<<N):
    count = 0
    FLG = True
    for j in range(N):
        if (i >> j) & 1:
            count += 1
            for x, y in query[j]:
                if (i >> (x - 1)) & 1 != y:
                    FLG = False
                    break   
        if not FLG:
            break
    else:
        ans = max(ans, count)

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())
l1 = []
for _ in range(n):
    l2 = []
    for _ in range(int(input())):
        l2.append(list(map(int, input().split())))
    l1.append(l2)

ans = 0
for k in product([1, 0], repeat=n):
    check = True
    for i, j in enumerate(l1):
        if k[i] == 0:
            continue
        for x in j:
            if k[x[0] - 1] != x[1]:
                check = False
    if check:
        ans = max(ans, sum(k))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())
l1 = []
for _ in range(n):
    l2 = []
    for _ in range(int(input())):
        l2.append(list(map(int, input().split())))
    l1.append(l2)

ans = 0
for k in product([1, 0], repeat=n):
    ng_check = False
    for i, j in enumerate(l1):
        if k[i] == 0:  # 不親切な人とした場合は弾く
            continue
        for x in j:  # 整合性が取れてるかチェック
            if k[x[0] - 1] != x[1]:
                ng_check = True  # 不整合
                break
        if ng_check:  # 整合性が取れてない場合
            break
    else:
        ans = max(ans, sum(k))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

memo = {}
for i in range(n):
    man_idx = i
    count = int(input())
    comment = [ list(map(int,input().split())) for _ in range(count) ]
    memo[man_idx] = comment

ans = 0
for i in range(2**n):
    sub_ans = 0
    is_true = True
    for j in range(n):
        if i >> j & 1:
            sub_ans += 1
            for x, y in memo[j]:
                if (i >> (x-1) & 1)  !=  int(y):
                    is_true = False
                    break
    if is_true:
        ans = max(sub_ans, ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
N = int(input())
H = []
A = []

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

for P in product([0,1],repeat=N):
  for h in H:
    if P[h[0]]==1 and P[h[1]]!=h[2]:
      break
  else:
    A+=[sum(P)]

print(max(A))

Submission status: Accepted

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

n = int(input())

#-1:undefined 0:unkind 1:honest
honest_thought = [[] for _ in range(n+1)] 
unkind_thought = [[] for _ in range(n+1)] 

for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = list(map(int, input().split()))
        if y == 0:
            unkind_thought[i].append(x)
        else:
            honest_thought[i].append(x)


ans = 0

for i in range(2 ** n):
    #print(i)
    flag = True

    #最初を設定
    honest = [False] * (n+1)
    unkind = [False] * (n+1)

    q = deque()
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            honest[j+1] = True
            q.append(j)

    while len(q) > 0 and flag:
        v = q.popleft()
        for x in unkind_thought[v]:
            if honest[x]:
                flag = False
                break
            elif not unkind[x]:
                unkind[x] = True
        for x in honest_thought[v]:
            if unkind[x]:
                flag = False
                break
            elif not honest[x]:
                flag = False
                break

    if flag:
        ans = max(ans, honest.count(True))


print(ans)

Submission status: Accepted

Solution code:
import itertools
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    ans=0
    n=INT()
    A=[]
    for i in range(n):
        a=INT()
        A.append([])
        for k in range(a):
            x,y=INTM()
            x-=1
            A[i].append([x,y])

    #print(A)

    for i in itertools.product([0,1], repeat=n):
        #print(str(sum(i))+'aaaa')
        flg=True
        for k in range(n):
            if i[k]==1:
                for j in A[k]:
                    if i[j[0]]!=j[1]:
                        flg=False
                        break
        
        if flg:
            ans=max(ans,sum(i))

    print(ans)


if __name__=='__main__':
    do()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n=int(input())
s=[]
ans=0
for i in range(n):
    a=int(input())
    s.append([list(map(int,input().split())) for _ in range(a)])
for i in range(2**n):
    bit=bin(i)[2:].zfill(n)
    flag=1
    for j in range(n):
        if bit[j]=='0':
            continue
        for sh in s[j]:
            if int(bit[sh[0]-1])!=sh[1]:
                flag=0
    if flag:
        ans=max(ans,bit.count('1'))
print(ans)

Submission status: Accepted

Solution code:
import itertools
N=int(input())
A=[]
Z=[]
for _ in range(N):
    a_i=int(input())
    z_i=[]
    A.append(a_i)
    for i in range(a_i):
        a,b=map(int,input().split())
        z_i.append([a-1,b])
    Z.append(z_i)
ans=0
for bit in itertools.product([0,1],repeat=N):
    f=True
    for j in range(N):
        if bit[j]==1:
            for k in range(A[j]):
                if bit[Z[j][k][0]]!=Z[j][k][1]:
                    f=False
                    break
    if f:
        ans=max(ans,bit.count(1))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Assertions = []
ansnum = 0

for i in range(N):
    b = []
    n = int(input())
    for j in range(n):
        xi,yi = map(int,input().split())
        b.append([xi-1,yi])
    Assertions.append(b)

for i in range(2**N):
    select = []
    
    ans = [0 for _ in range(N)]
    index = []
    flag = True
    
    for j in range(N):
        if ((i >> j) & 1):
            select.append(Assertions[j])
            
            index.append(j)
            
            ans[j] = 1
            
    
    for idx in index:
        for Assert in Assertions[idx]:
            if ans[Assert[0]] != Assert[1]:
                flag = False
                break
    
    if flag:
        ansnum = max(ansnum,len(index))

print(ansnum)

Submission status: Accepted

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

for j in range(n):
    a=int(input())
    for h in range(a):
        x,y=map(int,input().split())
        tes[j].append(x)
        tes[j].append(y)

for i in range(2**n):
    f=0
    m=0
    rel=[0 for _ in range(n)]
    for j in range(n):
        if (i>>j)&1:
            rel[j]=1
            m+=1
            
    
    for j in range(n):
        
        for q in range(len(tes[j])//2):
            if rel[j]==1 and tes[j][2*q+1]!=rel[tes[j][2*q]-1]:
                f=1
    if f==0:
        ans.append(m)
print(max(ans))