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 copy


N=int(input())
A=[]
X=[]#X[i][j]=人i+1曰く、人X[i][j]は↓
Y=[]#Y[i][j]である(1=正直、0=不親切)
for i in range(N):
    A.append(int(input()))
    Lx=[]
    Ly=[]
    for j in range(A[i]):
        x,y=map(int,input().split())
        Lx.append(x)
        Ly.append(y)
    X.append(copy.copy(Lx))
    Y.append(copy.copy(Ly))

#print(A,X,Y)

def check(letter,n=N,a=A,x=X,y=Y):#letterは二進数の文字列
    for k in range(n):
        if letter[k]=='1':#人k-1が正直者として
            number=a[k]#主張の数
            for l in range(number):
                if y[k][l]!=int(letter[x[k][l]-1]):#人kが嘘つきなら
                    return False
                    break
            else:
                continue
            break
    else:
        return True


L=[]
for m in range(2**N):
    bin_str=bin(m)[2:]
    if len(bin_str)<N:
        bin_str=(bin_str[::-1]+'0'*(N-len(bin_str)))[::-1]
    L.append(bin_str)
#print(L)


ans=0
for p in range(len(L)):
    if check(L[p]):
        #print(L[p],check(L[p]))
        ans=max(ans,L[p].count('1'))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = [ [] for _ in range(N)]
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int,input().split())
        L[i].append([person - 1, state])

# 正直者の最大数の初期化
honest = 0

for i in range(1,2**N):
    flag = True
    for j in range(N):
        if (i>>j)&1 == 1: # j番目が正直者と仮定したとき
            for x, y in L[j]:
                if (i>>x)&1 != y: # 矛盾を発見(正直者のjといっていることが違う)
                    flag = False
                    break # 矛盾を見つけたので、それ以降のjの証言は無視
            if not flag:
                break
    if flag:
        honest = max(honest, bin(i).count("1"))

print(honest)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
work = []
for i in range(n):
    a = int(input())
    work.append([list(map(int, input().split())) for i in range(a)])
result = 0
for i in range(2**n):
    state = bin(i)[2:].zfill(n)
    honest = []
    unkind = []
    for j in range(n):
        if state[j] == "0":
            unkind.append(j+1)
        else:
            honest.append(j+1)
    flag = True
    for human in honest:
        for x, y in work[human-1]:
            if y == 1 and x in unkind:
                flag = False
                break
            elif y == 0 and x in honest:
                flag = False
                break
        if not flag:
            break
    if flag:
        result = result if result>len(honest) else len(honest)
print(result)

Submission status: Accepted

Solution code:
import math

if __name__ == '__main__':
    n = int(input())
    ans = 0
    is_honest = [-1] * n
    evidence = []
    for i in range(n):
        a = int(input())
        tmp = []
        for j in range(a):
            x, y = map(int, input().split())
            tmp.append((x - 1, y))
        evidence.append(tmp)

    # 1 -> Honest, 0 -> Liar
    for i in range(2 ** n):
        flag = True
        for j in range(n):
            # j is Liar
            if not (i & (1 << j)):
                continue
            for x, y in evidence[j]:
                if y == 1 and not (i & (1 << x)):
                    flag = False
                elif y == 0 and (i & (1 << x)):
                    flag = False
        if flag:
            count = 0
            for k in range(n):
                if i & (1 << k):
                    count += 1
            ans = max(ans, count)

    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = [None] * n
for i in range(n):
    num = int(input())
    a[i] = [list(map(int,input().split())) for _ in range(num)]

def check(i, bit_):
    com = a[i]
    for xy in com:
        x,y = xy
        if( (bit_ >> (x-1))&1 != y ):
            return 0
    return 1

ans = 0
for i in range(2**n):
    c_num = 1
    honest = 0
    for j in range(n):
        if( (i>>j)&1 == 1 ):
            honest += 1
            c_num *= check(j, i)
    if(c_num == 0):
        continue

    ans = max(ans, honest)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [0 for _ in range(N)]
X = [[[] for i in range(2)] for _ in range(N)]
for i in range(N):
    A[i] = int(input())
    for j in range(A[i]):
        x, y = map(int, input().split())
        X[i][0].append(x)
        X[i][1].append(y)
ans = 0
for i in range(pow(2,N)):
    binary = format(i, 'b').zfill(N)
    flag = True
    honest = 0
    for j in range(N):
        if int(binary[j]) == 0:
            continue
        for x, y in zip(X[j][0], X[j][1]):
            if int(binary[x-1]) != y:
                flag = False
                break
        honest += 1
    if flag:
        ans = max(ans, honest)
print(ans)

Submission status: Accepted

Solution code:
def judge(isHonest, judge_list):
    for j in judge_list:
        x, y = j 
        if isHonest[x-1] != y:
            return False
    return True  

def main():
    N = int(input())

    testimony = []
    for _ in range(N):
        A = int(input())
        testimony.append([list(map(int, input().split())) for _ in range(A)])
    
    ans = 0
    for i in range(2**N):
        judge_list = []
        isHonest = []
        for j in range(N):
            if i & (1 << j):
                judge_list += testimony[j]
                isHonest.append(1)
            else:
                isHonest.append(0)
        if judge(isHonest, judge_list):
            ans = max(ans, sum(isHonest))
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

n = int(input())
hatugen = [[]for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        c,d = map(int,input().split())
        hatugen[i].append((c,d))
ans = 0
for i in range(1,2**n):
    consistent = True
    for j in range(n):
        #i通り目のj番目の人の発言が不誠実の時は、どうでもいいのでcontinue
        if (i >> j) & 1 == 0:
                continue
        else:
            for l,m in hatugen[j]:
                if (i >> (l-1)) & 1 != m:
                    consistent = False
                    break
    if consistent == True:
        ans = max(ans,bin(i)[2:].count('1'))
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
 
testimony = [[] for _ 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])
        
honest = 0
for i in range(1, 2**N):
    flag = 0
    for j in range(N):
        if (i>>j)&1 == 1: # j番目は正直と仮定, iのｊ番目のbitが立っている
            for x,y in testimony[j]:#jの証言をiterate
                if (i>>x)&1 != y: # xのビット（0,1)とjの発言(0,1)が矛盾している
                    flag = 1
                    break
    if flag == 0:  # 矛盾がある場合はflag == 1になる
        honest = max(honest, bin(i)[2:].count('1'))  # 1の数をカウントし最大となるものを選択
print(honest)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

a = np.array(list(itertools.product([0, 1], repeat=n)), dtype=np.bool)
for i, x, y in info:
    bl = (~a[:, i]) | (a[:, x] == bool(y))
    a = a[bl]

ans = a.sum(axis=1).max()
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ttn = [[-1] * n for _ in range(n)]  # Testimonies.
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = [int(z) for z in input().split()]
            x -= 1
            ttn[i][x] = y  # i says that x is honest guy or not.
    ans = set()
    for i in range(2 ** n):
        tmp = [i >> j & 1 for j in range(n)]  # Bit-shift.
        possible = True
        for k, tm in enumerate(tmp):
            if not possible:
                break
            if tm:
                for l, tt in enumerate(ttn[k]):
                    if tt == -1:
                        continue
                    if tt != tmp[l]:
                        possible = False
                        break
        if possible:
            ans.add(bin(i).count('1'))
    return max(ans)


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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ttn = [[-1] * n for _ in range(n)]  # Testimonies.
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = [int(z) for z in input().split()]
            x -= 1
            ttn[i][x] = y  # i says that x is honest guy or not.
    ans = set()
    # for else で頑張ったが，フラグを作ったほうがずっと分かりやすいだろう。
    for i in range(2 ** n):
        tmp = [i >> j & 1 for j in range(n)]  # Bit-shift.
        for k, tm in enumerate(tmp):
            if tm:
                for l, tt in enumerate(ttn[k]):
                    if tt == -1:
                        continue
                    if tt != tmp[l]:
                        break
                else:
                    continue
                break
        else:
            ans.add(bin(i).count('1'))
    return max(ans)


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

Submission status: Accepted

Solution code:
def check(x, y):
    for a, b in zip(x, y):
        if a != b and b != -1:
            return False
    else:
        return True


n = int(input())
remarks = []
cnt_max = 0
for _ in range(n):
    a = int(input())
    x = [tuple(map(int, input().split())) for i in range(a)]
    r = [-1] * n
    for i, j in x:
        r[i - 1] = j
    remarks.append(r)
for r in range(2 ** n):
    r = list(bin(r)[2:].zfill(n))
    r = [int(i) for i in r[:]]
    cnt = 0
    for i in range(n):
        if r[i] == 1:
            flag = check(r, remarks[i])
            cnt += 1
            if not flag:
                cnt = 0
                break
    cnt_max = max(cnt, cnt_max)
print(cnt_max)

Submission status: Accepted

Solution code:
n = int(input())
data = []
for i in range(n):
    a = int(input())
    d = []
    for j in range(a):
        xy = list(map(int,input().split()))
        d.append(xy)
    data.append(d)
ans = 0
def search(honest):
    if len(honest)==n:
        global ans
        ok = True
        for i in range(n):
            if honest[i]:
                for d in data[i]:
                    if honest[d[0]-1]!=d[1]:
                        ok = False
        if ok: ans = max(ans,honest.count(1))
    else:
        search(honest+[0])
        search(honest+[1])
search([])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())


def make_remark_list(i, r):
    # -1: 不明, 0: 嘘つき, 1: 真実
    people = [-1] * n
    people[i] = 1
    for x, y in r:
        people[x - 1] = y
    return people


def check(x, y):
    new_list = []
    for a, b in zip(x, y):
        a, b = min(a, b), max(a, b)
        if (a, b) == (0, 1):
            return False
        elif (a, b) == (-1, 0):
            new_list.append(0)
        else:
            new_list.append(max(a, b))
    return new_list


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

def max_count(r, cnt, i = 0):
    tmp = r
    for j, r_j in enumerate(remarks):
        if j < i: continue
        if tmp[j] == 0:
            continue
        elif tmp[j] == 1:
            if check(tmp, r_j):
                tmp = check(tmp, r_j)
                cnt += 1
            else:
                cnt = 0
                break
        else:
            tmp[j] = 1
            if check(tmp, r_j):
                cnt_1, tmp_1 = max_count(tmp, cnt, j)
                tmp[j] = 0
                cnt_0, tmp_0 = max_count(tmp, cnt, j)
                if cnt_0 > cnt_1:
                    return cnt_0, tmp_0
                else:
                    return cnt_1, tmp_1
            else:
                tmp[j] = 0
    return cnt, tmp

r = [-1] * n
cnt, r = max_count(r, 0)
print(cnt)

Submission status: Accepted

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

ans = 0
for i in range(1<<N):
    cond = [0]*N
    for j in range(N):
        if 1&(i>>j):  # 右シフトして論理積（bit全探索）
            cond[j] = 1

    mujun = False
    stop_flag = False
    for j in range(N):  # 一人一人判定

        # 正直者の時だけ判定
        # 不親切の場合、特に判定はしない（嘘でも本当でも良いので）
        if cond[j] == 1:
            for k in range(A[j]):  # jの証言を一つずつチェック
                #print(cond[rel[j][k][0]-1])
                #print(rel[j][k][1])
                if cond[relation[j][k][0]-1] != relation[j][k][1]:  # jのk番目の証言をチェック
                    mujun = True
                    stop_flag = True
                    break

        if stop_flag:
            break
    
    if not mujun:
        ans = max(ans, sum(cond))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = []
for i in range(N):
    L.append([])
    A = int(input())
    for j in range(A):
        x,y = map(int, input().split())
        L[i].append([x-1,y])
ans = 0
for i in range(2**N):
    ok = True
    for j in range(N):
        if (i & (1 << j)) != 0:
            for x,y in L[j]:
                truth = (i & (1<<x)) == 0
                claim = y == 0
                if(truth != claim):
                    ok = False
    # set i is possible
    if ok:
        # count bits that are 1
        ans = max(ans, bin(i).count('1'))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = []
for i in range(N):
    L.append([])
    A = int(input())
    for j in range(A):
        x,y = map(int, input().split())
        L[i].append([x-1,y])
def check(i, N):
    flg = True
    for j in range(N):
        if i >> j & 1:
            for x, y in L[j]:
                if (i >> x) & 1 != y:
                    flg = False
                    return flg
    return flg
ans = 0
for i in range(2 ** N):
    if check(i, N):
        ans = max(bin(i).count("1"), ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
path = []
ans = 0
for i in range(N):
    A = int(input())
    path.append([])
    for j in range(A):
        x, y = map(int,input().split())
        x -= 1
        path[-1].append((x, y))
for i in range(1<<N):
    i |= (1<<N)
    judge = True
    for j in range(N):
        if not judge:
            break
        if (1<<j) & i:
            for k in range(len(path[j])):
                if path[j][k][1] != int(bin(i)[-path[j][k][0] - 1]):
                    judge = False
                    break
    if judge:
        if ans < bin(i).count("1") - 1:
            ans = bin(i).count("1") - 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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


def check(i,n):
    flg = True
    for j in range(n):
        if i>>j & 1:
            for x,y in table[j]:
                if (i>>x)&1 != y:
                    flg = False
                    return flg
    return flg
ans = 0
for i in range(2**n):
    if check(i,n):
        ans = max(bin(i).count("1"),ans)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
g = [[-1] * n for _ in range(n)]  # Graph for testimonies.
for i in range(n):
    m = int(input())
    for _ in range(m):
        x, y = [int(z) for z in input().split()]
        x -= 1  # Zero-indexed.
        g[i][x] = y  # Person i says that person x is honest or not.

ans = set()
for bb in range(2 ** n):
    tmp = [0] * n
    possible = True
    for shift in range(n):
        if bb >> shift & 1:
            tmp[shift] = 1  # Assumes person i is honest or not.
    for i, j in enumerate(tmp):
        if j:  # Assumed honest.
            for k in range(n):
                if g[i][k] == -1:
                    # No testimony.
                    continue
                if g[i][k] != tmp[k]:
                    # Contradiction!
                    possible = False
    if possible:
        ans.add(bin(bb).count('1'))

print(max(ans))

Submission status: Accepted

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

for i in range(n):
  a[i]=int(input())
  for j in range(a[i]):
    x[i][j],y[i][j]=map(int,input().split())
    x[i][j]-=1
    
def check(honest):
  for i in range(n):
    if not honest[i]:
      continue
    for j in range(a[i]):
      if y[i][j]==1 and not honest[x[i][j]]:
        return 0
      if y[i][j]==0 and honest[x[i][j]]:
        return 0
  return 1

def dfs(honest):
  if len(honest)==n:
    if check(honest):
      return sum(honest)
    else:
      return 0
  return max(dfs(honest + [1]),
             dfs(honest + [0]))
 
print(dfs([]))

Submission status: Accepted

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

for i in range(n):
  a[i]=int(input())
  for j in range(a[i]):
    x[i][j],y[i][j]=map(int,input().split())
    x[i][j]-=1
    
def check(honest):
  for i in range(n):
    if not honest[i]:
      continue
    for j in range(a[i]):
      if y[i][j]==1 and not honest[x[i][j]]:
        return False
      if y[i][j]==0 and honest[x[i][j]]:
        return False
  return True

def dfs(honest):
  if len(honest)==n:
    if check(honest):
      return sum(honest)
    else:
      return 0
  return max(dfs(honest + [1]),
             dfs(honest + [0]))
 
print(dfs([]))

Submission status: Accepted

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

for i in range(n):
  a[i]=int(input())
  for j in range(a[i]):
    x[i][j],y[i][j]=map(int,input().split())
    x[i][j]-=1
    
def check(honest):
  for i in range(n):
    if not honest[i]:
      continue
    for j in range(a[i]):
      if y[i][j]==1 and not honest[x[i][j]]:
        return False
      if y[i][j]==0 and honest[x[i][j]]:
        return False
  return True

def dfs(honest):
  if len(honest)==n:
    if check(honest):
      return sum(honest)
    else:
      return 0
  return max(dfs(honest + [True]),
             dfs(honest + [False]))
 
print(dfs([]))

Submission status: Accepted

Solution code:
N = int(input())
 
testimony = [[] for _ in range(N)]
 
for i in range(N):
    n = int(input())
    for _ in range(n):
        person, state = map(int, input().split())
        testimony[i].append([person-1, state])

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]:
                if (i>>x)&1 != y:
                    flag = 1
                    break
    if flag == 0:
        honest = max(honest, bin(i)[2:].count('1'))

print(honest)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
from fractions import gcd

NN = 202020
MOD = 10**9+7
INF = float("inf")

n = int(input())
testi = defaultdict(dict)
for i in range(n):
    m = int(input())
    for j in range(m):
        x, y = map(int, input().split())
        testi[i][x-1] = y

# print(testi)
max_honest = 0
for num in range(1 << n):
    valid = True
    for p in range(n):
        if num >> p & 1:
            for k, v in testi[p].items():
                # print(num, p, k, v)
                if v ^ ((num >> k) & 1):
                    valid = False
                    break
        if not valid:
            break

    if valid:
        # print(bin(num)[2:])
        max_honest = max(max_honest, bin(num)[2:].count("1"))

print(max_honest)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from fractions import gcd                    # for Python3.4.3


def main():
    mod = 10000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    

    def check_no_contradict(case):
        for i, person in enumerate(case):
            if person == 1:
                for comment in comments[i]:
                    if case[comment[0]] != comment[1]:
                        return False
        return True


    n = ii()
    comments = [[] for _ in range(n)]
    for i in range(n):
        num = ii()
        for _ in range(num):
            a, b = mi()
            comments[i].append(tuple([a-1, b]))
    
    ans = 0
    for case in product([0, 1], repeat=n):
        if check_no_contradict(case):
            # print(f"case: {case}")
            ans = max(ans, case.count(1))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

N = int(input())
XY = []
for _ in range(N):
    A = int(input())
    tmp = []
    for __ in range(A):
        tmp.append(list(map(int, input().split())))
    XY.append(tmp)
ans = 0


def judge(bit):
    for i in range(N):
        tmp = XY[i]
        if((bit >> i) & 1 == 1):
            for j in tmp:
                #i番目の人の証言
                x = j[0] - 1 #人X
                y = j[1]    #1:正直者である 2:不親切な人

                #証言では正直者だけど、bitでは不親切な人の場合は矛盾

                if(y == 1 and (~bit) & (1 << x)):
                    return False
                #証言では不親切な人だけど、bitでは正直者の場合は矛盾
                if((y == 0) and bit & (1 << x)):
                    return False
    return True


for bit in range(1 << N):
    if(judge(bit)):
        counter = 0
        for i in range(N):
            if(bit & (1 << i)):
                counter += 1
        ans = max(ans, counter)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import itertools

n = int(readline())
s = [[] for i in range(n)]
u = [[] for j in range(n)]
for j in range(n):
    a = int(readline())
    for k in range(a):
        x, y = map(int, readline().split())
        if y == 1:
            s[j].append(x)
        else:
            u[j].append(x)
bit = list(itertools.product([0, 1], repeat=n))
ans = 0
for i in range(2 ** n):
    flag = True
    memo = []
    check_s = []
    check_u = []
    for j in range(n):
        if bit[i][j] == 1:
            memo.append(j + 1)
            check_s += s[j]
            check_u += u[j]
    if len(set(check_u) & set(memo)) == 0:
        for j in range(len(check_s)):
            if (check_s[j]) not in memo:
                flag = False
        if flag:
            ans = max(ans, len(memo))
print(ans)

Submission status: Accepted

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

def is_valid(nn,p):
	if not (nn>>p)&1:
		return True
	for talk in z[p]:
		if not (nn>>(talk[0]-1))&1 == talk[1]:
			return False
	return True	

def num_true(nn):
	sum = 0
	while nn:
		sum += nn%2
		nn //=2
	return sum
ans = 0
for nn in range(1<<n):
	for p in range(n):
		if not is_valid(nn,p):
			break
		if p == n-1:
			ans = max(ans,num_true(nn))
print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline())

testimonies = [[-1 for _ in range(N)] for _ in range(N)]
for i in range(N):
    A = int(sys.stdin.readline())
    for _ in range(A):
        x, y = map(int, sys.stdin.readline().rstrip().split())
        testimonies[i][x-1] = y

def check(honest_persons):
    flag = True
    for i in range(N):
        if honest_persons[i]:
            for j in range(N):
                if testimonies[i][j] == -1:
                    continue
                if testimonies[i][j] != honest_persons[j]:
                    flag = False
                    break
            else:
                continue
            break
    return flag

def main():
    ans = 0
    for i in range(1, 2**N):
        honest_persons = bin(i)[2:].zfill(N)
        honest_persons = list(map(int, list(honest_persons)))

        if check(honest_persons):
            ans = max(ans, sum(honest_persons))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline())

testimonies = [[-1 for _ in range(N)] for _ in range(N)]
for i in range(N):
    A = int(sys.stdin.readline())
    for _ in range(A):
        x, y = map(int, sys.stdin.readline().rstrip().split())
        testimonies[i][x-1] = y

def check(honest_persons):
    flag = True
    for i in range(N):
        if honest_persons[i]:
            for j in range(N):
                if testimonies[i][j] == -1:
                    continue
                if testimonies[i][j] != honest_persons[j]:
                    flag = False
                    break
    return flag

def main():
    ans = 0
    for i in range(1, 2**N):
        honest_persons = bin(i)[2:].zfill(N)
        honest_persons = list(map(int, list(honest_persons)))

        if check(honest_persons):
            ans = max(ans, sum(honest_persons))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
g = list([-1] * n for _ in range(n))
ans = 0


#gをいじる
for i in range(n):
    m = int(input())
    for j in range(m):
        a,x = map(int,input().split())
        a -= 1
        g[i][a] = x
    #
#print(g)
for i in range(2**n):
    d = [0]*n
    for j in range(n):     #n人が正直者、不親切どちらになるかのパターンを作成
        if((i>>j)&1):
            d[n-1-j] = 1
            #d[j] = 1

    #判定
    ok = True
    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 = False
    if ok: ans = max(ans,bin(i).count("1"))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[0]*n
A=[]
for i in  range(0,n):
    l[i]=int(input())
    A.append([[0,0] for i in range(l[i])])
    for j in range(l[i]):
        A[i][j][0],A[i][j][1]=map(int,input().split())
count=0
for i in range(0,2**n):
    count1=0
    for j in range(n):
        if (i>>(n-j-1))&1:
            count1=count1+1
        for m in range(l[j]):
            if  (i>>(n-j-1))&1:
                if A[j][m][1]!=(i>>(n-A[j][m][0]))&1:
                    break
        else:
            continue
        break
    else:
        if count1>count:
            count=count1
print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = [0]*N
testi = []
assume = 2**N-1
ans = 0

for i in range(N):
    A[i] = int(input())
    if A[i] == 0:
        testi.append(-1)
    else:
        testi.append([list(map(int, input().split())) for _ in range(A[i])])

while(assume):
    flag = True
    for i in range(N):
        if assume & (2**i) != 0 and testi[i] != -1:
            for j in testi[i]:
                if j[1] != ((assume & (2**(j[0]-1))) >> (j[0]-1)):
                    flag = False
                    break
        
        if not flag:
            break
    
    if flag:
        tmp = bin(assume).count('1')
        if tmp > ans:
            ans = tmp
    assume -= 1
    

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

bit = '0' + str(n) + 'b'

cnt = 0
for i in range(2 ** n):
    people = [int(peo) for peo in list(format(i, bit))]
    flg = False
    
    for j in range(n):
        if people[j] == 0:
            continue
        for k in range(n):
            if xy[j][k] == -1:
                continue
            if xy[j][k] != people[k]:
                flg = True
                break
        
        if flg:
            break
        
    if flg:
        continue
    else:
        cnt = max(cnt, sum(people))
    
print(cnt)