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 sys
from pprint import pprint

def solve(n, info):
    ans = 0
    for i in range(2 ** n):
        true_info = {}
        p_info = [0] * n
        for j in range(n):
            if (i >> j) & 1:
                true_info[j] = info[j]
                for x, y in info[j]:
                    if y == 1:
                        true_info[x-1] = info[x-1]
                # pprint(info[j])
                p_info[j] = 1
        # print("p_info")
        # pprint(p_info)
        # print("true_info")
        # pprint(true_info)
        flag = True
        for _, info_list in true_info.items():
            for x, y in info_list:
                if p_info[x-1] != y:
                    flag = False
                    break
            if not flag:
                break

        if flag:
            # pprint(true_info)
            ans = max(ans, sum(p_info))

    print(ans)

if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    info = []
    for i in range(n):
        a = int(sys.stdin.readline().strip())
        info.append([])
        for _ in range(a):
            x, y = map(int, sys.stdin.readline().strip().split(" "))
            info[i].append((x, y))
    
    # pprint(info)
    solve(n, info)

Submission status: Accepted

Solution code:
#-*- coding: utf-8 -*-
"""
oj dl https://atcoder.jp/contests/abc116/tasks/abc116_d -d test-d
oj test -d test-d -c "python abc116d.py"
oj test -d test-d -c "python abc116d.py" test-d/sample-3.in
"""
from collections import defaultdict
import sys
import math
from datetime import datetime
import re

def count1(bits):
    counter = 0
    while bits > 0:
        if bits & 1:
            counter += 1
        bits >>= 1
    return counter

def sol(N, testimonies):
    # print(N)
    # print(testimonies)
    maxi = 0
    for i in range(1<<N):
        ok = True
        for j in range(N):
            for x, y in testimonies[j]:
                if i & (1 << j): #正直者
                    if i & (1 << (x-1)) and not y: # 正直者と行っており、そうじゃないやん
                        ok = False; break
                    elif not (i & (1 << (x-1))) and y: #嘘つきといってるけど、そうじゃないやん！
                        ok = False; break
            if not ok:
                break
        if ok:
            maxi = max(count1(i), maxi)
    return maxi


do_submit = True
#do_submit = False

def input_parse(input_str):
    lines = [x.strip() for x in input_str.split("\n") if x.strip()]
    parsed_lines = [list(map(str, line.split())) for line in lines]
    #print(parsed_lines)
    n = int(parsed_lines[0][0])
    k = int(parsed_lines[0][1])
    #S = parsed_lines[0][0]
    return n, k


if not do_submit:
    n, k = input_parse("""
    5
10 4 8 7 3
    """)
    print(sol(n, k))

    n, k = input_parse("""
    100000 5
    """)
    print(sol(n, k))


else:
    N = int(input().strip())
    testimonies = []
    for i in range(N):
        A = int(input().strip())
        XYs = []
        for j in range(A):
            x, y = list(map(int, input().split()))
            XYs.append((x, y))
        testimonies.append(XYs)
    #S = input()
    print(sol(N, testimonies))

    # S = input().strip()
    # print(sol(S))

Submission status: Accepted

Solution code:
import itertools

n = int(input())

dic = {}


for val in range(n):
    a = int(input())
    h_L = []
    for _ in range(a):
        a1,a2 = list(map(int,input().split()))
        tmp = [a1-1,a2]
        h_L.append(tmp)
    dic[val] = h_L

ans = []
#print(dic)

bit = itertools.product([0,1],repeat=n)
#bit = [(1,1,0)]
for val in bit:
    flag = True
    for i,katei in enumerate(val):
        if katei == 0:
            continue
        if katei == 1:
            for hatsugen in dic[i]:
                #print(i,hatsugen)
                if hatsugen[1] != val[hatsugen[0]]:
                    flag = False
                    #print("aaa",i,hatsugen[1],val[hatsugen[0]])
    if flag is True:
        ans.append(sum(val))

print(max(ans))

Submission status: Accepted

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

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

def counter(status):
    f=1
    l=[-1]*N
    for i in range(N):
        if status[i]==0:
            continue
        else:
            for j in range(A[i]):
                if (l[XY[i][j][0]-1]!=-1 and l[XY[i][j][0]-1]!=XY[i][j][1]) or (status[XY[i][j][0]-1]!=XY[i][j][1]):
                    f=0
                    break
                else:
                    l[XY[i][j][0]-1]=XY[i][j][1]
    return([0,status.count(1)][f])

ans=0                
for i in range(2**N):
    ans=max(ans,counter(PRD[i]))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

ans = 0
for i in range(2 ** n):
    flg = True
    for j in range(n):
        if (i >> j) & 1 == 1:
            for k in tbl[j]:
                if (i >> (k[0] - 1)) & 1 != k[1]:
                    flg = False
    if flg == True:
        ans = max(ans, str(bin(i)).count('1'))

print(ans)

Submission status: Accepted

Solution code:
def counter(x):
    if x == 0:
        return 0
    return counter(x >> 1) + (x & 1)


N = int(input())
A = [0 for i in range(20)]
x = [[0 for i in range(20)] for j in range(20)]
y = [[0 for i in range(20)] for j in range(20)]

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

# 2^N 通りをbit全探索
# kが正直者 = 2進数表記のk-1桁目が1 (1 <= k <= N)
ans = 0
for bits in range(1, 1 << N):
    ok = True
    for i in range(1, N + 1):
        # 不親切な人の証言は無視
        if ((bits >> (i - 1)) & 1) == 0:
            continue
        for j in range(1, A[i] + 1):
            # x_ij が正直者であることが偽であれば False
            if ((bits >> (x[i][j] - 1)) & 1) != y[i][j]:
                ok = False
    if ok:
        ans = max(ans, counter(bits))

print(ans)

Submission status: Accepted

Solution code:
def counter(x):
    if x == 0:
        return 0
    return counter(x >> 1) + (x & 1)


N = int(input())
A = [0 for i in range(20)]
x = [[0 for i in range(20)] for j in range(20)]
y = [[0 for i in range(20)] for j in range(20)]

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

# 2^N 通りをbit全探索
# kが正直者 = 2進数表記のk-1桁目が1 (1 <= k <= N)
ans = 0
for bits in range(1, 1 << N):
    ok = True
    for i in range(1, N + 1):
        # 不親切な人の意見は無視
        if not ((bits >> (i - 1)) & 1):
            continue
        for j in range(1, A[i] + 1):
            # x_ij が正直者であることが偽であれば False
            if ((bits >> (x[i][j] - 1)) & 1) ^ y[i][j]:
                ok = False
    if ok:
        ans = max(ans, counter(bits))

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
N=int(input())
box = [[None]*N for i in range(N)]
for i in range(N):
  A = int(input())
  for j in range(A):
    x,y = map(int,input().strip().split())
    box[i][x-1]=y

ans=0
for bi in range(2 ** N - 1, -1, -1):
  chk=True
  for i,A in enumerate(box):
    if (bi>>i)%2 == 0:
      continue
    for j,y in enumerate(A):
      if y is None:
        continue
      elif y == 0 and (bi>>j)%2 == 1:
        chk=False
        break
      elif y == 1 and (bi>>j)%2 == 0:
        chk=False
        break
      else:
        pass
    if not chk:
      break
  if chk:
    tmp=0
    for c in range(N):
      if (bi>>c)%2 == 1:
        tmp+=1
    ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
def counter(x):
    if x == 0:
        return 0
    return counter(x >> 1) + (x & 1)


N = int(input())
A = [0 for i in range(20)]
x = [[0 for i in range(20)] for j in range(20)]
y = [[0 for i in range(20)] for j in range(20)]

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

# 2^N 通りをbit全探索
# kが正直者 = 2進数表記のk-1桁目が1 (1 <= k <= N)
ans = 0
for bits in range(1, 1 << N):
    ok = True
    for i in range(1, N + 1):
        # 不親切な人の意見は無視
        if not (bits & (1 << (i - 1))):
            continue
        for j in range(1, A[i] + 1):
            # x_ij が正直者であることが偽であれば False
            if ((bits >> (x[i][j] - 1)) & 1) ^ y[i][j]:
                ok = False
    if ok:
        ans = max(ans, counter(bits))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
dic = {i:[] for i in range(n)}

for ni in range(n):
  a = int(input())
  for ai in range(a):
    x,y = map(int,input().split())
    dic[ni].append((x-1,y))

ans = 0    
    
for i in range(2**n):
  p = [0]*n
  for j in range(n):
    if i>>j & 1:
      p[j]=1  
  
  flag = True
  for j in range(n):    
    if p[j]:
      for h,tf in dic[j]:
        if (tf==1 and p[h]==1) or (tf==0 and p[h]==0):
          pass
        else:
          flag = False          
  if flag:
    ans = max(ans,sum(p))
    
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
xy=[[] for i in range(N)]

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

m=0
for i in range(2**N):
  f=True
  for j in range(N):
    if (i>>j)&1==0:
      continue	
    for k in xy[j]:
      if (i>>k[0])&1!=k[1]:
        f=False
        break
    if f==False:
      break
  if f==True:
    c=0
    while i>0:
      c+= i&1
      i >>= 1
    m=max(m,c)
print(m)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
xy = [[] for i in range(n)]
for i in range(n):
    for j in range(inp()):
        a,b = inpl()
        xy[i].append([a,b])
# print(xy)
res = 0
for flag in itertools.product([0,1],repeat=n):
    cnt = 0
    theory = [-1]*n #-1:決まってない 0:不明 1:正直
    f = True
    for i,j in enumerate(flag):
        if theory[i] == -1:
            theory[i] = j
        elif theory[i] != j:
            f = False
            break
        if not j:
            continue
        cnt += 1
        for k in xy[i]:
            if theory[k[0]-1] == -1:
                theory[k[0]-1] = k[1]
            elif theory[k[0]-1] != k[1]:
                f = False
                break
        if not f:
            break
    if not f:
        continue
    res = max(res,cnt)
print(res)

Submission status: Accepted

Solution code:
N = int(input())
kind = []
unkind = []
for _ in range(N):
    a = int(input())
    k = u = 0
    for _ in range(a):
        ans, y = [int(_) for _ in input().split()]
        ans -= 1
        if y:
            k += 2**ans
        else:
            u += 2**ans
    kind += [k]
    unkind += [u]
ans = 0
for B in range(2**N - 1, -1, -1):
    k = 0
    u = 0
    for b in range(N):
        if (B >> b) & 1:
            k |= kind[b]
            u |= unkind[b]
    if (k & B) == k and (u & B) == 0:
        ans = max(ans, bin(B).count('1'))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

x_list = []
y_list = []

# 証言の数のリスト
A_list = []


# 入力処理
for n in range(N):
    # 各人が持ってる証言の数
    A = int(input())
    A_list.append(A)
    x = []
    y = []
    for a in range(A):
        x_tmp, y_tmp = map(int, input().split())
        x.append(x_tmp)
        y.append(y_tmp)
    x_list.append(x)
    y_list.append(y)


# 正直者（仮定）のリスト
# Falseで初期化　みんな不親切だと仮定する
isHonest_list = [False] * N

# 解候補のリスト
ans_candidate = []

# 全探索
def dfs(i, isHonest_list, ans_candidate):
    # 正直者・不親切の仮定が矛盾しないかどうか判定する
    # 矛盾しない場合、解候補のリストに正直者の人数を追加する
    if i >= N:
        isNotContradict = True  # 矛盾しないと仮定する
        for n in range(N):
            # 人iが不親切という仮定のときは証言を考慮しない
            if isHonest_list[n] == False:
                continue
            # 正直（仮定）な人iの各証言を考慮
            for A_list_i in range(A_list[n]):
                # 正直な人（仮定）なのに不親切な人のことを正直者、
                # もしくは正直者のことを不親切と証言してたら矛盾する
                if (y_list[n][A_list_i] == 1 and isHonest_list[x_list[n][A_list_i]-1] == False) or\
                    (y_list[n][A_list_i] == 0 and isHonest_list[x_list[n][A_list_i]-1]):
                    isNotContradict = False
                    break
            else:
                continue
            break

        # 矛盾しないとき
        if isNotContradict:
            ans_candidate.append(isHonest_list.count(True))
        return

    # 不親切な人であると仮定する
    isHonest_list[i] = False

    dfs(i+1, isHonest_list, ans_candidate)
    
    # 正直者であると仮定する
    isHonest_list[i] = True
    dfs(i+1, isHonest_list, ans_candidate)

dfs(0, isHonest_list, ans_candidate)
print(max(ans_candidate))

Submission status: Accepted

Solution code:
from itertools import product
n=int(input())
m=[]
for i in range(n):
  a=int(input())
  t=[-1]*n
  for j in range(a):
    each=list(map(int,input().split()))
    t[each[0]-1]=each[1]
  m.append(t)

ans = 0
prod=list(product(range(2),repeat=n))
for i in range(len(prod)):
  flag=1
  for j in range(n):
    if prod[i][j] == 1:
      for k in range(n):
        if m[j][k] != -1 and m[j][k] != prod[i][k]:
          flag = 0
          break
      if flag == 0:
        break
  if flag:
    ans = max(ans, sum(prod[i]))
  
print(ans)

Submission status: Accepted

Solution code:
#import heapq
#import itertools
#import math
#import numpy as np
#import sys

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

# bit all search
P = []
for i in range(2 ** N): # 全パターン数を1つずつ作っていく
    pat = [0] * N
    for j in range(N): 
        if ((i >> j) & 1) : #もとの数iを2進数表記でみて、1が立ってる箇所をチェックしていく  
            pat[N - 1 - j] = 1 
    P.append(pat)
#print(P)

# 正直 or 偽物の条件にマッチするやつチェック
ans = 0
flag = 'Y'
for p in P :
    for i in range(N) :
        if p[i] == 1 : # 正直者である人の意見を見に行く
            for x in X[i] :
                if x[1] != p[x[0]-1] :
                    flag = 'N'
    if flag == 'Y' : # flag = Y を維持したなら矛盾なしということで判定
        c = sum(p)
        if c > ans :
            ans = c
    flag = 'Y' # 初期化
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

#人が一人しかいないとき
if N == 1:
    print(1)
    exit()

#人が2人以上いるとき
#N人それぞれが正直か不誠実かの全パターンを生成
H = []
for i in range(2**N):
    S = str(bin(i))
    H.append(S[2:].zfill(N))
#入力を受け取る
IXY = []
for i in range(N):
    t = int(input())
    for j in range(t):
        x,y = map(int,input().split())
        #i番目の人が「x番目の人はyである」と証言
        IXY.append([i,x,y])

ans = 0
for h in H:
    cnt = h.count("1")
    for ixy in IXY:
        i,x,y = ixy[0],ixy[1]-1,ixy[2]
        if h[i] == "1" and h[x] != str(y):
            cnt = 0
            break
    ans = max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [0] * N
X = [[0]*N for _ in range(N)]
Y = [[0]*N for _ in range(N)]

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

ans = 0
for i in range(1 << N):
    flg = True
    for j in range(N):
        if i >> j & 1 ^ 1:
            # 不親切な人ならば、証言を見ても意味がない
            continue
        for k in range(A[j]):
            if i >> X[j][k] & 1 ^ Y[j][k]:
                flg = False
                break
        if not flg: break
    if flg: ans = max(ans,str(bin(i))[2:].count('1'))
print(ans)

Submission status: Accepted

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

def is_consistent(table,hito):
    flag=True
    for i in range(len(hito)):
        if hito[i]==0:
            continue
        elif hito[i]==1:
            for j in range(len(hito)):
                if table[i][j]==None:
                    continue
                elif table[i][j]!=hito[j]:
                    flag=False
                    break
        if flag==False:
            break
    return flag
  
ans=0
for i in range(0,2**N):
    length=len(bin(i)[2:])
    hito=[]
    for j in range(length):
        hito.append(int(bin(i)[2:][-j-1]))
    for j in range(N-length):
        hito.append(0)
    hito.reverse()
    if is_consistent(table,hito):
        ans=max(ans,sum(hito))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
witness = []
 
for i in range(n):
    a = int(input())
    witness.append([])
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        witness[-1].append((x,y))
 
def is_honest(i, j):
    return (i >> j) % 2 == 1
 
def honest_cnt(i):
    ans = 0
    for j in range(n):
        ans += is_honest(i, j)
    return ans
 
ans = 0
 
for i in range(1 << n):
    ok = True
    for j in range(n):
        if not is_honest(i,j):continue
        for (x, y) in witness[j]:
            if y == 0 and is_honest(i, x):
                ok = False
            if y == 1 and not is_honest(i, x):
                ok = False
    if ok:
        ans = max(ans, honest_cnt(i))
 
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    
    bit = bin(i)[2:].zfill(n)[::-1]
    cnt = bit.count('1')
    b = False
    
    for i,t in zip(bit,A):
        if i == '0': continue
        for p in t:
            k,v = p 
            if bit[k-1] != str(v):
                b = True
                cnt = 0
                break
        
        if b == True: break
    
    ans = max(ans,cnt)

print(ans)

Submission status: Accepted

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

ans=0
for i in range(2**n):
    r=1
    ib=list(format(i,"b").zfill(n))
    for j in range(n):
        if ib[j]=="1":
            for k in range(len(a[j])):
                if int(ib[a[j][k][0]-1])!=a[j][k][1]:
                    r=0
    if r==1:
        ans=max(ans,ib.count("1"))
print(ans)

Submission status: Accepted

Solution code:
def GetBitStands(val):
    i = 0
    while val > 0 :
        if (val & 1) != 0 : yield i
        i += 1
        val >>= 1

def GetBitCount(val):
    cnt = 0
    while val > 0 :
        if (val & 1) != 0 :
            cnt += 1
        val >>= 1
    return cnt

def IsAllHonest(bit_map,peaple):
    for index in GetBitStands(bit_map):
       if not peaple[index].is_honest(bit_map) :
           return False
    return True

def Honests(peaple):
    for i in range(1 << len(peaple)):
        if IsAllHonest(i,peaple):
            yield i

class UserWord:
    def __init__(self):
        self.has_word = 0
        self.word = 0
    def is_honest(self,bit):
        return (bit ^ self.word)&self.has_word == 0



num = int(input())

peaple = []


for i in range(num):
    p = UserWord()
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        #i番目の人が「x番目の人はyである」と証言
        mask = 1 << (x-1)
        p.has_word |= mask
        if y != 0:
            p.word |= mask
    peaple.append(p)

max = 0
for kouho in Honests(peaple):
    temp = GetBitCount(kouho)
    if max < temp:
        max = temp

print(max)

Submission status: Accepted

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

answer = 0
# 状態n
for n in range(2 ** N):
    # 正直者のリスト
    true_person = []
    index = 0
    copy_n = n
    while copy_n:
        if copy_n & 1:
            true_person.append(index)
        index += 1
        copy_n >>= 1

    # 矛盾が生じたときTrue
    flag = False

    # 人i
    for i in true_person:
        # iさんの証言
        for x,y in xy[i]:
            # 証言と状態が違う場合
            if (x in true_person and y == 0) or (not(x in true_person) and y == 1):
                flag = True
        if flag:
            break
    if flag:
        continue
    else:
        answer = max(answer, len(true_person))
    
print(answer)

Submission status: Accepted

Solution code:
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
ans = next(i for i in count(n, -1) for x in map(set, combinations(r, i))
           if all(a[j][0].isdisjoint(x) and a[j][1] < x for j in x))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0
for ts in product([1,0], repeat=n):
    for i, t in enumerate(ts):
        if t:
            if not all(ts[x-1] == y for x, y in xy[i]):
                break

    else:
        ans = max(ans, sum(ts))

print(ans)

Submission status: Accepted

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

flag = True
ans = []
for i in range(2 ** N):
	l = list(format(i, 'b').zfill(N))
	k = [int(s) for s in l]
	for j in range(N):
		if k[j] == 1:
			for l in range(len(A[j])):
				if A[j][l][1] != k[A[j][l][0] - 1]:
					flag = False
					break
	if flag == True:
		ans.append(k.count(1))
	else:
		flag = True

print(max(ans))

Submission status: Accepted

Solution code:
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
r = next(i for i in count(n, -1) for x in map(set, combinations(r, i))
         if all(a[j][0].isdisjoint(x) and a[j][1] < x for j in x))
print(r)

Submission status: Accepted

Solution code:
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
r = next(i for i in count(n, -1) for x in map(set, combinations(r, i))
         if all(a[j][0].isdisjoint(x) and a[j][1].issubset(x) for j in x))
print(r)

Submission status: Accepted

Solution code:
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
r = next(i for i in count(n, -1) for x in combinations(r, i)
         if all(a[j][0].isdisjoint(x) and a[j][1].issubset(x) for j in x))
print(r)

Submission status: Accepted

Solution code:
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
r = next(i for i in count(n, - 1) for x in combinations(r, i)
         if all(a[j][0].isdisjoint(x) and a[j][1].issubset(x) for j in x))
print(r)

Submission status: Accepted

Solution code:
from itertools import combinations, count
 
n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)
r = next(i for i in count(n, - 1) for x in map(set, combinations(r, i))
         if all(a[j][0].isdisjoint(x) and a[j][1] < x for j in x))
print(r)

Submission status: Accepted

Solution code:
from itertools import product

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

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

ans = 0

for ts in product([1,0], repeat=n):
    for i, t in enumerate(ts):
        if t:
            if not all(ts[x-1] == y for x, y in xy[i]):
                break
    else:
        ans = max(ans, sum(ts))

print(ans)

Submission status: Accepted

Solution code:
def popcount(x):
  r, q = 0, x
  while x:
    r += 1
    x &= x - 1
  return r, q
 
n = int(input())
r = range(n)
a = [[0, 0] for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y] |= 1 << (x - 1)
l = (1 << n) - 1 
b = sorted(map(popcount, range(1, l + 1)))
ans = next((i for i, x in reversed(b)
           if all(a[j][0] & x == a[j][1] & l - x == 0 for j in r if x >> j & 1)), 0)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ansli=[0]

import itertools

#判定配列用意
a=[]
for i in range(n):
  templi=[]
  for j in range(int(input())):
    x,y=map(int,input().split())
    templi.append([x,y])
  a.append(templi)

for i in itertools.product((0,1),repeat=n): #2のn乗通りの組み合わせ全て調査。
  temp=[-1]*n #n人について判定用配列作る。
  flag=1
  for j in range(n): #n人それぞれの証言を検証する。
    for k in a[j]: #jさんのk番目の証言について。
      x=k[0]-1
      y=k[1]

      #ここから先はjさんが正直か迷惑かでわかれる
      if i[j]==1: #もしjさんが正直なら…

        #まだ判定用配列に値がない場合
        if temp[x]==-1:
          temp[x]=y #このyの値をデフォルトとする。
        
        #判定用配列に既に値がある場合
        else:
          if temp[x]!=y: #先に入っている値と矛盾する場合は、このitertoolsループをスキップ
            flag=0
            break

      # else: #jさんが迷惑な場合…

      #   #まだ判定用配列に値がない場合
      #   if temp[x]==-1:
      #     if y==1:
      #       temp[x]=0 #このyの値をデフォルトとする。
      #     else:
      #       temp[x]=1
      #   #判定用配列に既に値がある場合
      #   else:
      #     if temp[x]==y: #先に入っている発言と矛盾する場合は、このitertoolsループをスキップ(jさんが嘘つきな場合なので、数値一致するケースが矛盾。)
      #       flag=0
      #       break

  #発言の検証のあとは、itertoolsと判定用配列の矛盾を調査
  for j in range(n):
    if temp[j]!=-1:
      if i[j]!=temp[j]: #ここで矛盾の検査
        flag=0
        break
  if flag==1: #全て検証して矛盾がない場合は、答えを入れてあげよう。
    ansli.append(sum(i))
    #print(i)

print(max(ansli))

Submission status: Accepted

Solution code:
n = int(input())
x = [[] for i in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    x[i].append(tuple(map(int,input().split())))
m = 0
for i in range(1,2**n):
  c = bin(i)[2:]
  c = '0'*(n-len(c)) + c
  f = 1
  co = 0
  for j in range(n):
    if c[j] == '1':
      co += 1
      for k,l in x[j]:
        if int(c[k-1]) != l:
          f = 0
          break
    if f == 0:
      break
  if f:
    m = max(m,co)
print(m)

Submission status: Accepted

Solution code:
def popcount(x):
  r = 0
  while x:
    r += 1
    x &= x - 1
  return r
 
n = int(input())
r = range(n)
a = [[0, 0] for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y] |= 1 << (x - 1)
 
m = 0
l = (1 << n) - 1
for x in range(1, l + 1):
  if all(a[i][0] & x == a[i][1] & l - x == 0 for i in r if x >> i & 1):
    m = max(m, popcount(x))
print(m)

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

def main():
    comb = (np.arange(2 ** n).reshape(-1, 1) >> np.arange(n) & 1).astype(np.bool)
    for i in range(n):
        for x, y in xy[i]:
            bl = ~comb[:, i] | (comb[:, x] == np.bool(y))
            comb = comb[bl] # ありえる組み合わせだけを残す
    '''
    ~comb[:, i]:= (i番目がUnkindと仮定したとき、)i番目をUnkind(False)としている組み合わせを残す
    (comb[:, x] == np.bool(y)):= (i番目がHonestと仮定したとき、)i番目の証言が矛盾しない組み合わせを残す
    '''
    
    ans = np.amax(np.sum(comb, axis=1))
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    pat = []
    for j in range(n):
        pat.append((i>>j)%2)
    check = True
    for j in range(n):
        if pat[j]:
            for z in xy[j]:
                if pat[z[0]-1] != z[1]:
                    check = False
    if check:
        ans = max(ans, sum(pat))
print(ans)

Submission status: Accepted

Solution code:
import itertools


n = int(input())

all = list(itertools.product([0,1], repeat=n))
xy,xyz = [],[]
for _ in range(n):
    a = int(input())
    for i in range(a):
        x,y = map(lambda x: int(x),input().split())
        xy.append([x,y])
    xyz.append(xy)
    xy = []


test = ['None']*n
ans = []
ans_list = []
j_list = []
bool = True
hoge = 0
for i in range(len(all)):
    for j,k in enumerate(all[len(all) - 1 - i]):
        if k == 1:
            ans.append(xyz[j])
            j_list.append(j)
    ans = list(itertools.chain.from_iterable(ans))

    test = all[len(all) - 1 - i]
    for x in range(len(ans)):
        if test[ans[x][0]-1] != ans[x][1]:
            bool = False
            break

    if bool :
        hoge = all[len(all) - 1 - i]
        break
    bool = True
    test = ['None']*n
    ans = []
    j_list = []
print(sum(hoge))

Submission status: Accepted

Solution code:
n = int(input())

class human:
    def __init__(self, a):
        self.a = a
        self.x = [None for i in range(a)]
        self.y = [None for i in range(a)]

humans = [[]for i in range(n)]
for i in range(n):
    a = int(input())
    humans[i] = human(a)
    for j in range(a):
        x, y = map(int, input().split())
        humans[i].x[j] = x
        humans[i].y[j] = y

loop_n = 2**n


def solve(bit_true):
    for i, bit in enumerate(bit_true):
        if bit == '1':
            for j, x in enumerate(humans[i].x):
                if int(bit_true[x-1]) == int(humans[i].y[j]):
                    pass
                elif int(bit_true[x-1]) != int(humans[i].y[j]):
                    return 0
    return sum(map(int, list(bit_true)))


i = 0
true_n = 0
while i < loop_n:
    bit_true = format(i, 'b').zfill(n)
    true_n = max(true_n, solve(bit_true))
    i += 1

print(true_n)