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:
def honest_or_unkind(n, tests):
    max_honest = 0
    for i in range(pow(2, n)):
        i = format(i, 'b').zfill(n)
        if str(i).count('1') > max_honest:
            flag = True
            for j, v in enumerate(str(i)):
                if v == '1':
                    for t in tests[j]:
                        if str(i)[t[0]-1] != str(t[1]):
                            flag = False
            if flag:
                max_honest = str(i).count('1')
    print(max_honest)

tests = []
n = int(input())
for i in range(n):
    a = int(input())
    tmp = []
    for j in range(a):
        tmp.append([int(k) for k in input().split()])
    tests.append(tmp)

honest_or_unkind(n, tests)

Submission status: Accepted

Solution code:


from itertools import product


def read_input():
    n = int(input())
    testimonies = {}

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

    return n, testimonies


def contradict(pattern, testimonies):
    for i, p in enumerate(pattern):
        if not p:
            continue
        else:
            for x, y in testimonies[i]:
                if pattern[x] != int(y):
                    return True    
    return False
            


def submit():
    n, testimonies = read_input()

    for pattern in product([True, False], repeat=n):
        if not contradict(pattern, testimonies):
            print(sum(pattern))
            break


if __name__ == "__main__":
    submit()

Submission status: Accepted

Solution code:
n = int(input())

evidences = [[] for _ in range(n)]
for i in range(n):
  a = int(input())
  for j in range(a):
    x,y = map(int, input().split())
    evidences[i].append((x-1, y))
    
result = 0
for i in range(1, 2**n):
  consistent = True
  for j in range(n):
    if (i >> j) & 1 == 0:
      continue
    for x,y in evidences[j]:
      if (i >> x) & 1 != y:
        consistent = False
        break
    if not consistent:
      break
  if consistent:
    result = max(result, bin(i)[2:].count('1'))
print(result)

Submission status: Accepted

Solution code:
N = int(input())
array_xy=[[] for i in range(N)]
# print(array_xy)

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

# print(array_xy)

#正直者と不親切な人のすべての場合を列挙し、証言が成り立つ場合をみる
max_honest=0
for i in range(1<<N):
    #正直者と不親切な人の組み合わせを作成
    isHonest=[False]*N
    for j in range(N):
        if ((i >> j) & 1) == 1:
            isHonest[j]=True
    # print("pattern:", isHonest)


    #証言が成り立つか確認
    ok = True
    for j in range(len(array_xy)):
        #不親切な人の時証言は気にしない
        if isHonest[j]==False:
            continue
        #正直者のときは証言をチェック→おかしければこの場合は不成立
        for k in range(len(array_xy[j])):
            tmp_x = array_xy[j][k][0]
            tmp_y = array_xy[j][k][1]
            # print("tmp_x,tmp_y",tmp_x,tmp_y)
            if  (isHonest[tmp_x-1]==True and tmp_y ==0) or \
                (isHonest[tmp_x-1]==False and tmp_y ==1):
                ok = False
        if ok == False:
            break
    if ok == True:
        # print(isHonest)
        if isHonest.count(True) > max_honest:
            max_honest = isHonest.count(True)
print(max_honest)

Submission status: Accepted

Solution code:
n = int(input())
testimony = [[] for _ in range(n)]
for i in range(n):
    for j in range(int(input())):
        x,y = map(int, input().split())
        testimony[i].append((x,y))
honest = 0
for i in range(2**n):
    flag = True
    for j in range(n):
        if (i>>j)&1:
            for x,y in testimony[j]:
                if (i>>(x-1))&1 != y:
                    flag = False
                    break
    if flag:
        honest = max(honest, bin(i)[2:].count('1'))
print(honest)

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * n
xy = [0] * n
for i in range(n):
     a[i] = int(input())
     xy[i] = [list(map(int,input().split())) for _ in range(a[i])]
memo = [0] * (2**n)
for i in range(2**n):
     flag = True
     ch = [0]*n  # あらかじめ ["-", "-", "-"] というリストを作っておく
     for j in range(n):
          if ((i >> j) & 1):
               ch[n - j - 1] = 1
     for k in range(n):
          if ch[k] == 1:
               for l in range(a[k]):
                    if xy[k][l][1] == ch[xy[k][l][0] - 1]:
                         continue
                    else:
                         flag = False

     if flag:
          memo[i] = sum(ch)
print(max(memo))

Submission status: Accepted

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

# print(whole_answers)

max_count = 0

conflict = False
for i in range(2 ** n):
    conflict = False
    for j, answers in enumerate(whole_answers):
        if i >> j & 1:
            for x, y in answers:
                if (y == 1 and i >> (x - 1) & 1 == 0) or (y == 0 and i >> (x - 1) & 1 == 1):
                    # print(bin(i))
                    conflict = True
                    break
            if conflict:
                break
    if not conflict:
        count = bin(i)[2:].count('1')
        max_count = max(max_count, count)
print(max_count)

Submission status: Accepted

Solution code:
N = int(input())
human = []
for i in range(N):
    A = int(input())
    hatugen = {}
    for j in range(A):
        x, y = map(int, input().split())
        hatugen[x] = y
    human.append(hatugen)
    
cnt = 0
for i in range(2 ** N):
    is_ok = True
    for j in range(N):
        if (i >> j) & 1:
            for K, V in zip(human[j].keys(), human[j].values()):
                k = K - 1
                if V ^ ((i >> k) & 1):
                    is_ok = False
                    break
    if is_ok:
        cnt = max(cnt, bin(i).count('1'))

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
honest = [[] for _ in range(N)]
liar = [[] for _ in range(N)]

for i in range(N):
    for _ in range(int(input())):
        x, y = map(int, input().split())
        if y == 1:
            honest[i].append(x - 1)
        elif y == 0:
            liar[i].append(x - 1)

ans = 0
for i in range(2 ** N):
    flag = True
    for j in range(N)[::-1]:
        if i >> j & 1:
            for k in honest[N - j - 1]:
                if not i >> (N - k - 1) & 1:
                    flag = False
            for k in liar[N - j - 1]:
                 if i >> (N - k - 1) & 1:
                     flag = False
            if flag is False:
                break
    if flag is True:
        ans = max(ans, bin(i).count("1"))

print(ans)

Submission status: Accepted

Solution code:
N  = int(input())
testimony = [[]for i in range(N)]
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        testimony[i].append([person-1,state])#3次元配列の作り方
honest = 0
for i in range(1, 2**N):
    flag = 0
    for j in range(N):
        if(i>>j)&1 == 1:
            for x,y in testimony[j]:#3次元リストからx,yを取り出す書きかた　覚える
                if (i>>x)&1 != y: #正直といっているがそうではない　と　嘘つきといっているがそうではない　の二つ同時
                    flag =1
                    break
    if flag == 0:
        honest = max(honest, bin(i)[2:].count('1'))# bin()で二進数に変換　最初の二文字は0bで取り除く count('1')で数える
print(honest)

Submission status: Accepted

Solution code:
n = int(input())
lis = []
for i in range(n):
    l = []
    a = int(input())
    for j in range(a):
        x, y = map(int,input().split())
        l.append([x-1,y])
    lis.append(l)
    
ho_maxcnt = 0
for i in range(1, 2**n):
    ho_cnt = bin(i).count("1")
    if ho_cnt <= ho_maxcnt: continue
    is_ok = True
    for j in range(n):
        jhonest = (i >> j) & 1
        if jhonest == 0:
            continue
        for say in lis[j]:
            if ((i >> say[0]) & 1) ^ say[1]:
                # Mujun
                is_ok = False
                break
        if not is_ok:
            break
    if not is_ok:
        continue
    if ho_cnt > ho_maxcnt:
        ho_maxcnt = ho_cnt
print(ho_maxcnt)

Submission status: Accepted

Solution code:
n = int(input())

g = [[-1] * 15 for _ in range(15)]

for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        g[i][x] = y
ans = 0
for i in range(1 << n):
    d = [0] * n
    for j in range(n):
        if i >> j & 1:
            d[j] = 1

    cnt = 0
    ok = 1
    for j in range(n):
        if d[j]:
            for k in range(n):
                if g[j][k] == -1:
                    continue
                if g[j][k] != d[k]:
                    ok = 0

    if ok:
        ans = max(ans, sum(d))
print(ans)

Submission status: Accepted

Solution code:
def int_to_list(bit, n):
    l = []
    for i in range(n):
     if bit & (1 << i):
         l.append(i)
    return l

def solve():
    N = int(input())
    A = [[] for _ in range(N)]
    for i in range(N):
        B = int(input())
        for _ in range(B):
            x, y = list(map(int, input().split()))
            A[i].append((x-1, y))

    ans = 0
    for i in range(1 << N):
        f = True
        # 正直者のリスト
        partial = int_to_list(i, N)
        for p in partial:
            for (a, b) in A[p]:
                if b == 1:
                    if not a in partial:
                        f = False
                else:
                    if a in partial:
                        f = False
        if f:
            ans = max(ans, len(partial))

    return ans

print(solve())

Submission status: Accepted

Solution code:
n = int(input())
a=[]
for i in range(n):
    len_A = int(input())
    arr = []
    for j in range(len_A):
        x,y=map(int,input().split())
        x -= 1
        arr.append((x,y))
    a.append(arr)
def is_honest(i,j):
    return (i>>j)&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(2**n):
    ok = True
    for j in range(n):
        if not is_honest(i,j):continue
        for (x,y) in a[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(a)
#print(a[0])
print(ans)

Submission status: Accepted

Solution code:
def bitcnt(n):
  n=(n&0x55555555)+(n>>1&0x55555555)
  n=(n&0x33333333)+(n>>2&0x33333333)
  n=(n&0x0f0f0f0f)+(n>>4&0x0f0f0f0f)
  n=(n&0x00ff00ff)+(n>>8&0x00ff00ff)
  n=(n&0x0000ffff)+(n>>16&0x0000ffff)
  return n
N = int(input())
xy = [[-1 for j in range(N)] for i in range(N)]
for i in range(N):
  for j in range(int(input())):
    x, y = map(int, input().split())
    x -= 1
    xy[i][x] = y
r = 0
for i in range(1<<N):
  t = [i>>j&1 for j in range(N)]
  ok = True
  for j in range(N):
    if t[j]:
      for k in range(N):
        if xy[j][k] == -1:
          continue
        if xy[j][k] != t[k]:
          ok = False
          break
  if ok:
    r = max(r, bitcnt(i))
print(r)

Submission status: Accepted

Solution code:
import math
import itertools

M = 0
N = int(input())
C = list(itertools.product([0,1],repeat=N))
A = [0]*N
x = [0]*N
y = [0]*N

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


for c in C:
  #print(c)
  marker = True
  for i in range(N):
    for j in range(A[i]):
      if c[i] == 1 and c[x[i][j]-1] != y[i][j]:
        #print(i,j)
        marker = False
  if marker == True:
    M = max(M,sum(c))
  
print(M)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import combinations
from operator import contains

def readlines(n):
    for _ in range(n):
        x, y = input().split()
        yield int(x)-1, y=="1"

def main():
    n = int(input())
    asserts = []

    for _ in range(n):
        a = int(input())
        asserts.append(list(readlines(a)))

    def check(comb):
        for i in comb:
            for x, y in asserts[i]:
                mujun = contains if not y else lambda a, b: b not in a
                if mujun(comb, x):
                    return -1
        
        return len(comb)

    for i in range(1, n+1):
        for comb in combinations(range(n), i):
            yield check(set(comb))

    yield 0

print(max(main()))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import combinations
from operator import contains

def readlines(n):
    for _ in range(n):
        x, y = input().split()
        yield int(x)-1, y=="1"

def main():
    n = int(input())
    asserts = []

    for _ in range(n):
        a = int(input())
        asserts.append(list(readlines(a)))

    def check(comb):
        for i in comb:
            for x, y in asserts[i]:
                mujun = contains if not y else lambda a, b: b not in a
                if mujun(comb, x):
                    return -1
        
        return len(comb)

    for i in range(n+1):
        for comb in combinations(range(n), i):
            yield check(set(comb))

    yield 0

print(max(main()))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import eq, ne

def readlines(n):
    for _ in range(n):
        x, y = input().split()
        yield int(x)-1, y

def main():
    n = int(input())
    graph = []

    for _ in range(n):
        a = int(input())
        graph.append(list(readlines(a)))

    def check(bits):
        for pre_honest, asserts in zip(bits, graph):
            if pre_honest == "0":
                continue
            for x, y in asserts:
                if bits[x] != y:
                    return -1
        
        return len([b for b in bits if b == "1"])

    for i in range(2**n-1, -1, -1):
        bit = format(i, "0{}b".format(n))
        ans = check(bit)
        if ans > -1:
            print(ans)
            return
    
    print(0)

main()

Submission status: Accepted

Solution code:
# from fractions import gcd
# mod = 10 ** 9 + 7
# N = int(input())
# a = list(map(int,input().split()))
# a,b,c = map(int,input().split())
# ans = [0] * N
# math.ceilで切り上げ
# dp = [[0] * 4 for i in range(3)] #2次元配列初期化
# dp = [[[0] * 2 for i in range(3)] for j in range(5)]
# (ord('A'))でASCII出力 Aは65
import math
import statistics
import string
import sys
from array import array
from collections import deque

def intinput():
    return int(input())
def listintinput():
    return list(map(int, input().split()))
def splitintinput():
    return map(int, input().split())
def factorialsurplus(x, y, z):  # xからyまでの階乗をzで割ったあまりを求める
    ret = 1
    for i in range(x, y + 1):
        ret = (ret * i) % z
    return (ret)
def isprime(x):
    if x == 1:
        return False
    if x == 2:
        return True
    sq = int(math.sqrt(x))
    for i in range(2,sq+1):
        if x % i == 0:
            return False
    return True
def hcfnaive(a,b):#最大公約数 math.gcdが使えない時の手段として入れとく。pythonが更新されたらいらなくなるはず
    if(b==0):
        return a
    else:
        return hcfnaive(b,a%b)


N = intinput()
dic = {}
ans = 0
true_person = 0
flag_contradiction = 0
for i in range(N):
    dic[i] = {}

for i in range(N):
    A = intinput()
    for j in range(A):
        x,y = splitintinput()
        dic[i][x-1] = y

for i in range(2**N):
    tmp = format(i, 'b').zfill(N)
    true_person = tmp.count('1')
    flag_contradiction = 0
    for j in range(N):
        if int(tmp[j]) == 1:
            for k in dic[j]:
                if dic[j][k] != int(tmp[k]):
                    flag_contradiction = 1
                    break
    if flag_contradiction == 0:
        ans = max(ans,true_person)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [0 for i in range(n)]
x = [[] for i in range(n)]
y = [[] for i in range(n)]
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        xx, yy = map(int,input().split())
        x[i].append(xx)
        y[i].append(yy)
ans = 0
for i in range(2**n):
    ok = True
    for j in range(n):
        if ((1 << j) & i):
            for k in range(a[j]):
                if y[j][k] == 0:
                    if (1 << (x[j][k] - 1)) & i:
                        ok = False
                else:
                    if not((1 << (x[j][k] - 1)) & i):
                        ok = False
    if ok:
        cnt = bin(i).count('1')
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [0 for i in range(n)]
x = [[] for i in range(n)]
y = [[] for i in range(n)]
for i in range(n):
    a[i] = int(input())
    for j in range(a[i]):
        xx, yy = map(int,input().split())
        x[i].append(xx)
        y[i].append(yy)
ans = 0
for i in range(2**n):
    ok = True
    for j in range(n):
        if ((1 << j) & i):
            for k in range(a[j]):
                if y[j][k] == 0:
                    if (1 << (x[j][k] - 1)) & i:
                        ok = False
                else:
                    if not((1 << (x[j][k] - 1)) & i):
                        ok = False
    if ok:
        cnt = 0
        while i:
            cnt += i & 1
            i >>= 1
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

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

for b in range(2 ** n):
    f = True
    for i in range(len(sa)):
        if ((b >> i) & 1):
            for x1, y1 in sa[i]:
                if (b >> (x1-1))&1 != y1:
                    f = False
                    break
    if f:
        ans = max(ans, bin(b)[2:].count("1"))

print(ans)

Submission status: Accepted

Solution code:
import itertools 
N = int(input())
evidence_dit = {} 
for i in range(N):
    A = int(input())
    x_y = []
    if A == 0:
        evidence_dit[i] = []
    for j in range(A):
        x_y.append(list(map(int,input().split())))        
        evidence_dit[i] = x_y 
ans = 0
attribute = [0,1] 
for i in itertools.product(attribute,repeat=N):
    flag = False    
    for j in range(N):
       if i[j] == 1:            
            for k in evidence_dit[j]:
                if i[k[0]-1] != k[1]:
                    flag = True
                    break
            if flag:
                break 
    if flag == False:
        ans = max(ans,sum(i))        
print(ans)
'''
入力:辞書型で置いておくことにした。
{0: [[2, 1], [3, 0]], 1: [[3, 1], [1, 0]], 2: [[1, 1], [2, 0]]}
証言が無い場合に [ ] を入れる。
attribute = [0,1] 
for i in itertools.product(attribute,repeat=N):
正直、不正直のパターンを列挙するところ、itertoolsで0,1の重複順列
for i in range(2 ** N):
    h = [0] * N 
    for j in range(N):
        if (i >> j) & 1:
            h[j] = 1
ビット演算子
i >> j　i を右に j ビットシフト
5 >> 2　5 を右に 2 ビットシフト
　　　　 101｜　➡　001｜01　➡　001
　　　　 右へ２つずらして足りなくなった桁は0にする。　
5 & 1　➡　101 AND 001　➡　001
　　　　　　両方１のところだけ１になる。
if 5 & 1:　5 & 1 の答えが１なら True、他は False
[0, 0, 0] [1, 0, 0] [0, 1, 0] [1, 1, 0] [0, 0, 1] [1, 0, 1] 
[0, 1, 1] [1, 1, 1]、のような0,1の全パターンを出している。
'''

Submission status: Accepted

Solution code:
'''
N人の「正直者」、「不親切な人」のすべての組み合わせを生成し、
正直者の証言が組み合わせに矛盾していないか確認する. 
矛盾していない組み合わせの正直者の最大数が解答.
組み合わせは bit で表現している. Nビット用意し、
1が立っていると正直者、0だと不親切な人. 
この組み合わせ状況と正直者の証言が矛盾しないか確認する.
'''
N = int(input())

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

result = 0
for i in range(1, 2 ** N):
    consistent = True
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        for x, y in evidences[j]:
            if (i >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
    if consistent:
        result = max(result, bin(i)[2:].count('1'))
print(result)

Submission status: Accepted

Solution code:
n = int(input())
comments = []
for i in range(n):
    a = int(input())
    temp = []
    for j in range(a):
        temp.append([int(x) for x in input().split()])
        
    comments.append(temp)

# 正直者と仮定した人が矛盾した発言をしていないかどうか調べる
# n=5でiが２進数でb00001の時、1番目の人が正直者と仮定している。
max_honest = 0
for member_state in range(2**n):
    flg = False
    for member_num in range(n):
        # member_state で1が立っているということは、正直者と仮定しているということ
        if member_state & 1<< member_num :
            #comments_check(member_state,com)
            for co in comments[member_num]:
                if member_state>>(co[0] - 1) & 1 != co[1] : #コメントが指し示す人物と証言の内容があっていれば矛盾なしとする
                    flg = True
                    break
        if flg == True:
            break
    else:
        # コメントに矛盾がないことが証明されたので正直者の人数を数え、max_honestを更新する
        member_num = 0
        for x in range(n):
            if member_state & 1<< x:
                member_num += 1

        if max_honest < member_num:
            max_honest = member_num

print(max_honest)

Submission status: Accepted

Solution code:
import itertools

n = int(input())

a = []

for _ in range(n):
    A = int(input())
    tmp = []
    for _ in range(A):
        x, y = map(int, input().split())
        x -= 1
        tmp.append([x, y])
    a.append(tmp)
    
ans = 0

for p in itertools.product([0,1], repeat=n):
    katei_list = list(p)
    mujun = False
    for i in range(n):
        if katei_list[i] == 1:
            for shogen in a[i]:
                if katei_list[shogen[0]] != shogen[1]:
                    mujun = True
                    break
            if mujun:
                break
        if mujun:
            break
    if not mujun and sum(p) > ans:
        ans = sum(p)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
g = [[0,0] for _ in range(n)]
for i in range(n):
  a = int(input())
  for _ in range(a):
    x,y = map(int,input().split())
    g[i][y] |= 1 << (x-1)
ans = 0
for num in range(1<<n):
  p = [g[j] for j in range(n) if num&(1<<j)]
  fl = 0
  if all(num & y == y and not num & x for x,y in p):
    if ans < len(p): ans = len(p)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
ans=0
say=[]
for _ in range(N):
    A=int(input())
    text=[]
    for _ in range(A):
        text.append(list(map(int,input().split())))
    say.append(text)

for i in range(2**N):
    people=[]
    for k in range(N):
        people.append(i%2)
        i//=2

    flag=True    
    for n in range(N):
        for t in say[n]:
            if people[n]!=0 and people[t[0]-1]!=t[1]:
                flag=False    
    if flag and sum(people)>ans:
        ans=sum(people)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
#証言　testimony
tes = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        tes[i].append([x-1, y])
            
# 全員正直者と仮定, n-1人正直者と仮定, n-2人正直者...と数を減らしながら全探索
for i in range(n):
    for C in itertools.combinations(range(n), n-i):
        for c in C:
            for x, y in tes[c]:
                if (y == 0 and x in C) or (y == 1 and x not in C):
                    break
            else:
                continue
            break
        else:
            print(n-i)
            exit()
print(0)

Submission status: Accepted

Solution code:
N = int(input())
A = []
lst = [list(format(i, '0%db' % N)) for i in range(2**N)]
X = [[] for i in range(N)]
Y = [[] for i in range(N)]

for i in range(N):
    tmp_A = int(input())
    A.append(tmp_A)
    for j in range(tmp_A):
        tmp_x,tmp_y = input().split()
        X[i].append(int(tmp_x)-1)
        Y[i].append(tmp_y)

ans = -1

for i in range(2**N):
    flag = 1
    for j in range(N):
        if lst[i][j] == "1":
            for k in range(A[j]):
               if lst[i][X[j][k]] != Y[j][k]:
                   flag = 0
    if flag:
        tmp = 0
        for j in lst[i]:
            if j == "1":
               tmp += 1
        if tmp > ans:
            ans = tmp

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
xy = [0]*N
A = []
ans = 0
cnt = 0
hatan = 0
for i in range(N):
    A.append(int(input()))
    xy[i] = [list(map(int,input().split())) for i in range(A[i])]
for i in range(2**N):
    cnt = 0
    hatan = 0
    bits = "0" + str(N) + "b"
    Honest_line = str(format(i,bits))
    for people in range(N):
        if(Honest_line[people] == "1"):
            cnt += 1
            for syougen in range(A[people]):
                if(int(Honest_line[xy[people][syougen][0]-1]) != xy[people][syougen][1]):
                    hatan = 1
    if(hatan == 0):
        ans = max(ans,cnt)
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1, 2 ** N):
    is_ok = True
    for j in range(N):
        if (i >> j) & 1 == 1:
            for x, y in msg[j]:
                if (i >> x) & 1 != y:
                    is_ok = False
                    break
    if is_ok:
        ans = max(ans, bin(i)[2:].count('1'))
print(ans)

Submission status: Accepted

Solution code:
import itertools


def judge(bits):
    for n in range(N):
        if not bits[n]:
            continue
        for s in X[n]:
            x, y = s
            # y = 1 なのに「不親切」だったらダメ
            if (y == 1 and (not bits[x - 1])):
                return 0
            # y = 0 なのに「正直者」だったらダメ
            if (y == 0 and bits[x - 1]):
                return 0
    return sum(bits)


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

ans = []
for bits in itertools.product([False, True], repeat=N):
    ans.append(judge(bits))

print(max(ans))

Submission status: Accepted

Solution code:
from itertools import product

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

for _ in range(n):
    ea = int(input())
    new = []
    for _ in range(ea):
        x, y = map(int, input().split())
        x -= 1
        new.append([x, y])

    xy.append(new)

ans = 0
for pat in product([1, 0], repeat=n):
    bl = True
    for i, e in enumerate(pat):
        if e:
            for x, y in xy[i]:
                if pat[x] != y:
                    bl = False

    if bl:
        ans = max(ans, sum(pat))

print(ans)

Submission status: Accepted

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


class Human:

    def __init__(self, statements):
        self.statements = statements

    def is_honest(self, honest_list):
        for x, y in self.statements:
            if y:
                if x not in honest_list:
                    return False
            else:
                if x in honest_list:
                    return False
        return True


class Humans:

    def __init__(self):
        self.humans = [None]

    def add(self, human: Human):
        self.humans.append(human)

    def is_all_honest(self, honest_list):
        for i in honest_list:
            if not self.humans[i].is_honest(honest_list):
                return False
        return True


def main():
    n = int(input())
    humans = Humans()
    for _ in range(n):
        a = int(input())
        xy = [tuple(map(int, input().split())) for _ in range(a)]
        humans.add(Human(xy))
    max_honest = 0
    for bit in range(2**n):
        honest_list = []
        for i in range(n):
            if (bit >> i) & 1:
                honest_list.append(i+1)  # 1ずれるため補正
        if humans.is_all_honest(honest_list):
            max_honest = max(max_honest, len(honest_list))
    print(max_honest)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def decode(i):
    ret = []
    for _ in range(n):
        ret.append(i & 1)
        i >>= 1
    return ret

ans = 0
for k in range(1 << n):
    l = decode(k)
    coh = True
    for i, w in enumerate(t):
        if l[i]:
            for x, y in w:
                if l[x-1] != y:
                    coh = False
    if coh:
        ans = max(ans, sum(l))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [0 for _ in range(N)]
xy = [0 for _ in range(N)]
for i in range(N) :
    A[i] = int(input())
    xy[i] = [0 for _ in range(A[i])]
    for j in range(A[i]) :
        x, y = map(int, input().split())
        xy[i][j] = (x, y)

ans = 0
for i in range(2**N):
    pat = str("{:0>{}b}".format(i, N))
    flag = True
    for j in range(N):
        if pat[j] == "1":
            for t in range(A[j]) :
                man = xy[j][t][0] - 1
                tru = xy[j][t][1]
                if pat[man] != str(tru) :
                    flag = False
    if flag == True :
        ans = max(ans, pat.count("1"))

print(ans)

Submission status: Accepted

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

res = 0
for k in range(1 << N):
    bits = [(k >> i) & 1 for i in range(N)]
    flag = True
    for i in range(N):
        if (k >> i) & 1 == 0:
            continue
        for x, y in XY[i]:
            if bits[x - 1] == y:
                continue
            flag = False
    if flag:
        res = max(res, sum(bits))
print(res)