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: Wrong Answer

Solution code:
#ABC147C bit全探索
#正直者は1, 嘘つきは0で管理する
import itertools
from collections import Counter
N = int(input())
A = []
Y = []
temp = 0
B = []
for i in range(N):
    a = int(input())
    A.append(a)
    X = []
    for i in range(a):
        x = list(map(int, input().split()))
        X.append(x)
    Y.append(X)
#print('A',A)
#print(Y)
flag = True
ans = N
for x in range(2**N):
    honto = [1]*N
    for y in range(N):
        if (x>>y) & 1:
            honto[y]= 0
#    print('honto',honto)
    cnt = 0
    #あるパターンで矛盾しないか？
    B = []
    C = [0]*N
    temp = [0]*N
    for i in range(N):
        if honto[i] == 0:
            cnt +=1
            for j in range(A[i]):
                Y[i][j][1]=abs(Y[i][j][1]-1)
#            print('Y',Y)
#    print('cnt',cnt)
    for j in range(N):
        for k in range(A[j]):
#            print('Y[j][k]',Y[j][k])
            if Y[j][k] not in B:
                B.append(Y[j][k])
                temp[Y[j][k][0]-1] += 1
                if Y[j][k][1]==1 and honto[j]==1:
                    C[j]=1
                elif Y[j][k][1]==1 and honto[j]==0:
                    C[j]=0
                elif Y[j][k][1]==0 and honto[j]==1:
                    C[k]=1
                else:
                    C[j]=0
#                print('B',B)
#                print('C',C)
    temp = sorted(temp, reverse=True)
#    print('temp',temp[0])
    if temp[0]>1:
        flag = False
    else:
        flag = True
#    c = collections.Counter(B)
#    print('ans','cnt','flag',ans,cnt,flag)
    if cnt<=ans and flag == True and honto == C:
#        print(cnt)
        ans = cnt
#        print('honest!')
                
print(N-ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
# A = []
# lst = [list(f"{i:0{N}b}") 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: Wrong Answer

Solution code:
# N = int(input())
# A = []
# lst = [list(f"{i:0{N}b}") 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: Wrong Answer

Solution code:
#147c
#n=int(input())
#n,m=map(int,input().split())
#a=[int(x) for _ in input().split()]

n=int(input())
flg=[True]*n
ans=0
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        if y==0:
            flg[i] = False
    if flg[i]:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

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

    s.append(a)

ans = 0
for i in reversed(range(2 ** N)):
    flag = False
    c = bin(i)[2:]
    c = '0' * (N - len(c)) + c if len(c) < N else c
    for j, l in enumerate(s):
        for k in l:
            if (int(c[j]) and int(c[k[0] - 1]) != k[1]) or (not int(c[j]) and int(c[k[0] - 1]) == k[1]):
                flag = True
                break

        if flag:
            break

    if flag:
        continue
    else:
        ans = sum([int(x) for x in c])
        break

print(ans)

Submission status: Wrong Answer

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

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

    s.append(a)

ans = 0
for i in reversed(range(2 ** N)):
    flag = False
    c = bin(i)[2:]
    c = '0' * (N - len(c)) + c if len(c) < N else c
    for j, l in enumerate(s):
        for k in l:
            if (int(c[j]) and int(c[k[0] - 1]) != k[1]) or (not int(c[j]) and int(c[k[0] - 1]) == k[1]):
                flag = True
                break

        if flag:
            break

    if flag:
        continue
    else:
        ('ok')
        ans = sum([int(x) for x in c])
        break

print(ans)

Submission status: Wrong Answer

Solution code:
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
        else :
            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: Wrong Answer

Solution code:
N = int(input())
xs = [[] for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        xs[i].append((x-1,y))
ans = 0
for b in range(1<<N):
    mujun = False
    for k,z in enumerate(xs):
        for x,y in z:
            if b&(1<<x):
                if y==0:
                     mujun = True
            else:
                if y==1:
                    mujun = True
        if mujun:
            break
    if mujun:
        break
    if not mujun:
        tmp = bin(b).count('1')
        ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read#全部読み込むやつ
readline = sys.stdin.buffer.readline#1行読み込むやつ
readlines = sys.stdin.buffer.readlines#リストで読み込むらしい


import itertools

N = int(readline())

syougen = []
for i in range(N):
    A = int(readline())
    hoge = []
    for i in range(A):
        s = tuple(map(int,readline().split()))
        hoge.append(s)
    syougen.append(hoge)
    
A = 0
for i in list(itertools.product([0,1],repeat = N)):
    cnt = 0
    ans = 0
    for j in range(N):
        if i[j] == 0:
            pass
        else:
            test = True
            for k,m in syougen[j]:
                if i[k-1] == int(m):
                    continue
                else:
                    test = False
            if test:
                ans += 1
            A = max(cnt,ans)
    
        
print(A)

Submission status: Wrong Answer

Solution code:
n = int(input())
table = []
for _ in range(n):
    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):#iはbitでn人それぞれが正直者か嘘つきかのどちらかを表している。
    flg = True
    for j in range(n):
        if i>>j & 1:#右にシフト演算したものの一桁目が1であるとき。iのうち１である桁j=正直者jの意見に関しては吟味する。
            for x,y in table[j]:#ある正直者jの、xに対する評価y
                if (i>>x)&1 != y:#iにおけるxの評価(実際のxの評価)　！＝　jのxに対する評価y
                    flg = False
                    # print(flg)
                    return flg
    # print(flg)
    return flg

# print(table)
ans = 0
for i in reversed(range(2**n)):   #bit全探索
    if check(i,n):
        ans = bin(i).count("1")
        break

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

c = [[-1] * n for _ in range(n)]

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

ans = 0
for i in range(n):
   for j in range(i+1, n):
      if c[i][j] == c[j][i]:
         ans += 1
      elif c[i][j] == 1 and c[j][i] == -1:
         ans += 1
      elif c[j][i] == 1 and c[i][j] == -1:
         ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def judge(bit, N, a_x_y_dict):

    for i in range(N):
        if not (bit & (1 << i)):
            continue

        for values in a_x_y_dict[i]:
            x = values[0]
            y = values[1]

            if y == 1 and not (bit & (1 << x)):
                return False
            if y == 0 and (bit & (1 << x)):
                return False
    return True


N = int(input())

a_x_y_dict = {}
for i in range(N):
    a = int(input())
    x_y_list = []

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

res = 0

for bit in range(1 << N):
    if judge(bit, N, a_x_y_dict):
        count = 0
        for i in range(N):
            if bit & (1 << i):
                count += 1
        res = max(res, count)

print(res)

Submission status: Wrong Answer

Solution code:
def judge(bit, N, a_x_y_dict):

    for i in range(N):
        if not (bit & (1 << i)):
            continue

        for key, values in a_x_y_dict.items():
            for v in values:
                x = v[0]
                y = v[1]

                if y == 1 and not (bit & (1 << x)):
                    return False
                if y == 0 and (bit & (1 << x)):
                    return False

    return True

N = int(input())

a_x_y_dict = {}
for i in range(N):
    a = int(input())
    x_y_list = []

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

res = 0

for bit in range(1 << N):
    if judge(bit, N, a_x_y_dict):
        count = 0
        for i in range(N):
            if bit & (1 << N):
                count += 1
        res = max(res, count)

print(res)

Submission status: Wrong Answer

Solution code:
def f(i):
    global m
    if i == n:
        for j in range(n):
            for k in range(n):
                if G[j][k] == 1:
                    if s[j] + s[k] == 1:
                        return
                elif G[j][k] == 0:
                    if s[j] + s[k] != 1:
                        return
        if m < sum(s):
            m = sum(s)
        return
    f(i + 1)
    s[i] = 1
    f(i + 1)
    s[i] = 0

n = int(input())
G = [[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        G[i][x - 1] = y
s = [0] * n
m = 0
f(0)
print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())

times = n
table = []
for _ in range(times):
    a = int(input())
    temp = []
    for _ in range(a):
        temp.append(list(map(int,input().split())))
    table.append(temp)  # S += [input()] とも書ける
    
def check(i,n):
    honestOrUnkind = [0]*n
    honestOrUnkind[i] = 1
    for item in table[i]:
        membernum = item[0]-1
        honestOrUnkind[membernum] = item[1]
    for idx,hOrU in enumerate(honestOrUnkind):
        if hOrU == 1:
            for item in table[idx]:
                membernum = item[0]-1
                if honestOrUnkind[membernum] != item[1]:
                    return False,honestOrUnkind
                else:
                    honestOrUnkind[membernum] = item[1]
                    continue
        else:
            continue    
    return True,honestOrUnkind

member = [None]*n
ans = 0
for i in range(n):
    flg , memberlist = check(i,n)
    if flg:
        # member[i] = 1
        ans = max(memberlist.count(1),ans)
    else:
        member[i] = 0

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

times = n
table = []
for _ in range(times):
    a = int(input())
    temp = []
    for _ in range(a):
        temp.append(list(map(int,input().split())))
    table.append(temp)  # S += [input()] とも書ける
    
def check(i,n):
    honestOrUnkind = [None]*n
    honestOrUnkind[i] = 1
    for item in table[i]:
        membernum = item[0]-1
        honestOrUnkind[membernum] = item[1]
    for idx,hOrU in enumerate(honestOrUnkind):
        if hOrU == 1:
            for item in table[idx]:
                membernum = item[0]-1
                if honestOrUnkind[membernum] != item[1]:
                    return False,honestOrUnkind
                else:
                    honestOrUnkind[membernum] = item[1]
        else:
            continue    
    return True,honestOrUnkind

member = [None]*n
ans = 0
for i in range(n):
    flg , memberlist = check(i,n)
    if flg:
        member[i] = 1
        ans = max(memberlist.count(1),ans)
    else:
        member[i] = 0
    
ans = max(member.count(1),ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

times = n
table = []
for _ in range(times):
    a = int(input())
    temp = []
    for _ in range(a):
        temp.append(list(map(int,input().split())))
    table.append(temp)  # S += [input()] とも書ける
    
def check(i,n):
    honestOrUnkind = [None]*n
    honestOrUnkind[i] = 1
    for item in table[i]:
        membernum = item[0]-1
        honestOrUnkind[membernum] = item[1]
    for idx,hOrU in enumerate(honestOrUnkind):
        if hOrU == 1:
            for item in table[idx]:
                membernum = item[0]-1
                if honestOrUnkind[membernum] != item[1]:
                    return False,honestOrUnkind
                else:
                    honestOrUnkind[membernum] = item[1]
        else:
            continue    
    return True,honestOrUnkind

member = [None]*n
ans = 0
for i in range(n):
    flg , memberlist = check(i,n)
    if flg:
        ans = max(memberlist.count(1),ans)
    else:
        member[i] = 0
    
ans = max(member.count(1),ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

times = n
table = []
for _ in range(times):
    a = int(input())
    temp = []
    for _ in range(a):
        temp.append(list(map(int,input().split())))
    table.append(temp)  # S += [input()] とも書ける
    
def check(i,n):
    honestOrUnkind = [None]*n
    honestOrUnkind[i] = 1
    for item in table[i]:
        membernum = item[0]-1
        honestOrUnkind[membernum] = item[1]
    for idx,hOrU in enumerate(honestOrUnkind):
        if hOrU is None:
            continue
        elif hOrU == 1:
            for item in table[idx]:
                membernum = item[0]-1
                if honestOrUnkind[membernum] is None:
                    continue
                elif honestOrUnkind[membernum] != item[1]:
                    return False,honestOrUnkind
                else:
                    continue
        else:
            continue    
    return True,honestOrUnkind

member = [None]*n
ans = 0
for i in range(n):
    flg , memberlist = check(i,n)
    if flg:
        ans = max(memberlist.count(1),ans)
    else:
        member[i] = 0
    
ans = max(member.count(1),ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

times = n
table = []
for _ in range(times):
    a = int(input())
    temp = []
    for _ in range(a):
        temp.append(list(map(int,input().split())))
    table.append(temp)  # S += [input()] とも書ける
    # table.append(list(map(int,input().split()))) # 行列の場合
    # 整数として取り込むときは、 input() を int(input()) に置き換える。

# print(table)
def check(i,n):
    honestOrUnkind = [None]*n
    honestOrUnkind[i] = 1
    for item in table[i]:
        membernum = item[0]-1
        honestOrUnkind[membernum] = item[1]
    for idx,hOrU in enumerate(honestOrUnkind):
        if hOrU is None:
            continue
        elif hOrU == 1:
            for item in table[idx]:
                membernum = item[0]-1
                if honestOrUnkind[membernum] is None:
                    continue
                elif honestOrUnkind[membernum] != item[1]:
                    return False,honestOrUnkind
                else:
                    continue
        else:
            continue    
    # for k in range(n):
    #     num = (i+k) % n
    #     # if honestOrUnkind[num] == 1:
    #     for item in table[num]:
    #         membernum = item[0]-1
    #         if honestOrUnkind[membernum] is None:
    #             honestOrUnkind[membernum] = item[1]
    #         elif honestOrUnkind[membernum] != item[1]:
    #             return False
    #         else:
    #             pass
    return True,honestOrUnkind

if n == 1:
    print(1)
    exit()

member = [None]*n
ans = 0
for i in range(n):
    flg , memberlist = check(i,n)
    if flg:
        ans = max(memberlist.count(1),ans)
    else:
        member[i] = 0
    
ans = max(member.count(1),ans)

print(ans)

Submission status: Wrong Answer

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]):
    u,v=map(int,input().split())
    x[i][j]=u-1
    y[i][j]=v
ans=0
for i in range(2**n):
  arr=[0]*n
  cnt=0
  flag=True
  for j in range(n):
    if i>>j&1:
      arr[j]=1
      cnt+=1
  for k in range(n):
    for j in range(a[k]):
      if arr[k]==1:
        if (y[k][j]==1 and arr[x[k][j]]==0) or (y[k][j]==0 and arr[x[k][j]]==1):
          flag=False
      if arr[k]==0:
        if (y[k][j]==1 and arr[x[k][j]]==1) or (y[k][j]==0 and arr[x[k][j]]==0):
          flag=False
  if flag:
    ans=max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[0]*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]):
    u,v=map(int,input().split())
    x[i].append(u-1)
    y[i].append(v)
ans=0
for i in range(2**n):
  arr=[0]*n
  cnt=0
  flag=True
  for j in range(n):
    if i>>j&1:
      arr[j]=1
      cnt+=1
  for k in range(n):
    for j in range(a[k]):
      if arr[k]==1:
        if (y[k][j]==1 and arr[x[k][j]]==0) or (y[k][j]==0 and arr[x[k][j]]==1):
          flag=False
      if arr[k]==0:
        if (y[k][j]==1 and arr[x[k][j]]==1) or (y[k][j]==0 and arr[x[k][j]]==0):
          flag=False
  if flag:
    ans=max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]


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

    #print(xy)
    #print(xy[0])
    #print(len(xy[0]))

    ans = 0
    for i in range(2**n):   # パターンが2のn乗
        flag = False
        count = 0
        for j in range(n):                # n人

            if i >> j & 1 == 1:                         #はなす人が正直者
                for k in range(len(xy[j])):
                    if (i >> xy[j][k][0]-1 & 1) != xy[j][k][1]:        # 違っていたら
                        flag = True
                        break

                if flag == True:
                    break
                    
                else:
                    count += 1

            else:                                      #話す人が不親切
                for k in range(len(xy[j])):
                    if (i >> xy[j][k][0]-1 & 1) == xy[j][k][1]:        # 一致していたら
                        flag = True
                        break

                if flag == True:
                    break

        if flag == False:
            ans = max(ans, count)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
"""dd = [(-1, 0), (0, 1), (1, 0), (0, -1)];
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)];
ddn9 = ddn + [(0, 0)]
for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""

def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]  # WideIntPoint
def ws(): return sys.stdin.readline().split()
def si(): return int(sys.stdin.readline())  # SingleInt
def ss(): return input()
def hi(n): return [si() for _ in range(n)]
def hs(n): return [ss() for _ in range(n)]  # HeightString
def s_list(): return list(input())
def mi(n): return [wi() for _ in range(n)]  # MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]  # NumberGrid
def grid(n): return [s_list() for _ in range(n)]


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

    #print(xy)
    #print(xy[0])
    #print(len(xy[0]))

    ans = 0
    for i in range(2**n):   # パターンが2のn乗
        flag = False
        count = 0
        for j in range(n):                # n人

            if i >> j & 1 == 1:                         #はなす人が正直者
                for k in range(len(xy[j])):
                    if (i >> xy[j][k][0]-1 & 1) != xy[j][k][1]:        # 違っていたら
                        flag = True
                        break

                if flag == True:
                    break

                count += 1

            else:                                      #話す人が不親切
                for k in range(len(xy[j])):
                    if (i >> xy[j][k][0]-1 & 1) == xy[j][k][1]:        # 一致していたら
                        flag = True
                        break

                if flag == True:
                    break

        if flag == False:
            ans = max(ans, count)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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())
    
    l = [[] for _ in range(N)]
    for i in range(N):
        for _ in range(int(input())):
            p, q = map(int, input().split())
            l[i].append((p, q))

    ans = 0
    for i in range(1 << N):
        partial = int_to_list(i, N)

        for j in range(N):
            f = True
            for p, q in l[j]:
                r = p-1
                if q == 0 and r in partial:
                    f = False
                if q == 1 and not r in partial:
                    f = False
        if f:
            ans = max(ans, len(partial))
            
    return ans

print(solve())

Submission status: Wrong Answer

Solution code:
n=int(input())
mark=dict()
for i in range(n):
    A=int(input())
    temp_list=[tuple(map(int,input().split())) for i in range(A)]
    mark[i+1]=temp_list
#正直者を仮定する
#正直者の証言を集める（L）
#Lに矛盾がないか調べる
#print(mark)
ans=0
for i in range(2**n):
    honest_remark=[]
    mujun=[]
    cnt=0
    for j in range(n):
        #j桁目が1の時
        if (i>>j)&1:
            cnt+=1
            for k in mark[j+1]:
                honest_remark+=[k]
            mujun.append((j+1,0))
        else:
            mujun.append((j+1,1))

    if not honest_remark:continue
    #print(honest_remark,mujun)
    honest_remark=set(honest_remark)
    mujun=set(mujun)
    temp=honest_remark&mujun
    if len(temp)==0:
        ans=max(ans,cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
n = int(input())
a = []
xy = [] #xy[i人目][j個目][0: x, 1: y]
for i in range(n):
    a.append(int(input()))
    xy.append([])
    for _ in range(a[i]):
        xy[i].append([int(i) for i in input().split()])
ans = 0
for i in range(n): #i人の正直者
    b = list(combinations(list(range(n)), i))
    for j in range(len(b)): #組み合わせj
        flag = False
        #print(b[j])
        for k in b[j]: #人k
            for l in range(a[k]): #証言l
                if (xy[k][l][0] - 1 in b[j] and xy[k][l][1] != 1) or ((not xy[k][l][0] - 1 in b[j]) and xy[k][l][1] == 1):
                    flag = True
                    break
                #print(xy[k][l][0], xy[k][l][1])
            if flag:
                break
        if not flag:
            #print('YES', j)
            ans = i
print(ans)

Submission status: Wrong Answer

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

ans = 0
r = []
for i in range(N):
  p = [-1]*N
  for row in xy[i]:
    p[row[0]-1] = row[1]
    p[i] = 1
  r.append(p)

for row in r:
  ANS = 0
  ABC = ''
  for i in range(N):
    if row[i] == 1:
      ANS += 1
      for j in range(N):
        if r[i][j] == 0 or r[i][j] == 1:
          if r[i][j] == row[j]:
            continue
          else:
            ABC = 'NO'
            break
    else:
      continue
  if ABC == '':
    ans = max(ans,ANS)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
Y=[]*n
for i in range(n):
    Y.append([-1]*n)
for i in range(n):
    for j in range(int(input())):
        x,y=map(int,input().split())
        Y[i][x-1]=y

ans=0
for c in range(2**n):
    b=bin(c)[2:]
    B=[0]*n
    for i in range(len(b)):
        B[i]=int(b[i])
    a=0
    for i in range(n):
        if B[i]==1:
            for j in range(n):
                if B[j]+Y[i][j]==1:
                    a=1
                    break
        if a>0:
            break
    if a==0:
        ans=max(ans,sum(B))
print(ans)

Submission status: Wrong Answer

Solution code:
import re
n=int(input())
A=[]
for i in range(n):
    B=["."]*n
    for x,y in [list(map(int,input().split())) for k in range(int(input()))]:
        B[x-1]=str(y)
    A.append("".join(B))
    
ans=0
for i in range(2**n):
    num=format(i,"b").zfill(n)
    cnt,flag=0,1
    for k,j in enumerate(num):
        result=re.search(r"".join(A[k]),num)
        if result is not None and j=="1":
            cnt +=1
        else:
            flag=0
            break
    if flag:ans=max(ans,cnt)
print(ans)

Submission status: Wrong Answer

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

def count_honest(bits):
    honest = [(bits >> i) & 1 for i in range(n)]
    for i in range(n):
        for k, v in d[i].items():
            v = v if honest[i] else (v+1)%2
            if honest[k] != v:
                return 0
    return sum(honest)


print(max([count_honest(i) for i in range(2**n)]))

Submission status: Wrong Answer

Solution code:
n = int(input())
d = [dict()] * n
for i in range(n):
  a = int(input())
  for j in range(a):
    x,y = map(int,input().split())
    d[i][x-1] = y
ans = 0

def count_honest(bits):
  count = 0
  vec = [-1] * n
  for i in range(n):
    honest = (bits >> i) | 1
    count += honest
    for k,v in d[i].items():
      v = v if honest else (v+1) % 2
      if vec[k] == -1:
        vec[k] = v
      elif vec[k] != v:
        return 0
  return count
  
for i in range(2**n):
  ans = max(ans, count_honest(i))

print(ans)

Submission status: Wrong Answer

Solution code:
# #!/usr/bin/env python3
# # -*- coding: utf-8 -*-


def main():
    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)]

    max_H = 0
    for i in range(2**N):
        bin = format(i, '015b')[::-1]
        ok = True

        for j in range(N):
            for x, y in XY[j]:
                if bin[j] == '1' and y != int(bin[x - 1]):
                    ok = False
                    break
                else:
                    continue
                break
        if ok:
            H = sum(int(x) for x in bin)
            max_H = max(max_H, H)
        print(max_H)


if __name__ == "__main__":
    main()