Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

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

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

0

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

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



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


Sample output:
2

Submission status: Accepted

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


for i in range(n):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        if y == 1:
            statement[i].append([x-1, True])
        if y == 0:
            statement[i].append([x-1, False])

cnt = 0
for bit in range(2**n):
    honest = []
    for i in range(n):
        if (bit >> i) & 1:
            honest.append(i)
    flag = True
    for j in range(len(statement)):
        if j in honest:
            for k in honest:
                if [j, False] in statement[k]:
                    flag = False
                    break
        else:
            for k in honest:
                if [j, True] in statement[k]:
                    flag = False
                    break
        
        if not flag:
            break  
    if flag:
        cnt = max(cnt, len(honest))
print(cnt)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0
for bit in product([0, 1], repeat=n):
    for i, liar in enumerate(bit):
        if liar and any(bit[x - 1] != y for x, y in xy[i]):
            break
    else:
        ans = max(ans, sum(bit))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [0 for n in range(N)]
XY = [0 for n in range(N)]
count_max = 0

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

for i in range(2 ** N):
  op = [0]*N
  for j in range(N):  # ポイント１
    if ((i >> j) & 1):
      op[N-1-j] = 1
      
  flag = True
  
  for k in range(len(op)):
    if op[k] == 1:
      for l in range(A[k]):
        if XY[k][l][1] != op[XY[k][l][0]-1]:
          flag = False
        
  if flag:
    if sum(op) > count_max:
      count_max = sum(op)

print(count_max)

Submission status: Accepted

Solution code:
N = int(input())

syougen = [ [] for _ in range(N) ]
for i in range(N):
    num = int(input())
    for j in range(num):
        x, y = map(int, input().split())
        syougen[i].append([x, y])

#print(syougen)
ans = 0
for bit in range(1 << N):
    break_flag = 0
    for i in range(N):
        if (bit >> i) & 1:
            for j in range(len(syougen[i])):
                if ((bit>>(syougen[i][j][0]-1))&1) != syougen[i][j][1]:
                    break_flag = 1
                    break
            if break_flag == 1:
                break
        if i == N-1:
            ans = max(ans, bin(bit).count("1"))
print(ans)

Submission status: Accepted

Solution code:
import copy
N = int(input())
testimony = []
for n in range(N):
    A = int(input())
    testimony.append({})
    for a in range(A):
        x, y = map(int, input().split())
        testimony[n][x - 1] = y    

def judge(truthy):
    answer = True
    for i in range(len(truthy)):
        if truthy[i] == 1:
            for t in testimony[i].keys():
                if truthy[t] != testimony[i][t]:
                    answer = False
                    break
        if not answer:
            break
    # print(answer, truthy)
    return 0 if not answer else truthy.count(1)

def dfs(truthy, depth):
    if N == depth:
        return judge(truthy)
    truth = copy.copy(truthy)
    truth.append(1)
    t = dfs(truth, depth + 1)
    false = copy.copy(truthy)
    false.append(0)
    f = dfs(false, depth + 1)
    return max(t, f)

print(dfs([], 0))

Submission status: Accepted

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

answer = 0
for index in range(2 ** n):
    honests = [0 for _ in range(n)]
    for shift in range(n):
        if (index >> shift) & 1:
            honests[shift] = 1
    ok = True
    for idx1 in range(n):
        if honests[idx1]:
            for idx2 in range(n):
                if graph[idx1][idx2] == -1:
                    continue
                if graph[idx1][idx2] != honests[idx2]:
                    ok = False
    if ok:
        answer = max(answer, honests.count(1))

print(answer)

Submission status: Accepted

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

for i in range(2**N):
    Z=[0]*N
    flag=0
    for j in range(N):
        if ((i>>j)&1):
            Z[j]=1
    for k in range(N):
        for l in range(A[k]):
            if Z[k]==1:
                if Z[xy[k][l][0]-1]!=xy[k][l][1]:
                    flag=1
    if flag==0:
        mx=max(mx,Z.count(1))
print(mx)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    cnt = 0
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            cnt += 1
            for x, y in xyl[j]:
                x -= 1
                if (i >> x) & 1 != y:
                    flag = False
    if flag:
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

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

    ans = 0
    for bit in range(1 << N):
        ok = True
        for i in range(N):
            if bit >> i & 1:
                for (x, y) in evdi[i]:
                    if y == 1 and not bit >> x & 1:
                        ok = False
                        break
                    if y == 0 and bit >> x & 1:
                        ok = False
                        break
        cnt = bin(bit).count("1")
        if ok:
            ans = max(cnt, ans)
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

def resolve():
    N = int(input())
    evdi = [[] for _ in range(N)]
    for i in range(N):
        cnt = int(input())
        for _ in range(cnt):
            x, y = map(int, input().split())
            x -= 1
            evdi[i].append((x, y))

    ans = 0
    for bit in range(1 << N):
        ok = True
        for i in range(N):
            if bit >> i & 1:
                for (x, y) in evdi[i]:
                    if y == 1 and not bit >> x & 1:
                        ok = False
                        break
                    if y == 0 and bit >> x & 1:
                        ok = False
                        break
        cnt = bin(bit).count("1")
        if ok:
            ans = max(cnt, ans)
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n=int(input())
say=[]
for i  in range(n):
    qq=[]
    for i in range(int(input())):
        qq.append(list(map(int,input().split())))
    say.append(qq)
ans=0
for bit in range(1<<n):
    plate=0
    L=[(bit>>i)&1 for i in range(n)]
    for i in range(n):
        if L[i]==0:continue
        for l in say[i]:
            if  L[l[0]-1] != l[1]:
                plate=1;break
        if plate:break
    else:
        ans=max(ans,sum(L))
print(ans)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=[0]*N
    xy=[]
    for i in range(N):
        A[i]=I()
        temp=[]
        for _ in range(A[i]):
            x,y=MI()
            x-=1
            temp.append((x,y))
        xy.append(temp)
        
    import itertools
    ans=0
    
    for ite in itertools.product([0,1], repeat=N):
        # ite[i]=1なら正直者，
        flag=1
        for i in range(N):
            if flag==0:
                break
            if ite[i]==1:
                for x,y in xy[i]:
                    if ite[x]!=y:
                        flag=0
                        break
        if flag:
            ans=max(ans,sum(ite))
            
    print(ans)
            

main()

Submission status: Accepted

Solution code:
n=int(input())
xy=[[[]] for _ in range(n)]
for i in range(n):
    a=int(input())
    xy[i]=[list(map(int,input().split())) for _ in range(a)]
ans=0
for i in range(2**n):
    tmp=[0]*n
    flag1=True
    for j in range(n):
        if (i>>j)&1:
            tmp[j]=1
    for k in range(n):
        flag2=True
        if tmp[k]==1:
            for x,y in xy[k]:
                if tmp[x-1]!=y:
                    flag1=False
                    flag2=False
                    break
        if not flag2:
            break
    if flag1:
        ans=max(ans,sum(tmp))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XY_list = [[] for _ in range(N)]
for i in range(N):
    num = int(input())
    for j in range(num):
        person, state = map(int, input().split())
        XY_list[i].append([person - 1, state])
ans = 0
for i in range(1 << N):
    bool = True
    for j in range(N):
        if (i >> j) & 1 == 1:
            for person, state in XY_list[j]:
                if (i >> person) & 1 != state:
                    bool = False
                    break

    if bool:
        ans = max(ans, bin(i)[2:].count("1"))
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
numbers=[]
for _ in range(N):
    A=int(input())
    number=[]
    for _ in range(A):
        x,y=map(int,input().split())
        number.append([x,y])
    numbers.append(number)
answers=[]
for i in range(2**N):
    number=[]
    for j in range(N):
        if ((i>>j)&1):
            number.append(j+1)
    answers.append(number)
del answers[0]
ans=0
for answer in answers:
    kouho=[]
    num=0
    flag=0
    for a in answer:
        kouho+=numbers[a-1]
    for k in kouho:
        if k[1]==1 and k[0] not in answer:
            flag=1
            break
        elif k[1]==0 and k[0] in answer:
            flag=1
            break
    if flag==0:
        num=len(answer)
    ans=max(ans,num)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
testimonies=[]

for i in range(N):
  A=int(input())
  testimony=[]
  for j in range(A):
    testimony.append(list(map(int,input().split())))
    testimony[-1][0]-=1
  testimonies.append(testimony)

ans=0
for i in range(2**N):
  isContradiction=False
  for j in range(N):
    if not i&1<<j:continue
    for x,y in testimonies[j]:
      if i&1<<x:x=1
      else:x=0
      if not x==y:
        isContradiction=True
        break
  if not isContradiction:
    ans=max(ans,bin(i).count("1"))
print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    N = int(input())
    n_x_y = {}
    for n in range(N):
        A = int(input())
        x_y = {}
        for _ in range(A):
            x, y = map(int, input().split())
            x_y[x-1] = y
        n_x_y[n] = x_y

    ans = 0
    for flags in itertools.product([1, 0], repeat=N):
        sat = True
        for n, flag in enumerate(flags):
            if flag == 0:
                continue
            for x, y in n_x_y[n].items():
                if (y == 1 and flags[x] == 0) or (y == 0 and flags[x] == 1):
                    sat = False
                    break
            if sat is False:
                break
        if sat is True and sum(flags) > ans:
            ans = sum(flags)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def digitSum(n):
    s = str(bin(n))
    s = s[2:]
    array = list(map(int, s))
    return sum(array)
N = int(input())
A = []
X = []
Y = []
res = 0
for i in range(N):
    a = int(input())
    A.append(a)
    X_temp = []
    Y_temp = []
    for j in range(a):
        x,y = map(int,input().split())
        X_temp.append(x)
        Y_temp.append(y)
    X.append(X_temp)
    Y.append(Y_temp)
for i in range(1 << N):
    judge = True
    for j in range(N):
        if (i >> j) & 1:#もしAjが正直者だったら
            for k in range(A[j]):
                if (i >> X[j][k]-1) & 1 != Y[j][k]:
                    judge = False
        """else:#もしAjが不親切ものだったら。不親切者も正しいことをいうこともある。
            for k in range(A[j]):#
                if (i >> X[j][k]-1) & 1 == Y[j][k]:
                    judge = False"""
    if judge:
        res = max(res,digitSum(i))
print(res)

Submission status: Accepted

Solution code:
n = int(input())

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

ans = 0
for i in range(2**n):
    lst = [0 for _ in range(n)]
    for j in range(n):
        if (i >> j) & 1:
            lst[j] = 1
    
    flag = True
    for j in range(n):
        if lst[j] == 1:
            for x, y in xy[j]:
                if lst[x - 1] != y:
                    flag = False
                    break
            else:
                continue
            break

    if flag:
        ans = max(ans, sum(lst))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
Dup = []

for i in range(n):
    a = int(input())
    Dup.append([])
    for j in range(a):
        x,y = map(int, input().split())
        Dup[-1].append((x-1,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 Dup[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())
all_h_or_u = []

#証言リスト
for i in range(n) :
    x = int(input())
    h_or_u = []
    for j in range(x) :
        h_or_u.append(list(map(int, input().split())))
    
    for k in range(x) :
        h_or_u[k][0] -= 1
    
    all_h_or_u.append(h_or_u)
    
#真偽パターン 
all_t_or_f = []
for a in range(2 ** n) :
    t_or_f = []
    for b in range(len(bin(2**n)) - 3) :
        if (a >> b) & 1 :
            t_or_f.append(1)
        else :
            t_or_f.append(0)
        
    all_t_or_f.append(t_or_f)

#真偽パターンに応じた証言の検証
max_cnt = 0
for c in all_t_or_f :
    cnt = 0
    for d in range(n) :
        if c[d] == 1 :
            for e in all_h_or_u[d] :
                if c[e[0]] != e[1] :
                    cnt += 1
    
    if cnt == 0 :
        max_cnt = max(max_cnt, sum(c))
            
print(max_cnt)

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())

test = []

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

ans = 0

for i in product(range(2), repeat=n):
  flag = True
  for j in range(n):
    if i[j] == 1:
      for s in test[j]:
        if i[s[0]-1] != s[1]:
          flag = False 
          break
  if flag == True:
    cnt = i.count(1)
    if cnt > ans:
      ans = cnt

print(ans)

Submission status: Accepted

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

ans = 0

for i in range(2**N):
    b = format(i, "0" + str(N) + "b")
    t = 0
    f = 0
    for j in range(N):
        if b[j] == "1":
            t += 1
            for k in xy[j]:
                if str(k[1]) != b[k[0]-1]:
                    f = 1
                    break
    if f == 0:
        ans = max(ans, t)
        #print(b)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
x = [[0] * (N-1) for _ in range(N)]
y = [[0] * (N-1) for _ in range(N)]
A = [0] * N
for i in range(N):
  A[i] = int(input())
  for j in range(A[i]):
    x[i][j], y[i][j] = list(map(int, input().split()))
n = 2 ** N
Flag = 0
ans = 0
while(n < 2 ** (N+1)):
  Flag = 0
  for i in range(N):
    if(int(bin(n)[i + 3]) == 1):
      for j in range(A[i]):
        if(y[i][j] != int(bin(n)[x[i][j] + 2])):
          Flag = 1
          break
    if(Flag == 1):
      break
  else:
    ans = max(ans, sum(list(map(int,bin(n)[3:]))))
  n += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
b = []

for i in range(N):
  a = [-1] * N
  for j in range(int(input())):
    temp = list(map(int, input().split()))
    a[temp[0]-1] = temp[1]
  b.append(a)
  
ans = 0

for i in range(2 ** N):
  temp = list(map(int, list(str(format(i, 'b')).zfill(N))))
  num = 0
  for j, var in enumerate(temp):
    if var == 1:
      for k, var2 in enumerate(b[j]):
        if var2 == -1:
          pass
        elif var2 != temp[k]:
          num = -1
          break
      if num == -1:
        break
      else:
        num += 1
  if num > ans:
    ans = num
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n = int(input())

memo = [[] for _ in range(n)]

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

ans = 0
for a in product([0,1], repeat=n):
    REAL = True
    for i in range(n):
        if a[i] == 1:
            for x, y in memo[i]:
                if a[x] != y:
                    REAL = False
                    break
        if REAL == False:
            break

    if REAL:
        ans = max(ans, sum(a))

print(ans)

Submission status: Accepted

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

maxH=0
for mask_i in range(1<<N):
  
  H=[0]*(N+1)
  for n in range(N):
    if mask_i>>n&1:
      H[n+1]=1
  #print(H[1:])
  
  ok=True
  for n in range(1,N+1):
    if H[n]==1:
      for x,y in XY[n]:
        if H[x]!=y:
          ok=False
          break
  if ok:
    maxH=max(maxH,sum(H))

print(maxH)

Submission status: Accepted

Solution code:
n = int(input())

remark_list = [[] for _ in range(n)] # -1:言及なし, 0:不親切, 1：親切
for i in range(n):
    a = int(input())
    for j in range(a):
        remark_list[i].append(list(map(int, input().split())))

ans = 0
for i in range(2**n):
    state = [-1]*n
    is_ok = True
    ok_num = 0
    for j in range(n):
        if ((i >> j) & 1):
            if state[j] != 0:
                state[j] = 1
            else:
                is_ok = False
            remark = remark_list[j]
            ok_num += 1
            for r in remark:
                if state[r[0]-1] == -1:
                    state[r[0]-1] = r[1]
                elif state[r[0]-1] != r[1]:
                    is_ok = False
                    break
        else:
            if state[j] != 1:
                state[j] = 0
            else:
                is_ok = False
    if is_ok:
        ans = max(ans, ok_num)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
Big_lis = []
A = []

for i in range(n):
    lis = []
    a = int(input())
    A.append(a)
    for j in range(a):
        x, y = map(int, input().split())
        lis.append((x, y))
    Big_lis.append(lis)
ANS = 0

for i in range(2 ** n):
    check = bin(i)[2:]
    check = '0' * (n - len(check)) + check
    ans = check.count('1')
    for j in range(n):
        if i >> j & 1:
            for k in range(A[j]):
                if str(check[n - Big_lis[j][k][0]]) != str(Big_lis[j][k][1]):
                    ans = 0
    ANS = max(ANS, ans)
print(ANS)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
As = []
xys = []
for _ in range(N):
    a = int(input())
    As.append(a)
    xys.append([tuple(map(int, input().split())) for _ in range(a)])


ans = -1
for is_shoziki in itertools.product([1, 0], repeat=N):
    n = sum(is_shoziki)
    if n <= ans:
        continue
    flg = True
    for i in range(N):
        if not flg:
            break
        if is_shoziki[i] == 0:
            continue
        for x, y in xys[i]:
            if is_shoziki[x - 1] != y:
                flg = False
                break
    if flg:
        ans = n

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

W = [[-1]*N for _ in range(N)]
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = [int(z) for z in input().split()]
        x -= 1
        W[i][x] = y

M = 0
for b in range(2**N):

    d = [0] * N
    for i in range(N):
        if (b >> i) & 1:
            d[i] = 1
    
    ok = True
    for i in range(N):
        if d[i] == 1:
            for j in range(N):
                if W[i][j] == -1:
                    continue
                if W[i][j] != d[j]:
                    ok =False

    if ok == True:
        M = max(M, sum(d))

print(M)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
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])
ans = 0 
for tf_s in itertools.product(range(2), repeat = n):
    for i in range(n):
        if tf_s[i] == 0:
            continue
        for x, y in tes[i]:
            if tf_s[x] != y:
                break
        else:
            continue
        break
    else:
        ans = max(ans, tf_s.count(1))
print(ans)

Submission status: Accepted

Solution code:
# 全探索

n=int(input())

class People:
    def __init__(self):
        self.type=None

peoples=[People() for i in range(n+1)]

def change_10to2(i):
    ans=format(i, '#0' + str(n + 3) + 'b')[2:]
    return ans

def set_people_type(binary_list,peoples):
    for i,people in enumerate(peoples):
        if i!=0:
            people.type=binary_list[i]

def get_statement():
    shougen={}
    for i in range(1,n+1):
        ai=int(input())
        ans=[]
        for j in range(ai):
            kumi=[int(k) for k in input().split()]
            ans.append(kumi)
        shougen[str(i)]=ans
    return shougen

shougens=get_statement()

def shougen_dicide(peoples,shougens):
    for i in range(1,n+1):
        shougen=shougens[str(i)]
        for shou in shougen:
            people,type=shou
            people=int(people)
            type=str(type)
            # 正直者のとき
            if peoples[i].type=="1":
                if peoples[people].type!=type:
                    return False

            # #嘘つきのとき
            # else:
            #     if peoples[people].type==type:
            #         return False
    return True



ans=0
for i in range(2**n):
    binary_list=change_10to2(i)
    set_people_type(binary_list,peoples)
    if shougen_dicide(peoples,shougens):
        ans=max(ans,binary_list.count("1"))
print(ans)

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(list(map(int, input().split())))
ans = 0
for s in range(1 << N):
  #1:TRUE, 0:UNKNOWN
  state = [(s >> j) & 1 for j in range(N)]
  f = 0
  for i in range(N):
    if state[i] == 0:
      continue
    for x in X[i]:
      if state[x[0]-1] != x[1]:
        f = 1
        break
    if f == 1:
      break
  if f == 0:
    ans = max(ans, sum(state))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
COM=[[] for i in range(n)]

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

ans=0
for i in range(2**n):
    sco=bin(i).count("1")
    if sco<=ans:
        continue
    end=False
    #print(i)
    for q in range(n):
        if (i>>q)&1==1:
            for que in COM[q]:
                #print(que,que[0],(i>>que[0])&1,que[1])
                if (i>>que[0])&1!=que[1]:
                    end=True
                    break
            if end:
                break
    if end:
        continue
    #print("!")
    ans=sco
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
xy = [[] for i in range(n)]
for i in range(n):
    a.append(int(input()))
    for j in range(a[i]):
        xy[i].append(list(map(int, input().split())))
ans = 0
for i in range(2**n):
    tf = [False for j in range(n)]
    for j in range(n):
        if (i>>j)&1:
            tf[j] = True
    flag = False
    for j in range(n):
        for k in range(a[j]):
            if tf[j]:
                if xy[j][k][1] != tf[xy[j][k][0]-1]:
                    flag = True
                    break
        if flag:
            break
    else:
        ans = max(ans, tf.count(True))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
shougen = [[] for _ in range(N)]
for k in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        x -= 1
        shougen[k].append((x, y))
ans = 0
bit = 2**N-1
while bit:
    person = [-1 for _ in range(N)]
    b = bit
    count = 0
    while count < N:
        person[count] = b & 1
        b >>= 1
        count += 1
    flag = True
    for k in range(N):
        if person[k] == 1:
            for x, y in shougen[k]:
                if person[x] != y:
                    flag = False
                    break
            else:
                continue
            break
    if flag:
        ans = max(ans, sum(person))
    bit -= 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
lis=[]
for _ in range(n):
    a=int(input())
    l.append(a)

    li=[]
    for _ in range(a):
        c,d=map(int,input().split())
        li.append([c,d])
    lis.append(li)

ans=-1
for i in range(2**n-1,-1,-1):
    mark=bin(i)[2:]
    mark=(n-len(mark))*'0'+mark
    s=0
    record=[-1]*n
    f=1
    for j in range(n):
        for k in range(l[j]):
            number=lis[j][k][0]-1
            hou=lis[j][k][1]
            if int(mark[j])==1:
                if record[number]==-1:
                    record[number]=hou
                elif record[number]!=hou:f=0
            if f==0:break
        if f == 0: break

    if f==1:
        F=True
        for i in range(n):
            if record[i]!=-1:
                if record[i]!=int(mark[i]):
                    F=False
                    break
        if F==True:
            print(mark.count('1'))
            exit()

Submission status: Accepted

Solution code:
N=int(input())
testimony=[[-1]*N for i in range(N)]
count=0
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        testimony[i][x-1]=y
for i in range(1<<N):
    honest=[0]*N
    for j in range(N):
        if (i>>j)&1:
            honest[j]=1
    flag=True
    for j in range(N):
        if honest[j]:
            for k in range(N):
                if testimony[j][k]==-1:
                    continue
                if testimony[j][k]!=honest[k]:
                    flag=False
    if flag:
        count=max(count,honest.count(1))
print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = []
for _ in range(N):
    a = int(input())
    b = []
    for _ in range(a):
        b.append(list(map(int, input().split())))
    A.append(b)
# 証言リスト A[i人目][j個目の証言] -> [誰が, bit(1は正、0は誤)]

# bitが1であれば正しい証言、0であれば間違った証言とする
# 正しい証言だけ確認して、[i, 1]と証言した i も1かどうか、[j,0]と証言したjが0かどうか



def F(i):
    cnt = 0
    B = [-1]*N                #B = [-1,-1,-1]
    r = 0
    for j in range(N):    # i=1,  j=0,1,2
        if (i>>j)&1:         # 001 ->  1,0,0  j=0
            r += 1               # r = 1    
            if B[j] == 0:     #B[0] == -1  
                return 0
            B[j]=1              # B = [1,-1,-1]   
            for p,q in A[j]: # A[0] = [[2, 1], [3, 0]]   
                if q == 0:
                    if B[p-1]==1:  # B[2] == -1
                        return 0
                    B[p-1] = 0  # B = [1,1,0]
                else:
                    if B[p-1]==0:  # B[1] == -1
                        return 0
                    B[p-1] = 1      # B = [1,1,-1]
            else:
                cnt += 1          # cnt = 1
        else:         # j=1
            if B[j]==1:       #B[1] ==1
                return 0
            B[j]=0
            
    if cnt == r:
        return cnt

ans = 0
for i in range(1<<N):
    ans = max(ans,F(i))
print(ans)

Submission status: Accepted

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

ans=[]
for i in range(2**N):
    Bit = [1]*N
    for j in range(N):
        if (i >> j) & 1:
            Bit[j] = 0
    i=0
    no=0
    while i<N:
        if Bit[i]==1:
            for x,y in A[i]:
                if Bit[x-1]!=y:
                    no=1
        i+=1
    if no:
        ans.append(0)
    else:
        ans.append(Bit.count(1))

print(max(ans))

Submission status: Accepted

Solution code:
def main():
	N = int(input())
	A = [[] for i in range(N)]
	# A[i][j] -> i-th person's testimony of person's honesty (j makes no sense)
	for i in range(N):
		a = int(input())
		for j in range(a):
			x, y = [int(b) for b in input().split(" ")]
			A[i].append([x - 1, str(y)])

	cand = []
	for i in range(2 ** N):
		honest_flag = True
		bit = list(pad_zero(format(i, 'b'), N))
		honests = [int(p) for p, q in enumerate(bit) if q == "1"]
		for honest in honests:
			w = A[honest]
			for k in range(len(w)):
				if w[k][1] != bit[w[k][0]]:
					honest_flag = False
		if honest_flag:
			cand.append(len(honests))

	print(max(cand))


def pad_zero(s, n):
	s = str(s)
	return ("0" * n + s)[-n:]

main()