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:
def main():
    # 入力
    n = int(input())

    boolls = [[]]
    for i in range(n):
        tmpls = []
        for x in boolls:
            y = x.copy()
            x.append(True)
            y.append(False)
            tmpls.append(x)
            tmpls.append(y)
        boolls = tmpls

    boolls.sort(key=lambda _: _.count(True), reverse=True)

    xyls = []
    for i in range(n):
        ai = int(input())
        tuples = []
        for j in range(ai):
            x, y = map(int, input().split())
            tuples.append((x, y==1))
        xyls.append(tuples)

    tmpTrueCnt = n
    max_cnt = 0
    for boolx in boolls:
        truecnt = boolx.count(True)
        if max_cnt > truecnt:
            break

        if tmpTrueCnt > truecnt:
            tmpTrueCnt = truecnt

        ok = True
        for i in range(len(boolx)):
            if not ok:
                break
            tf = boolx[i]
            if tf:
                zz = xyls[i]
            else:
                zz = [(x[0], not x[1]) for x in xyls[i]]

            for message in zz:
                if boolx[message[0]-1] != message[1]:
                    ok = False
                    break

        if ok:
            if max_cnt < tmpTrueCnt:
                max_cnt = tmpTrueCnt

    print(max_cnt)


main()

Submission status: Wrong Answer

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

# bfs,dfs ?->try dfs
def dfs(i):#iの人が正直者だと仮定する。i=0,1,2,...,n-1
  seen=[-1]*n # -1:未定、1:正直者、0:不親切
  seen[i]=1
  todo=list(range(n))
  todo.append(i)
  while len(todo)>0:
    b=todo.pop()
    if seen[b]==1:
      l=xy[b]
      for li in l:
        if seen[li[0]-1]==-1:
          seen[li[0]-1]=li[1]
          if li[1]==1:
            todo.append(li[0]-1)
        elif seen[li[0]-1]!=li[1]:
          return 0

  return seen.count(1)

ans=0
for i in range(n):
  ans=max(ans,dfs(i))
print(ans)

Submission status: Wrong Answer

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

# bfs,dfs ?->try dfs
def dfs(i):#iの人が正直者だと仮定する。i=0,1,2,...,n-1
  seen=[-1]*n # -1:未定、1:正直者、0:不親切
  seen[i]=1
  todo=list(range(n))
  todo.append(i)
  while len(todo)>0:
    b=todo.pop()
    l=xy[b]
    if seen[b]==1:
      for li in l:
        if seen[li[0]-1]==-1:
          seen[li[0]-1]=li[1]
          if li[1]==1:
            todo.append(li[0]-1)
        elif seen[li[0]-1]!=li[1]:
          return -1

  return seen.count(1)

ans=0
for i in range(n):
  ans=max(ans,dfs(i))
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import itertools

# -1 no ans
# 1 syoziki
# 0 hu sinsetu

N = int(input())
ans = [[-1] * N for i in range(N)]


for person in range(N):
    A = int(input())
    print(A)
    for _ in range(A):
        x, y = map(int, input().split())
        x -= 1
        ans[person][x] = y


def is_ok(num):
    # -1 not decided
    # 1 syoziki
    # 0 husinsetu
    people = [-1] * N
    for i in range(N):
        # i is syoziki
        if((num >> i) & 1):
            if(people[i] == 0):
                return False
            people[i] = 1
            for j in range(N):
                if(ans[i][j] == 1):
                    if(people[j] == 0):
                        return False
                    people[j] = 1
                if(ans[i][j] == 0):
                    if(people[j] == 1):
                        return False
                    people[j] = 0
        else:
            if(people[i] == 1):
                return False
            people[i] = 0

    return True


def countBit(num):
    ori = num
    count = 0
    while(num > 0):
        if(num & 1):
            count += 1
        num = num >> 1
    return count


out = 0

for i in range(1 << N):
    if(is_ok(i)):
        out = max(out, countBit(i))

print(out)

Submission status: Wrong Answer

Solution code:
n = int(input())
alist = []
xy = [[] for i in range(n)]
ans = 0
for i in range(n):
    xy[i] =  []
for i in range(n):
    alist.append(int(input()))
    for j in range(alist[i]):
        a,b=input().split()
        xy[i].append([int(a), int(b)])
g = [[] for i in range(2**n-1)]
for i in range(1,2**n):
    for j in range(n):
        if list(format(i,'0b').zfill(n))[j] == '1':
            g[i-1].append(xy[j])
def lie(xy,p):
    z = list(format(p,'0b').zfill(n)) 
    for i in range(len(xy)):
        for j in range(len(xy[i])):
            print(str(xy[i][j][1]),z[xy[i][j][1]-1])
            if str(xy[i][j][1]) == z[xy[i][j][0]-1]:
                continue
            else:
                return 'No'
                break
    return 'Yes'
for k in range(2**n-1):
    if lie(g[k],k+1) == 'Yes':
        print(k+1)
        ans = max(ans,list(str(format(k+1,'0b'))).count('1'))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

def popcount(x):
    return bin(x).count('1')

g = [[-1 for j in range(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
        g[x][y] = y

ans = 0
for i in range(1 << n):
    d = [0 for _ in range(n)]
    for j in range(n):
        if i >> j & 1:
            d[j] = 1
    ok = True
    for j in range(n):
        if d[j]:
            for k in range(n):
                if g[j][k] == -1:
                    continue
                if g[j][k] != d[k]:
                    ok = False
    if ok:
        ans = max(ans, popcount(i))

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())
tes = [[-1]*N for i in range(N)]
for i in range(N):
    A = int(readline())
    for j in range(A):
        x,y = map(int,readline().rstrip().split())
        tes[i][x-1] = y

cnt = 0
for i in range(2**N):
    flag = True
    for j in range(N):
        hon = [0]*N
        if (i>>j)&1 == 1:
            hon[j] = 1
            for k in range(N):
                if tes[j][k] == -1:
                    continue
                if tes[j][k] != hon[k]:
                    flag = False
                    break
    if flag:
        cnt = max(cnt,hon.count(1))
print(cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())
tes = [[0]*N for i in range(N)]
for i in range(N):
    A = int(readline())
    for j in range(A):
        x,y = map(int,readline().rstrip().split())
        tes[i][x-1] = y

cnt = 0
for i in range(2**N):
    hon = [0]*N
    for j in range(N):
        if (i>>j)&1:
            hon[j] = 1
    flag = True
    for j in range(N):
        if hon[j]:
            for k in range(N):
                if tes[j][k] != hon[k]:
                    flag = False
                    break
        if not flag:
            break
    if flag:
        cnt = max(cnt,hon.count(1))
print(cnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())
tes = [[-1]*N for i in range(N)]
for i in range(N):
    A = int(readline())
    for j in range(A):
        x,y = map(int,readline().rstrip().split())
        tes[i][x-1] = y

cnt = 0
for i in range(2**N):
    hon = [0]*N
    for j in range(N):
        if (i>>j)&1:
            hon[j] = 1
    flag = True
    for j in range(N):
        if hon[j]:
            for k in range(N):
                if tes[j][k] != hon[k]:
                    flag = False
                    break
        if not flag:
            break
    if flag:
        cnt = max(cnt,hon.count(1))
print(cnt)

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 j in range(a)]
    word.append(l)

ans=0

for i in range(2**n):
    m=bin(i)[2:].rjust(n, "0")
    cnt=0
    flag=0

    for j in range(n):
        if m[j]=="0":
            pass
        elif m[j]=="1":
            for k in range(len(word[j])):
                target=word[j][k][0]-1
                if m[target]=="1" and word[j][k][1]==1:
                    cnt+=1
                elif m[target]!=str(word[j][k][1]):
                    flag=1
    
    if flag==0 and cnt>ans:
        ans=cnt

Submission status: Wrong Answer

Solution code:
n = int(input())

a = []

evidences = []
for i in range(n):
    ls = []
    x = int(input())
    a.append(x)
    for j in range(x):
        l = [int(_) for _ in input().split(' ')]
        ls.append(l)
    evidences.append(ls)

patterns = []
for i in range(2**n):
    pattern = [0] * n
    for j in range(n):
        if (i >> j & 1):
            pattern[j] = 1
    patterns.append(pattern)

honest = 0
for pattern in patterns:
    contradict = False
    for i in range(n):
        for evidence in evidences[i]:
            if(pattern[i] == 1):
                if (pattern[evidence[0]-1] != evidence[1]):
                    contradict = True
            else:
                if (pattern[evidence[0]-1] == evidence[1]):
                    contradict = True
    if (contradict == False):
        honest = max(honest, pattern.count(1))

print(honest)

Submission status: Wrong Answer

Solution code:
n = int(input())

a = []

# 証言（1:honest, 0:unkind）
evidences = []
for i in range(n):
    ls = []
    x = int(input())    #証言数
    a.append(x)
    for j in range(x):
        l = [int(_) for _ in input().split(' ')]
        ls.append(l)
    evidences.append(ls)

patterns = []
for i in range(2**n):
    pattern = [0] * n
    for j in range(n):
        if (i >> j & 1):
            pattern[j] = 1
    patterns.append(pattern)
    
print(n)
print(evidences)
print(patterns)

honest = 0
for pattern in patterns:
    contradict = False
    for i in range(n):
        for evidence in evidences[i]:
            if(pattern[i] == 1):
                if (pattern[evidence[0]-1] != evidence[1]):
                    contradict = True
                    break
            else:
                if (pattern[evidence[0]-1] == evidence[1]):
                    contradict = True
                    break
    if (contradict == False):
        honest = max(honest, pattern.count(1))

print(honest)

Submission status: Wrong Answer

Solution code:
n = int(input())

a = []

# 証言（1:honest, 0:unkind）
evidences = []
for i in range(n):
    ls = []
    x = int(input())    #証言数
    a.append(x)
    for j in range(x):
        l = [int(_) for _ in input().split(' ')]
        ls.append(l)
    evidences.append(ls)

patterns = []
for i in range(2**n):
    pattern = [0] * n
    for j in range(n):
        if (i >> j & 1):
            pattern[j] = 1
    patterns.append(pattern)

honest = 0
for pattern in patterns:
    contradict = False
    for i in range(n):
        for evidence in evidences[i]:
            if(pattern[i] == 1):
                if (pattern[evidence[0]-1] != evidence[1]):
                    contradiction = True
                    break
            else:
                if (pattern[evidence[0]-1] == evidence[1]):
                    contradiction = True
                    break
    if (contradict == False):
        honest = max(honest, pattern.count(1))

print(honest)

Submission status: Wrong Answer

Solution code:
# 人数
n = int(input())

# 証言の数
a = []

# 証言（1:honest, 0:unkind）
evidences = []
for i in range(n):
    ls = []
    x = int(input())    #証言数
    a.append(x)
    for j in range(x):
        l = [int(_) for _ in input().split(' ')]
        ls.append(l)
    evidences.append(ls)

patterns = []
for i in range(2**n):
    pattern = [0] * n
    for j in range(n):
        if (i >> j & 1):
            pattern[j] = 1
    patterns.append(pattern)

honest = 0
for pattern in patterns:
    for i in range(n):
        for evidence in evidences[i]:
            if(pattern[i] == 1):
                if (pattern[evidence[0]-1] != evidence[1]):
                    break
            else:
                if (pattern[evidence[0]-1] == evidence[1]):
                    break
        else:
            continue
        break
    else:
        if(pattern.count(1) > honest):
            honest = pattern.count(1)

print(honest)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    n = int(input())
    info = []
    for _ in range(n):
        a = int(input())
        tmp = []
        for __ in range(a):
            tmp.append(list(map(int, input().split())))
        info.append(tmp)
    
    mask = 0
    honest = [0] * n
    ans = 0
    while mask < (1 << n):
        part = 0
        is_ok = True
        for i in range(n):
            if 1  & mask >> i  == 1:
                 honest[i] = 1
                 part += 1

        for i in range(n):
            if honest[i] == 1:
                for w in info[i]:
                    if honest[w[0] - 1] != w[1]:
                        is_ok = False
        
        if is_ok:
            if part > ans:
                ans = part
        mask += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A = []
for i in range(N):
	a = []
	for j in range(ri()):
		x, y = rl()
		a.append((x-1, y))
	A.append(a)

def check(A, b):
	for i, a in enumerate(A):
		for x, y in a:
			if b[i] == 1:
				if b[x] != y:
					return False
	return True

import itertools
ans = 0
for b in itertools.product([0,1], repeat=N):
	if check(A, b):
		print(b)
		ans = max(ans, sum(b))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, math
from pprint import pprint
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A = []
for i in range(N):
	a = []
	for j in range(ri()):
		x, y = rl()
		a.append((x-1, y))
	A.append(a)

def check(A, b):
	for i, a in enumerate(A):
		for x, y in a:
			if b[i] == 1:
				if b[x] != y:
					return False
			else:
				if b[x] == y:
					return False
	return True

import itertools
ans = 0
for b in itertools.product([0,1], repeat=N):
	if check(A, b):
		ans = max(ans, sum(b))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
li = []
for i in range(N):
    A = int(input())
    li.append([[int(j) for j in input().split()] for k in range(A)])

ans = 0

for i in range(1 << N):
    consistent = True  # 全ての証言と矛盾がなければTrue
    honests = 0  # 正直者の人数
    for j in range(N):  # j番目の人の証言をチェックする
        claims = li[j]  # j番目の人の証言リスト
        if (i >> j) & 1 == 1:
            # i is honest
            honests += 1
            for claim in claims:
                if (i >> (claim[0] - 1)) & 1 != claim[1]:
                    # 正直者・嘘つきの仮定と証言が一致しない
                    consistent = False
        else:
            # i is a lier
            for claim in claims:
                if (i >> (claim[0] - 1)) & 1 == claim[1]:
                    # 正直者・嘘つきの仮定と証言が一致してしまう（jは嘘つきなのに）
                    consistent = False
    if consistent:
        ans = max(ans, honests)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
li = []
for i in range(N):
    A = int(input())
    li.append([[int(j) for j in input().split()] for k in range(A)])

ans = 0

for i in range(2 ** N):
    consistent = True  # 全ての証言と矛盾がなければTrue
    honests = 0  # 正直者の人数
    for j in range(N):  # j番目の人の証言をチェックする
        claims = li[j]  # j番目の人の証言リスト
        if (i >> j) & 1 > 0:
            # i is honest
            honests += 1
            for claim in claims:
                if (i >> (claim[0] - 1)) & 1 !=  claim[1]:
                    # 正直者・嘘つきの仮定と証言が一致しない
                    consistent = False
                    break
        else:
            # i is a lier
            for claim in claims:
                if (i >> (claim[0] - 1)) & 1 == claim[1]:
                    # 正直者・嘘つきの仮定と証言が一致してしまう（jは嘘つきなのに）
                    consistent = False
                    break
    if consistent:
        ans = max(ans, honests)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
honest = []
unkind = []
for _ in range(n):
    a = int(input())
    ho = []
    un = []
    for _ in range(a):
        x, y = map(int, input().split())
        if y == 1:
            ho.append(x-1)
        else:
            un.append(y-1)
    honest.append(ho)
    unkind.append(un)

# 全探索
ans = []
for i in range(2 ** n):
    person = []
    for j in range(n):
        person.append(i % 2)
        i //= 2

    flag = False

    # honestを判定
    for j in range(n):
        if person[j] == 1:
            for k in honest[j]:
                if person[k] == 0:
                    flag = True
                    break
            if flag:
                break
    if flag:
        continue
    
    # unkindを判定
    for j in range(n):
        if person[j] == 1:
            for k in unkind[j]:
                if person[k] == 1:
                    flag = True
                    break
            if flag:
                break
    if flag:
        continue

    ans.append(sum(person))
print(max(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
depositions = []
for _ in range(n):
    p = []
    for _ in range(int(input())):
        x, y = map(int, input().split())
        p.append((x, y))
    depositions.append(p)


def get_honest(a, b, bit):
    if b == 1 and (bit & (1 << a - 1)) > 0:
        return 1
    elif b == 0 and (bit & (1 << a - 1)) == 0:
        return 1
    else:
        return 0


num_people = 0
for i in range(2 ** n):
    escape = 0
    for j, pair in enumerate(depositions):
        if escape:
            break
        for (k, l) in pair:
            flag = get_honest(k, l, i)
            if i & (1 << j):
                if flag == 0:
                    escape = 1
                    break
            else:
                if flag == 1:
                    escape = 1
                    break
    if escape == 0:
        num_people = max(num_people, bin(i)[2:].count('1'))

print(num_people)

Submission status: Wrong Answer

Solution code:
n = int(input())
depositions = []
for _ in range(n):
    p = []
    for _ in range(int(input())):
        x, y = map(int, input().split())
        p.append((x,y))
    depositions.append(p)

def get_hoest(a,b, bit):
    if b == 1 and (bit & (1 << a - 1)) > 0:
        return 1
    elif b == 0 and (bit & (1 << a - 1)) == 0:
        return 1
    else:
        return 0

num_people = 0
for i in range(2 ** n):
    escape = 0
    for j, pair in enumerate(depositions):
        if escape:
            continue
        for (k,l) in pair:
            flag = get_hoest(k, l, i)
            if i & (1 << j):
                if flag == 0:
                    escape = 1
            else:
                if flag == 1:
                    escape = 1
    if escape == 0:
        num_people = max(num_people, bin(i)[2:].count('1'))

print(num_people)

Submission status: Wrong Answer

Solution code:
n = int(input())
depositions = []
for _ in range(n):
    p = []
    for _ in range(int(input())):
        x, y = map(int, input().split())
        p.append((x,y))
    depositions.append(p)

def get_hoest(a,b, bit):
    if b == 1 and (bit & (1 << a - 1)) > 0:
        return 1
    elif b == 0 and (bit & (1 << a - 1)) == 0:
        return 1
    else:
        return 0

num_people = 0
for i in range(2 ** n):
    escape = 0
    for j, pair in enumerate(depositions):
        if escape:
            continue
        for (k,l) in pair:
            flag = get_hoest(k, l, i)
            if i & (1 << j):
                if flag == 0:
                    escape = 1
                    continue
            else:
                if flag == 1:
                    escape = 1
                    continue
    if escape == 0:
        num_people = max(num_people, bin(i)[2:].count('1'))

print(num_people)

Submission status: Wrong Answer

Solution code:
N = int(input())

evidences = [[] for _ in range(N)]
for i in range(N): # i:人の番号
    A = int(input())
    for _ in range(A): #  x:人の番号, y:正直者か見破る番号
        x, y = map(int, input().split())
        evidences[i].append((x - 1, y))
print(evidences)
        
# 全通り試す(最大は2**15だから問題ない)
result = 0
for i in range(1, 2 ** N): # iのビットは正直者と不親切な人の割合
    consistent = True# 全通り試して矛盾がなければtrue
    for j in range(N):# ビット演算で一人ずつ見ていく
        if (i >> j) & 1 == 0: # 選んだ一人が不親切なら
            continue
        for x, y in evidences[j]: # x:人の番号, y:正直者か見破る番号
            if (i >> x) & 1 != y: # xで一人を選んで,yの証言と一致してなかったら矛盾
                consistent = False
    if consistent:
        result = max(result, bin(i).count('1'))
print(result)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    N = int(input())
    L = [[] for _ in range(N)]
    maxans = 0

    for i in range(N):
        for j in range(int(input())):
            x, y = map(int, input().split())
            x = x - 1
            L[i].append([x, y])  # iが為した証言をL[i]に格納

    for i in range(2 ** N):  # 正直者の組み合わせ全て調べる
        honest = [0] * N
        consistent = True
        cnt = 0
        for j in range(N):
            if ((i >> j) & 1):  # jが正直者
                honest[j] = 1
                cnt += 1  # 正直者の数

        for k in range(N):
            if honest[k] == 1:
                for l in L[k]:
                    if (l[1] == 1 and honest[l[0]] == 0) or \
                            (l[1] == 0 and honest[l[0]] == 1):
                        consistent = False
                        break
            else:
                for l in L[k]:
                    if (l[1] == 1 and honest[l[0]] == 1) or \
                            (l[1] == 0 and honest[l[0]] == 0):
                        consistent = False
                        break

        if consistent == True:
            maxans = max(maxans, cnt)

    print(maxans)


resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
testimony = []  # 各iの証言

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


best = 0  # 正直者の最大人数

print(1 << 1)

# 「<<」はビット演算を表す
# 1 << 1 ならば　0001 → 0010　なので 2
# 1 << 2 ならば　0001 → 0100　なので 4
# 1 << 3 ならば　0001 → 1000　なので 8
# 3人なら 000, 001, 010, 011, 100, 101, 110, 111 の8通りが考えられる
# 1の部分が正直者、0が不親切者、111だと3人とも正直者
# honest=0 ならば 正直者は0、honest=1　ならば　正直者は1(index=0)
# honest=2 ならば 正直者は2(index=1)、honest=3　ならば　正直者は1と2(011 2進数)
for honest in range(1 << n):  # 正直者をあらかじめ仮定して破綻を確認する
    for i in range(n):  # 証言者i
        if not (honest >> i) & 1:  # iが不親切な人なら証言を聞かない
            continue # 「continue」はfor文スキップを表す
        for j, t in testimony[i]:  # iによるjに対する証言t
            if (honest >> j) & 1 != t:  # jに対する仮定とtが食い違えば破綻
                break # for文を抜ける
        else:
            continue
        break
    else:  # 全ての正直者に話を聞いて破綻が無ければ更新
        best = max(best, bin(honest).count('1'))

print(best)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[[] for i in range(N)]
for i in range(N):
  M=int(input())
  L[i]=[list(map(int,input().split())) for j in range(M)]
#print(L)

L_2=[[i,None] for i in range(N)]
L_3=[0 for i in range(N)]
ans=0
for k in range(2**N):
	Y_N=True
	count=0
	for a in range(N):
		if ((k >> a) & 1):  # 正直者のリストを作る
			L_3[a]=1
	for a in range(N):  # このループが一番のポイント
		if ((k >> a) & 1):  # 正直者のリスト
			count += 1
			for b in range(len(L[a])):
				if L_3[a] == 0: #もし正直者じゃないとされてたら
					Y_N=False #破綻
				person = L[a][b][0]-1
				if L_3[person]==1-L[a][b][1]: #すでに言われてることと矛盾
					Y_N=False #破綻
				L_3[person]=L[a][b][1] #証言の内容で人となりをアップデート
				#print(L_3,a,b)
	#print(L_3,count,Y_N)
	if Y_N:
		ans = max(ans, count)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

#証言のリスト
l = [[-1] * 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())
        #証言の記録
        l[i][x-1] = y

ans = 0

for i in range(2**n):
    Val = True
    for j in range(n):
        if (i >> j & 1) == 1:   #iにおけるjビット目が、1であれば
            for k in range(n):
                if l[j][k] == -1: continue
                if (j >> k & 1) != l[j][k]: Val = False
    if Val:
        res = 0
        num = i
        while num > 0:
            res += num % 2
            num //= 2
            ans = max(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

#証言のリスト
l = [[[-1] for _ in range(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())
        #証言の記録
        l[i][x-1] = y

ans = 0

for i in range(2**n):
    Val = True
    for j in range(n):
        if (i >> j & 1):   #iにおけるjビット目が、1であれば
            for k in range(n):
                if l[j][k] == -1: continue
                if (j >> k & 1) != l[j][k]: Val = False
    if Val:
        res = 0
        num = i
        while num > 0:
            res += num % 2
            num //= 2
            ans = max(ans, res)

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())

#証言のリスト
l = [[-1] * 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())
        #証言の記録
        l[i][x-1] = y

ans = 0

for i in range(2**n):
    Val = True
    for j in range(n):
        if (i >> j & 1) == 1:   #iにおけるjビット目が、1であれば
            for k in range(n):
                if l[j][k] == -1: continue
                if (j >> k & 1) != l[j][k]: Val = False
    if Val:
        res = 0
        num = i
        while num > 0:
            res += num % 2
            num //= 2
            ans = max(ans, res)

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())

#証言のリスト
l = [[-1] * 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())
        #証言の記録
        l[i][x-1] = y

ans = 0

for i in range(2**n):
    Val = True
    for j in range(n):
        if (i >> j & 1):   #iにおけるjビット目が、1であれば
            for k in range(n):
                if l[j][k] == -1: continue
                if (j >> k & 1) != l[j][k]: Val = False
    if Val:
        res = 0
        num = i
        while num > 0:
            res += num %2
            num //= 2
            ans = max(ans, res)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

#証言のリスト
l = [[-1] * 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())
        #証言の記録
        l[i][x-1] = y

ans = 0

for i in range(2**n):
    Val = True
    for j in range(n):
        if (i >> j & 1):   #iにおけるjビット目が、1であれば
            for k in range(n):
                if l[j][k] == -1: continue
                if (j >> k & 1) != l[j][k]: Val = False
    if Val:
        res = 0
        num = i
        while num > 0:
            res += num %2
            num //= 2
            ans = max(ans, res)

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())

#証言のリスト
l = [[-1] * 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())
        #証言の記録
        l[i][x-1] = y

ans = 0

for i in range(2**n):
    Val = True
    for j in range(n):
        if (i >> j & 1):   #iにおけるjビット目が、1であれば
            for k in range(n):
                if l[j][k] == -1: continue
                if (j >> k & 1) != l[j][k]: Val = False
    if Val:
        res = 0
        while i > 0:
            res += i %2
            i //= 2
            ans = max(ans, res)

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
words = []
ans = 0
for i in range(n):
	a = int(input())
	w = []
	for _ in range(a):
		x, y = map(int, input().split())
		w.append([x-1, y])
	words.append(w)
for bit in range(n):
	ok = True
	is_honest = [(bit>>i) & 1 for i in range(n)] #bitをiずらして末尾が1のひとは正直
    
	for i in range(n):
		if not is_honest[i]:
			continue
		for x, y in words[i]:
			if is_honest[x] != y:
				ok = False
	if ok:
		ans = max(ans, sum(is_honest))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = []
XY_list = []
for i in range(N):
    a = int(input())
    xy = [list(map(int, input().split())) for i in range(a)]
    A_list.append(a)
    XY_list.append(xy)

result = 0

for i in range(2 * N):
    bit = str(format(2 ** N + 1 - i, 'b')).zfill(N)
    flag = 0
    for j in range(N):
        if bit[j] == '1':
            for k in range(A_list[j]):
                man = XY_list[j][k][0]
                judge = XY_list[j][k][1]
                if int(bit[man - 1]) != judge:
                    flag = 1
                    break
        if flag == 1:
            break
    if flag == 0:
        tmp = 0
        for j in range(N):
            tmp += int(bit[j])
        if tmp > result:
            result = tmp
print(result)

Submission status: Wrong Answer

Solution code:
N = int(input())
A_list = []
XY_list = []
for i in range(N):
    a = int(input())
    xy = [list(map(int, input().split())) for i in range(a)]
    A_list.append(a)
    XY_list.append(xy)

result = 0

for i in range(2 * N + 2):
    bit = str(format(2 ** N + 1 - i, 'b')).zfill(N)
    flag = 0
    for j in range(N):
        if bit[j] == '1':
            for k in range(A_list[j]):
                man = XY_list[j][k][0]
                judge = XY_list[j][k][1]
                if int(bit[man - 1]) != judge:
                    flag = 1
                    break
        if flag == 1:
            break
    if flag == 0:
        tmp = 0
        for j in range(N):
            tmp += int(bit[j])
        if tmp > result:
            result = tmp
print(result)