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:

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

ans=0
for i in range(2**n):
    s=bin(i)[2:].zfill(n)  #[2:]はbinにしたときに最初につく0bをのぞく．zfillはn桁の0埋め．
    f=True
    for j,k in enumerate(lst):  #kは証言，jはそれを言った人の番号
        for x,y in k:   #xは人番号なので，インデックスのときは-1する
            if s[x-1]!=str(y) and s[j]=='1':    #仮定したsとjの人の証言を照らし合わせる．jの人が不親切という仮定の時，証言に意味はないので無視．
                                                #仮定と証言で一致しないものがあったとき，flagを消す．
                f=False
        if f:                                   #全ての証言と照らし合わせてもokのとき，仮定したsは正しい．
            ans=max(ans,s.count('1'))   #ansを更新
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-

def solve():
    # 真偽不明の意見は無視して、正直者の意見のみをうまいこと数えればよい
    N = int(input())
    As = []
    for n in range(N):
        A = int(input())
        XYs = []
        for a in range(A):
            x, y = list(map(int, input().split()))
            XYs.append((x-1, y))
        As.append(XYs)

    ans = 0
    for i in range(N):
        is_next = False
        # iが正直者だと仮定する
        honests = [None for _ in range(N)]
        honests[i] = 1

        que = []
        for x, y in As[i]:
            honests[x] = y
            if y == 1:
                que.append(x)

        while len(que) != 0:
            j = que.pop(-1)
            for x, y in As[j]:
                if honests[x] == None:
                    honests[x] = y
                    if y == 1:
                        que.append(x)
                else:
                    # 矛盾を調べる
                    if honests[x] != y:
                        is_next = True
                        break
            if is_next:
                break
        if is_next:
            continue

        # 正直者の数を数える
        ret = 0
        for j in honests:
            if j == 1:
                ret += 1

        # 残ったやつを調べる
        for j in range(N):
            if honests[j] != None: continue

            is_honest = True
            for x, y in As[j]:
                if honests[x] != y:
                    is_honest = False
            if is_honest:
                ret += 1
        ans = max(ans, ret)

    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-

def solve():
    # 真偽不明の意見は無視して、正直者の意見のみをうまいこと数えればよい
    N = int(input())
    As = []
    for n in range(N):
        A = int(input())
        XYs = []
        for a in range(A):
            x, y = list(map(int, input().split()))
            XYs.append((x-1, y))
        As.append(XYs)

    ans = 0
    for i in range(N):
        is_next = False
        # iが正直者だと仮定する
        honests = [None for _ in range(N)]
        honests[i] = 1

        que = []
        for x, y in As[i]:
            honests[x] = y
            if y == 1:
                que.append(x)

        while len(que) != 0:
            j = que.pop(-1)
            for x, y in As[j]:
                if honests[x] == None:
                    honests[x] = y
                    que.append(x)
                else:
                    # 矛盾を調べる
                    if honests[x] != y:
                        is_next = True
                        break
            if is_next:
                break
        if is_next:
            continue

        # 正直者の数を数える
        ret = 0
        for j in honests:
            if j == 1:
                ret += 1

        # 残ったやつを調べる
        for j in range(N):
            if i == j: continue
            if honests[j] != None: continue

            is_honest = True
            for x, y in As[j]:
                if honests[y] != x:
                    is_honest = False
            if is_honest:
                ret += 1

        ans = max(ans, ret)

    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-

def solve():
    # 真偽不明の意見は無視して、正直者の意見のみをうまいこと数えればよい
    N = int(input())
    As = []
    for n in range(N):
        A = int(input())
        XYs = []
        for a in range(A):
            x, y = list(map(int, input().split()))
            XYs.append((x-1, y))
        As.append(XYs)

    ans = 0
    for i in range(N):
        is_next = False
        # iが正直者だと仮定する
        honests = [None for _ in range(N)]
        honests[i] = 1

        que = []
        for x, y in As[i]:
            honests[x] = y
            if y == 1:
                que.append(x)

        while len(que) != 0:
            j = que.pop(-1)
            for x, y in As[j]:
                if honests[x] == None:
                    honests[x] = y
                    que.append(x)
                else:
                    # 矛盾を調べる
                    if honests[x] != y:
                        is_next = True
                        break
            if is_next:
                break
        if is_next:
            continue

        # 正直者の数を数える
        ret = 0
        for j in honests:
            if j == 1:
                ret += 1

        # 残ったやつを調べる
        # for j in range(N):
        #     if i == j: continue
        #     if honests[j] != None: continue

        #     is_honest = True
        #     for x, y in As[j]:
        #         if honests[y] != x:
        #             is_honest = False
        #     if is_honest:
        #         ret += 1

        ans = max(ans, ret)

    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def check(pat):
  honest = [0]*N
  for i in pat:
    honest[i] = 1
    
  for i in range(N):
    n = len(x[i])
    if honest[i] == 0:
      if i in pat:
        return -1
      else:
        continue
    for j in range(n):
      y = x[i][j]
      honest[y[0]] = y[1]
    
  for i in range(N):
    n = len(x[i])
    if honest[i] == 0:
      continue
    for j in range(n):
      y = x[i][j]
      if honest[y[0]] != y[1]:
        return -1
    
  return len(pat)

N = int(input())
x = [0]*N
for i in range(N):
  A = int(input())
  x[i] = []
  for j in range(A):
    y1,y2 = map(int,input().split())
    x[i].append((y1-1,y2))
max_honest = 0
l = [i for i in range(N)]
n = len(l)
for i in range(2 ** N):
    pat = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            pat.append(l[j])  # フラグが立っていたら bag に果物を詰める
    max_honest = max(max_honest,check(pat))
print(max_honest)

Submission status: Wrong Answer

Solution code:
def check(pat):
  honest = [-1]*N
  for i in pat:
    honest[i] = 1
  for i in range(N):
    n = len(x[i])
    for j in range(n):
      y = x[i][j]
      if i in pat:
        if honest[y[0]] > -1 and honest[y[0]] != y[1]:
          return -1
        honest[y[0]] = y[1]

  return len(pat)

N = int(input())
x = [0]*N
for i in range(N):
  A = int(input())
  x[i] = []
  for j in range(A):
    y1,y2 = map(int,input().split())
    x[i].append((y1-1,y2))
max_honest = 0
l = [i for i in range(N)]
n = len(l)
for i in range(2 ** N):
    pat = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            pat.append(l[j])  # フラグが立っていたら bag に果物を詰める
    max_honest = max(max_honest,check(pat))
print(max_honest)

Submission status: Wrong Answer

Solution code:
def check(pat):
  honest = [-1]*N
  for i in pat:
    honest[i] = 1
  for i in range(N):
    n = len(x[i])
    for j in range(n):
      y = x[i][j]
      if i in pat:
        if honest[y[0]] > -1 and honest[y[0]] != y[1]:
          return -1
        honest[y[0]] = y[1]
      else:
        if honest[y[0]] > -1 and honest[y[0]] == y[1]:
          return -1
        honest[y[0]] = int(not y[1])
        
  return len(pat)

N = int(input())
x = [0]*N
for i in range(N):
  A = int(input())
  x[i] = []
  for j in range(A):
    y1,y2 = map(int,input().split())
    x[i].append((y1-1,y2))
max_honest = 0
l = [i for i in range(N)]
n = len(l)
for i in range(2 ** N):
    pat = []
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            pat.append(l[j])  # フラグが立っていたら bag に果物を詰める
    max_honest = max(max_honest,check(pat))
print(max_honest)

Submission status: Wrong Answer

Solution code:
N = int(input())

As = [[] for _ in range(N)]

for i in range(N):
    n = int(input())
    for j in range(n):
        person, state = map(int, input().split())
        As[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 As[j]:
                if (j>>x) & 1 != y:  # 人jは正直だが矛盾を発見
                    flag = 1
                    break
    if flag == 0:
        # 1の数をカウントし最大となるものを選択
        honest = max(honest, bin(i)[2:].count('1'))

print(honest)

Submission status: Wrong Answer

Solution code:
N = int(input())

As = [[] for _ in range(N)]

for i in range(N):
    n = int(input())
    for j in range(n):
        A = [int(k) for k in input().split()]
        person, state = A[0], A[1]
        As[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 As[j]:
                if (j>>x) & 1 != y:  # 人jは正直だが矛盾を発見
                    flag = 1
                    break
    if flag == 0:
        # 1の数をカウントし最大となるものを選択
        honest = max(honest, bin(i)[2:].count('1'))

print(honest)

Submission status: Wrong Answer

Solution code:
N = int(input())

As = [[] for _ in range(N)]

for i in range(N):
    n = int(input())
    for j in range(n):
        person, state = [int(k) for k in input().split()]
        As[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 As[j]:
                if (j>>x) & 1 != y:  # 人jは正直だが矛盾を発見
                    flag = 1
                    break
    if flag == 0:
        # 1の数をカウントし最大となるものを選択
        honest = max(honest, bin(i)[2:].count('1'))

print(honest)

Submission status: Wrong Answer

Solution code:
N = int(input())

As = [[] for _ in range(N)]

for i in range(N):
  n = int(input())
  for j in range(n):
    person, state = [int(k) for k in input().split()]
    As[i].append([person-1, state])
        
honest = 0
for i in range(2**N):
  flag = 0
  for j in range(N):
    if (i>>j) & 1 == 1:
      for x, y in As[j]:
        if (j>>x) & 1 != y:
          flag = 1
          break
  if flag == 0:
    honest = max(honest, bin(i)[2:].count('1'))

print(honest)

Submission status: Wrong Answer

Solution code:
N = int(input())

As = [[] for _ in range(N)]

for i in range(N):
  n = int(input())
  for j in range(n):
    person, state = [int(k) for k in input().split()]
    As[i].append([person-1, state])
        
honest = 0
for i in range(2**N):
  flag = 0
  for j in range(N):
    if (i>>j) & 1:
      for x, y in As[j]:
        if (j>>x) & 1 != y:
          flag = 1
          break
  if flag == 0:
    honest = max(honest, bin(i)[2:].count('1'))

print(honest)

Submission status: Wrong Answer

Solution code:
N = int(input())

As = [[] for _ in range(N)]

for i in range(N):
  n = int(input())
  for j in range(n):
    person, state = [int(k) for k in input().split()]
    As[i].append([person-1, state])
    
print(As)
    
honest = 0
for i in range(2**N):
  flag = 0
  for j in range(N):
    if (i>>j) & 1:
      for x, y in As[j]:
        if (j>>x) & 1 != y:
          flag = 1
          break
  if flag == 0:
    honest = max(honest, bin(i)[2:].count('1'))

print(honest)

Submission status: Wrong Answer

Solution code:
n = int(input())

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


l = []
ans = 0
for i in range(2**n):
	l = []
	torf = [0 for _ in range(n)]
	# 正直者を1にする
	for j in range(n):
			if i & (1<<j):
				torf[j] = 1
				l.append(j)
	flag = False
	for j in range(n):
		# 正直者の証言が正しいかチェック
		if torf[j] == 1:
			for k in range(a[j]):
				if torf[xy[j][k][0]-1] != xy[j][k][1]:
					flag = True
					break
		# 嘘つきの証言が嘘かチェック
		else:
			for k in range(a[j]):
				if torf[xy[j][k][0]-1] == xy[j][k][1]:
					flag = True
					break
		if flag:
			break
	if not flag:
		ans = max(ans,len(l))

print(ans)

Submission status: Wrong Answer

Solution code:
def is_nth_bit_set(x, n):
    if x & (1 << n):
        return 1
    else:
        return 0


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

ans = 0
for i in range(2 ** N):
    judge = [None] * N
    flag = True
    for j in range(N):
        honest = is_nth_bit_set(i, j)
        judge[j] = honest

    for j in range(N):
        honest = judge[j]
        for x, y in comment[j]:
            if honest:
                if judge[x] == y:
                    continue
                else:
                    flag = False
                    break
            else:
                if judge[x] == abs(y - 1):
                    continue
                else:
                    flag = False
                    break

    if not flag:
        continue

    tmp = sum(judge)
    if tmp > ans:
        ans = tmp
print(ans)

Submission status: Wrong Answer

Solution code:
def is_nth_bit_set(x, n):
    if x & (1 << n):
        return 1
    else:
        return 0


N = int(input())
comment = {}
for i in range(N):
    A = int(input())
    comment[i + 1] = []
    for _ in range(A):
        x, y = map(int, input().split())
        comment[i + 1].append((x, y))

ans = 0
for i in range(2 ** N):
    judge = [None] * N
    flag = True
    for j in range(N):
        honest = is_nth_bit_set(i, j)
        judge[j] = honest

    for j in range(N):
        honest = is_nth_bit_set(i, j)
        for x, y in comment[j + 1]:
            if honest:
                if judge[x - 1] == y:
                    continue
                else:
                    flag = False
                    break
            else:
                if judge[x - 1] == abs(y - 1):
                    continue
                else:
                    flag = False
                    break

        if not flag:
            break

    if not flag:
        continue

    tmp = sum(judge)
    if tmp > ans:
        ans = tmp
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

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


def check(i):
    honests = []
    for j in range(n):
        if (i >> j) & 1:
            honests.append(j)

    for j in honests:
        for k in range(len(testimony[j])):
            if testimony[j][k] == 1 and k not in honests:
                return False
            if testimony[j][k] == 0 and k in honests:
                return False

    return True


ans = 0
for i in range(2 << (n-1)):
    if check(i):
        count = 0
        for j in range(n-1):
            if (i >> j) & 1:
                count += 1
        ans = max(ans, count)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
rela = [[0] * N for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            rela[i][x] = 1
        else:
            rela[i][x] = -1  
            
def kensyou(person):
    for i in range(N):
        for j in range(N):
            if person[i] == 1:
                if rela[i][j] == 1:
                    if person[j] == -1:
                        return 0
                elif rela[i][j] == -1:
                    if person[j] == 1:
                        return 0
            elif person[i] == -1:
                if rela[i][j] == 1:
                    if person[j] == 1:
                        return 0
                elif rela[i][j] == -1:
                    if person[j] == -1:
                        return 0
    return 1
ans = 0
for i in range(2 ** N):
    person = []
    for j in range(N):
        if ((i >> j) & 1):
            person.append(1)
        else:
            person.append(-1)
    #print(kensyou(person))
    if kensyou(person):
        ans = max(ans, person.count(1))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
rela = [[0] * N for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            rela[i][x] = 1
        else:
            rela[i][x] = -1  
ans = 0
for i in range(N):
    for j in range(N):
        if rela[i][j] == 1:
            if rela[j][i] == 1:
                ans += 1
        elif rela[i][j] == -1:
            if rela[j][i] == -1:
                ans += 1   
print(ans)

Submission status: Wrong Answer

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    v = []
    for i in range(n):
        v.append([])
    for i in range(n):
        A = int(input())
        for j in range(A):
            human,lie = readInts() # human : 人  lie: 1 が正直者 0 が不親切
            v[human-1].append([human - 1,lie]) # human : 0-based index
    #print(v)
    def judge(bit):
        # i 人目の証言を検証する
        for i in range(n):
            # 証言は意味がないな
            if not (bit & (1<<i)): # 1のたってるやつだけみてる
                continue
            for x,y in v[i]:
                #print(x,y,bit)
                # y = 1 なのに 不親切 だったらだめ
                if y == 1 and not (bit & (1 << x)):
                    return False
                # y = 0 なのに 正直ならだめ
                if y == 0 and bit & (1 << x):
                    return False
        return True
    res = 0
    for bit in range(1 << n):
        if judge(bit):
            count = 0
            for i in range(n):
                if bit & (1 << i):
                    count += 1
            res = max(res,count)
    print(res)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

ans = 0
for i in range(2**n):
  flag = 0
  count = 0
  for j in range(n):
    if ((i>>j)&1)==1 and flag==0:
      for k,l in word[j]:
        if ((i>>(k-1))&1) != l:
          flag = 1 ## tell a lie
          break
  if flag==0:
    count = bin(i).count('1')
    ans = max(ans,count)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
k=0
l=[]
for i in range(n):
    a=int(input())
    for j in range(a):
     x1,x2=map(int,input().split())
     if x2==0:
        l.append((x1,x2))

print(n-len(set(l)))

Submission status: Wrong Answer

Solution code:
N=int(input())

answers=[]
counts=[]


for i in range(N):
    A=int(input())
    answer=[]
    for a in range(A):
        x,y=map(int,input().split())
        answer.append([x,y])
    answers.append(answer)

#print(answers)
for i in range(pow(2,N)+1):
    hypo=str(bin(i)).ljust(N+2,"0")[2:]
    judge=True
    count=0
    #print(hypo)
    for n in range(N):
        if hypo[n]=="1" and judge==True:
            count+=1
            for j in answers[n]:
                if hypo[j[0]-1]==str(j[1]):
                    pass
                else:
                    judge=False
                    break
    if judge==False:
        pass
    else:
        counts.append(count)
#print(counts)
print(max(counts))

Submission status: Wrong Answer

Solution code:
N=int(input())

answers=[]
counts=[]


for i in range(N):
    A=int(input())
    answer=[]
    for a in range(A):
        x,y=map(int,input().split())
        answer.append([x,y])
    answers.append(answer)

#print(answers)
for i in range(pow(2,N)):
    hypo=str(bin(i)).ljust(N+2,"0")[2:]
    judge=True
    count=0
    #print(hypo)
    for n in range(N):
        if hypo[n]=="1" and judge==True:
            count+=1
            for j in answers[n]:
                if hypo[j[0]-1]==str(j[1]):
                    pass
                else:
                    judge=False
                    break
    if judge==False:
        pass
    else:
        counts.append(count)
#print(counts)
print(max(counts))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import numpy as np

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N=int(input())
    A = []
    for i in range(N):
        a = int(input())
        A.append([])
        xy = None
        for j in range(a):
            xy = list(map(int,input().split()))
            A[i].append(xy)
    #print(A)

    c = 0
    for bit in range(2**N):
        bs = np.array(list(map(int,list("0"*N+bin(bit)[2:])[-N:])))
        ok = True
        #print(bs)
        for i in range(N):
            if A[i]:
                for j in range(len(A[i])):
                    x, y = A[i][j]
                    if bs[i]==0:
                        y = 1-y
                    if bs[x-1]!=y:
                        ok=False
                        #print("NG")
                        break
                else:
                    continue
                break
        if ok:
            #print("OK")
            #print(bs)
            c = max(c, bs.sum())

    print(c)        


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import numpy as np

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N=int(input())
    A = []
    for i in range(N):
        a = int(input())
        A.append([])
        xy = None
        for j in range(a):
            xy = list(map(int,input().split()))
            A[i].append(xy)
    #print(A)

    c = 0
    for bit in range(2**N):
        bs = np.array(list(map(int,list("0"*N+bin(bit)[2:])[-N:])))
        ok = True
        #print(bs)
        for i in range(N):
            if A[i]:
                for j in range(len(A[i])):
                    x, y = A[i][j]
                    if bs[i]==0:
                        y = 1-y
                    if bs[x-1]!=y:
                        ok=False
                        #print("NG")
                        break
        if ok:
            #print("OK")
            #print(bs)
            c = max(c, bs.sum())

    print(c)        


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import numpy as np

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N=int(input())
    A = []
    for i in range(N):
        a = int(input())
        xy = None
        for j in range(a):
            xy = list(map(int,input().split()))
        A.append(xy)
    #print(A)

    c = 0
    for bit in range(2**N):
        bs = np.array(list(map(int,list("0"*N+bin(bit)[2:])[-N:])))
        ok = True
        #print(bs)
        for i in range(N):
            if A[i]:
                x, y = A[i]
                if bs[i]==0:
                    y = 1-y
                if bs[x-1]!=y:
                    ok=False
                    #print("NG")
                    break
        if ok:
            #print("OK")
            c = max(c, bs.sum())

    print(c)        


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
num = int(input())
coms = [[0 for __ in range(num)] for _ in range(num)]

ans_num = 0

for com in coms:
    b = []
    n = int(input())
    for _ in range(n):
        xi,yi = [int(j) for j in input().split(" ")]
        com[xi - 1] = yi

for i in range(2 ** num):
    selects = []
    ans_array = [0 for _ in range(num)]
    indexes = []
    flag = True

    #組み合わせの作成
    for j in range(num):
        if((i >> j) & 1):
            selects.append(coms[j])
            indexes.append(j)
    
    #正直者の人(仮定)
    for i in indexes:
        ans_array[i] = 1
    
    #正直者(仮定)が正しいかの判定
    for select, index in zip(selects, indexes):
        for i, arr in enumerate(select):
            if i == index:
                continue

            if ans_array[i] != arr:
                flag = False
                break

            else:
                continue

    if flag and (len(indexes) >= ans_num):
        ans_num = len(indexes)

print(ans_num)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import numpy as np

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N=int(input())
    A = []
    for i in range(N):
        a = int(input())
        xy = None
        for j in range(a):
            xy = list(map(int,input().split()))
        A.append(xy)
    print(A)

    c = 0
    for bit in range(2**N):
        bs = np.array(list(map(int,list("0"*N+bin(bit)[2:])[-N:])))
        ok = True
        #print(bs)
        for i in range(N):
            if A[i]:
                x, y = A[i]
                if bs[i]==0:
                    y = 1-y
                if bs[x-1]!=y:
                    ok=False
                    #print("NG")
                    break
        if ok:
            #print("OK")
            c = max(c, bs.sum())

    print(c)        


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

num = int(input())
coms = [[0 for __ in range(num)] for _ in range(num)]

ans_num = 0

for com in coms:
    b = []
    n = int(input())
    for _ in range(n):
        xi,yi = [int(j) for j in input().split(" ")]
        com[xi - 1] = yi

for i in range(2 ** num):
    selects = []
    ans_array = [0 for _ in range(num)]
    indexes = []
    flag = True
    for j in range(num):
        if((i >> j) & 1):
            selects.append(coms[j])
            indexes.append(j)
    for i in indexes:
        ans_array[i] = 1
    
    for select, index in zip(selects, indexes):
        for i, arr in enumerate(select):
            if i == index:
                continue
            elif ans_array[i] != arr:
                flag = False
                continue
            else:
                continue
    if flag and (len(indexes) >= ans_num):
        ans_num = len(indexes)

print(ans_num)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
x = []
y = []

for i in range(n):
    a.append(int(input()))
    tx = []
    ty = []
    for j in range(a[i]):
        tmp = [int(i) for i in input().split()]
        tx.append(tmp[0])
        ty.append(tmp[1])
    x.append(tx)
    y.append(ty)

mx = 0
for b in range(1 << n):
    ev = [0] * n
    for i in range(n):
        if b & (1 << i): ev[i] = 1
    
    status = True
    for i in range(n):
        for j in range(a[i]):
            status = (ev[i] == 0 or ev[x[i][j] - 1] == y[i][j]) and (ev[i] == 1 or ev[x[i][j] - 1] != y[i][j])
    if status and mx < sum(ev): mx = sum(ev)

print(mx)

Submission status: Wrong Answer

Solution code:
n = int(input())

A = []

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

ans = 0
max = 0
flag = 0

for i in range(2**n):
    i = 3
    ans = 0
    flag = 0
    for j in range(n):
        if ((i>>j) & 1) == 1 and flag ==  0:
            for k,l in A[j]:
                if ((i>>(k-1)) & 1) != l:
                    flag = 1
                    break
    if flag == 0:
        ans = bin(i).count('1')
        if ans > max:
            max = ans
print(max)

Submission status: Wrong Answer

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

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

ans = 0

for b in range(1 << n): # 正直者か不親切か全ての設定パターンを作る。
    cnt = bin(b).count("1")
    judge = True
    for j in range(n):
        if judge == False: #矛盾があれば、ループを止める。
            break
        if b & (1 << j) != 0: # j番目の人が正直者設定なら進む。
            for x, y in l[j]:
                if y == 1 and b & (1 << j) == 0: # 証言:正直者、設定:不親切の場合
                    judge = False
                if y == 0 and b & (1 << j) != 0: # 証言:不親切、設定:正直者の場合
                    judge = False
    if judge == True:
        ans = max(cnt, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
x = []
y = []

for i in range(n):
    a.append(int(input()))
    tx = []
    ty = []
    for j in range(a[i]):
        tmp = [int(i) for i in input().split()]
        tx.append(tmp[0])
        ty.append(tmp[1])
    x.append(tx)
    y.append(ty)


mx = 0
for b in range(1 << n):
    ev = [0] * n
    for i in range(n):
        if b & (1 << i): ev[i] = 1
    
    status = True
    for i in range(n):
        for j in range(a[i]):
            if ev[i] == 1:
                if ev[x[i][j] - 1] != y[i][j]:
                    status = False
            else:
                if ev[x[i][j] - 1] == y[i][j]:
                    status = False
    
    if status and mx < sum(ev): mx = sum(ev)

print(mx)