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())

sayTable = []
for i in range(n):
	a = int(input())
	
	sayArray = []
	for j in range(a):
		x, y = [int(v) for v in input().split()]
		sayArray.append((x-1, y+1))
	sayTable.append(sayArray)

def countHonest(honest):
	count = 0
	for v in honest:
		if v == 2:
			count += 1
	return count

def checkHonest(sayArray, honest):
	for x, y in sayArray:
		if y == 2 and honest[x] != 2:
			return False
	return True

def checkHonestAll(sayTable, honest):
	for i in range(n):
		h = honest[i]
		if h != 2:
			continue
		sayArray = sayTable[i]
		for x, y in sayArray:
			if y != honest[x]:
				return False
	return True

def setHonest(sayArray, honest):
	for x, y in sayArray:
		honest[x] = y

def search(sayTable, honest, i):
	if i >= n:
		if checkHonestAll(sayTable, honest):
			return countHonest(honest)
		else:
			return 0

	count = 0
	h = honest[i]
	sayArray = sayTable[i]
	if (h == 0 or h == 2) and checkHonest(sayArray, honest):
		copyHonest = honest[:]
		setHonest(sayArray, copyHonest)
		copyHonest[i] = 2
		c = search(sayTable, copyHonest, i+1)
		if count < c:
			count = c

	honest[i] = 1
	c = search(sayTable, honest, i+1)
	if count < c:
		count = c
	return count

print(search(sayTable, [0] * n, 0))

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
xy = [0 for _ in range(n)]
for i in range(n):
    ai = int(input())
    xy[i] = [list(map(int , input().split())) for _ in range(ai)]

#print(xy)
#print(xy[0])
#print(xy[0][0])
ans = 0
for i in itertools.product([0, 1], repeat=n):
    ok = True
    cnt = sum(i)
    for j in range(n):
        xyj = xy[j]
        if i[j] == 1:
            for xyk in xyj:
                if xyk[1] == 1:
                    if i[xyk[0]-1] == 0:
                        ok = False
                elif xyk[1] == 0:
                    if i[xyk[0]-1] == 1:
                        ok = False
    print(ok, i)
    if ok:
        ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
pattern = []
test = []
ans = 0

def make_pattern(arr):
    if len(arr) == N:
        pattern.append(arr)
        return
    make_pattern(arr + [1])
    make_pattern(arr + [0])
    return

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

make_pattern([])

for p in pattern:
    is_mismatched = False
    for i in range(N):
        for xi, yi in test[i]:
            if p[i] == 1:
                if p[xi - 1] != yi:
                    is_mismatched = True
            else:
                if p[xi - 1] != (yi + 1) % 2:
                    is_mismatched = True
    if not is_mismatched:
        ans = max(ans, p.count(1))

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    person_list = [i for i in range(1, N+1)]
    
    ans_per_dic = {}
    ans_pattern_dic = {}
    honest_pattern = combinations(N, person_list)
    for i in range(1, N+1):
        ans_per_dic[i] = 0
        A = int(input())
        ans_list = []
        for a in range(A):
            l = input().rstrip().split(" ")
            l = [int(x) for x in l]
            ans_list.append(l)
        ans_pattern_dic[i] = ans_list
    
    cnt = 0
    
    for pattern in honest_pattern:
        temp_dic = ans_per_dic.copy()
        for p in pattern:
            temp_dic[p] = 1
        flag = True
        for person, answer in ans_pattern_dic.items():
            if judge(temp_dic, person, answer) == False:
                flag = False
                break
        if (flag == False):
            continue
        if cnt < len(pattern):
            cnt = len(pattern)
    print(cnt)
            
def judge(temp_dic, person, answer):
    if temp_dic[person] == 1:
        for ans in answer:
            if temp_dic[ans[0]] != ans[1]:
                return False
    else:
        return False
    return True
    
def combinations(n, guest_list):
    all_comb_list = []
    for i in range(1, 2**n):
        num = i
        c_list = []
        for j in range(n):
            if num % 2 == 1:
                c_list = [guest_list[n - 1 - j]] + c_list
            num = num // 2
        all_comb_list.append(c_list)
    return all_comb_list
    
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def countSetBits(n): 
    count = 0
    while (n): 
        count += n & 1
        n >>= 1
    return count 

def main():
    N = I()
    mat = [[-1 for __ in range(N)] for _ in range(N)]
    for i, _ in enumerate(range(N)):
        A = I()
        for __ in range(A):
            targ, b = LI()
            mat[i][targ - 1] = b
    ans = 0
    for bit in range(1 << N):
        err = False
        for j in range(N):
            honest_man = (bit & (1<<j))
            if honest_man:
                for k in range(N):
                    r = mat[j][k]
                    if r == -1:
                        continue
                    if (bit >> k) & 1 == r:
                        err = True
        if not err:
            ans = max(ans, countSetBits(bit))
    print(ans)

    '''
    for bit in range(1 << N):
        truth = [-1 for _ in range(N)]
        err = False
        for i in range(N):
            honest_man = (bit & (1<<(N-1-i)))
            if honest_man:
                for j in range(len(mat[i])):
                    con = mat[i][j]
                    targ_ix = j
                    if con != -1:
                        if truth[targ_ix] != con:
                            if truth[targ_ix] != -1:
                                err = True 
                        if (bit & (1<<(N-1-targ_ix))) != con:
                            print('i: {0:{fill}3b}'.format(i, fill='0'))
                            print('bit: {0:{fill}3b}'.format(bit, fill='0'))
                            print("1<<(N-1-targ_ix): {0:{fill}3b}".format(bit & (1<<(N-1-targ_ix)), fill='0'))
                            print("con: ", con)
                            err = True
                        truth[targ_ix] = con
        if not err:
            ans = max(ans, countSetBits(bit))
    '''
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
pattern = []
test = []
ans = 0

def make_pattern(arr):
    if len(arr) == N:
        pattern.append(arr)
        return
    make_pattern(arr + [1])
    make_pattern(arr + [0])
    return

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

make_pattern([])

for p in pattern:
    is_mismatched = False
    for i in range(N):
        for xi, yi in test[i]:
            if p[i] == 1:
                if p[xi - 1] != yi:
                    is_mismatched = True
                    break
            else:
                if p[xi - 1] != (yi + 1) % 2:
                    is_mismatched = True
                    break
        if is_mismatched:
            break
    if not is_mismatched:
        ans = max(ans, p.count(1))

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
xy = [0 for _ in range(n)]
for i in range(n):
    ai = int(input())
    xy[i] = [list(map(int , input().split())) for _ in range(ai)]

#print(xy)
#print(xy[0])
#print(xy[0][0])
ans = 0
for i in itertools.product([0, 1], repeat=n):
    ok = True
    cnt = sum(i)
    for j in range(n):
        xyj = xy[j]
        for xyk in xyj:
            if xyk[1] == 0:
                if i[xyk[0]-1] == 1:
                    ok = False
            elif xyk[1] == 1:
                if i[xyk[0]-1] == 0:
                    ok = False
    if ok:
        ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
wi = [[] for i in range(N)]
for i in range(N):
    wi[i].append([i,1])
    for j in range(int(input())):
        x,y = map(int,input().split())
        wi[i].append([x-1,[-1,1][y]])
ans = 0
for i in range(2**N):
    flag = False
    hoge = 0
    witnes = [0]*N
    for j in range(N):
        if i>>j & 1 == 1:
            hoge += 1
            for x,y in wi[j]:
                if witnes[x] in [y,0]:
                    witnes[x] = y
                else:
                    flag = True
                    break
        else:
            for x,y in wi[j]:
                if witnes[x] in [-y,0]:
                    witnes[x] = -y
                else:
                    flag = True
                    break
        if flag:
            break
    if not flag:
        ans = max(hoge,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
w=[[] for i in range(n)]
for i in range(n):
    a=int(input())
    for j in range(a):
        x,y=map(int,input().split())
        w[i].append((x,y))
ans=0
for i in range(1<<n):
    x="0"*15+bin(i)[2:]
    z=[int(i) for i in x[-n:]]
    f=1
    for p,q in enumerate(w):
        if z[p]==1:
            for r in q:
                if (z[r[0]-1]!=r[1]):
                    f=0
    if f:
        ans=max(ans,z.count('1'))
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for i in range(N):
        a = int(input())
        for j in range(a):
            x, y = (int(i) for i in input().split())
            G[i].append((x-1, y))
            # 人iは人xのことをyと言っている

    ans = 0
    for bit in range(1 << N):
        cur = 0
        good = True  # 矛盾がない
        for i in range(N):
            if bit & (1 << i):
                # 人iは正直者
                cur += 1
                for j, y in G[i]:
                    # if (bit & (1 << j)) and y == 1:
                    #    continue
                    # elif not(bit & (1 << j)) and y == 0:
                    #    continue
                    if (bit & (1 << j)) and y == 0:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
                        break
            else:
                # 人iはうそつき
                for j, y in G[i]:
                    # if (bit & (1 << j)) and y == 0:
                    #    continue
                    # elif not(bit & (1 << j)) and y == 1:
                    #    continue
                    if (bit & (1 << j)) and y == 0:
                        good = False
                        break
                    elif not(bit & (1 << j)) and y == 1:
                        good = False
                        break
        # print(bit, ":", good)
        if good:
            ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools
n = int(input())
xy = [0 for _ in range(n)]
for i in range(n):
    ai = int(input())
    xy[i] = [list(map(int , input().split())) for _ in range(ai)]

#print(xy)
#print(xy[0])
#print(xy[0][0])
ans = 0
for i in itertools.product([0, 1], repeat=n):
    ok = True
    cnt = sum(i)
    for j in range(n):
        xyj = xy[j]
        for xyk in xyj:
            if xyk[1] == 0:
                if i[j] == 1:
                    ok = False
            elif xyk[1] == 1:
                if i[j] == 0:
                    ok = False
    if ok:
        ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = []
ans = 0
for i in range(n):
    js = int(input())
    _xy = []
    for j in range(js):
        x, y = map(int, input().split())
        _xy.append([x, y])
    xy.append(_xy)
for i in range(2 ** n):
    s = [[] for _ in range(n)]
    tmp = []
    for j in range(n):
        if i >> j & 1:
            tmp.append(j)
    for j in range(len(xy)):
        if j in tmp:
            for k in range(len(xy[j])):
                s[xy[j][k-1][0]-1].append(xy[j][k-1][1])
        else:
            for k in range(len(xy[j])):
                t = xy[j][k-1][1]
                if t == 0:
                    t = 1
                else:
                    t = 0
                s[xy[j][k-1][0]-1].append(t)
    tmp2 = 0
    s = [list(set(j)) for j in s]
    tf = True
    for j in s:
        if len(j) > 1:
            tf = False
    if tf:
        for j in range(len(s)):
            if 1 in s[j]:
                if j in tmp:
                    tmp2 += 1
    if tmp2 > ans:
        ans = tmp2
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
pattern = []
test = []
ans = 0

def make_pattern(arr):
    if len(arr) == N:
        pattern.append(arr)
        return
    make_pattern(arr + [1])
    make_pattern(arr + [0])
    return

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

make_pattern([])

for p in pattern:
    is_mismatched = False
    for i in range(N):
        for xi, yi in test[i]:
            if p[xi - 1] != (yi - p[i] + 1) % 2:
                is_mismatched = True
                break
        if is_mismatched:
            break
    if not is_mismatched:
        ans = max(ans, p.count(1))

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())

#print(N)

honest=[]
for i in range(N):
  honest.append(1)

data=[]
for i in range(N):
  A=int(input())
  kari=[]
  for j in range(A):
    kari.append(list(map(int,input().split())))
#  print(kari)
  data.append(kari)
                
#print(data)      
for i in range(N):
  honest1=[]
  for m in range(N):
   honest1.append(honest[m])
  if honest[i]==1:
   #print(i,honest,data[i])
   for j in range(len(data[i])):
     x=data[i][j][0]
     y=data[i][j][1]
    # print(i,j,x,y,honest)
#    if honest[x-1] != y:
# assuming i is honest
    # print(i,j,honest,honest1)
     honest1[x-1]= y
     cond=0
     #print(i,j,honest,honest1)
     if x-1<i and honest[x-1] !=y:
         honest[i]=0
         honest1=honest
     elif y==1:
        for k in range(len(data[x-1])):
          x0=data[x-1][k][0]
          y0=data[x-1][k][1]
          #print(i+1,x0,honest1[x0-1],y0)
          if honest1[x0-1] != y0:
             honest[i]=0
             honest1=honest
             cond=1
             break
        if cond==0:
         honest=honest1
        #print(i+1,honest)      
         
sum=0
for i in range(N):
  sum += honest[i]
  
print(sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
table = [[-1]*(N+1) for i in range(N+1)]
for i in range(1,N+1):
    A = int(input())
    for j in range(A):
        x,y = map(int,input().split())
        table[i][x] = y
# print(table)
# table[i][x] 人iが人xを正直者;1,真偽不明:0,未言及:-1
def my_shift(i,k):
    return int(str(bin(i))[-1]) if k == 0 else i>>k
ans = 0
for i in range(2**N):

    hito = [0]*N
    for j in range(N):
        if i >> j & 1:
            hito[j] = 1

    flag = True
    cnt = 0
    for j in range(N):
        if i >> j & 1:
            cnt += 1
            for k in range(N):
                if table[j+1][k+1] != -1:
                    #print(table[j+1][k+1])
                    #if table[j+1][k+1] ^ (i >> k):
                    if table[j+1][k+1] ^ my_shift(i,k):
                        # if j == 1 and k == 0:
                        #     print(i>>k)
                        #     print(my_shift(i,k))
                        #     print(table[j+1][k+1])
                        flag = False
                        # print(hito)
                        # print(i,j,k)
    if flag:
        if cnt > ans:
            ans = cnt
print(ans)
#print(3 >> 0) # 3????

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = [(bin(i)[2:]).zfill(n) for i in range(2**n)]
num_list = []
A_list = []
xy_list = []
for i in range(n):
    a = int(input())
    A_list.append(a)
    for j in range(a):
        x,y = map(int,input().split())
        xy_list.append([x,y])
for i in range(len(lst)):
    choose = lst[i]
    one_count = choose.count("1")
    a_count = 0
    print(choose)
    print(one_count)
    flag = True
    for num, j in enumerate(A_list):
        a_count += j
        for k in range(a_count-j, a_count):
            x,y = xy_list[k][0],xy_list[k][1]
            if choose[num] == "1" and choose[x-1] != str(y):
                flag = False
    if flag:
        num_list.append(one_count)
    else:
        num_list.append(0)
print(max(num_list))

Submission status: Wrong Answer

Solution code:
N = int(input())
pattern = []
test = []
ans = 0

def make_pattern(arr):
    if len(arr) == N:
        pattern.append(arr)
        return
    make_pattern(arr + [1])
    make_pattern(arr + [0])
    return

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

make_pattern([])

for p in pattern:
    is_mismatched = False
    for i in range(N):
        for xi, yi in test[i]:
            if p[xi - 1] != abs(yi - p[i] + 1):
                is_mismatched = True
                break
        if is_mismatched:
            break
    if not is_mismatched:
        ans = max(ans, p.count(1))

print(ans)

Submission status: Wrong Answer

Solution code:

N = int(input())


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


# それぞれの人が正直かどうかについて全探索する
ans = 0
for i in range(2**N):
    bnum = (bin(i)[2:]).zfill(N)

    f = True
    for j in range(N):
        # j番目のひとが正直なら
        if bnum[j] == "1":
            # 人jの証言について調べる
            for x,y in es[j]:
                # 証言内容と仮定した正直かどうか(bnumのこと)に矛盾があるなら飛ばす
                #print(j,x,y,bnum[x])
                if bnum[x] != str(y):
                    print("aaa")
                    f = False
    #print(bnum, f)
    if f:
        ans = max(ans, bnum.count("1"))
    
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools 
N=int(input())
arr=[[-1]*N]*N
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y = map(int,input().split())
        arr[i][x-1]=y
L=list(itertools.product([0,1],repeat=N))
ans=0
for l in L:
    O=[[-1]*N]*N
    for i in range(N):
        if(l[i]==1):
            for j in range(N):
                O[i][j]=arr[i][j]
    f=0
    for i in range(N):
        for j in range(N):
            if(O[i][j]!=-1):
                if O[i][j]==1 and l[j]==0:
                    f=1
                    break
                if O[i][j]==0 and l[j]==1:
                    f=1
                    break
    if f==0:
        ans=max(ans,sum(l))
print(ans)

Submission status: Wrong Answer

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

#bit全探索
#bitたつ→正直者
#bitたたない→不親切もの
tmp = [-1 for _ in range(N)]
for i in range(2 ** N):
    tmp = [-1 for _ in range(N)]
    flag = True
    cnt = 0
    for j in range(N):
        if i >> j & 1:
            #正直者
            tmp[j] = 1
            cnt += 1
    for j in range(N):
        if i >> j & 1:
            A = xy[j]
            for k in A:
                _x = k[0] - 1
                _y = k[1]
                if tmp[_x] == -1:
                    tmp[_x] = _y
                elif tmp[_x] != -1 and tmp[_x] ==_y:
                    pass
                else:
                    flag = False
    if flag:
        ans = max(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

N=2**n
ans=[]
for k in range(N):
    c=format(k,"b")
    cha=c.zfill(n)
    cnt=0
    mis=0
 
    for l in range(n):
        if cha[l]==1 and mis==0:
            for m in range(cnt,cnt+a[l]):
                if y[m]==0:
                  if cha[x[m]-1]!=0:
                    mis+=1
                    cnt+=a[l] 
                    break
                  else:
                      if m==cnt+a[l]-1:
                          cnt+=a[l]      
                else:
                  if cha[x[m]-1]!=1:
                    mis+=1
                    cnt+=a[l] 
                    break
                  else:
                      if m==cnt+a[l]-1:
                          cnt+=a[l]                     
        elif cha[l]==0 and mis==0:
            for m in range(cnt,cnt+a[l]):
                if y[m]==0:
                  if cha[x[m]-1]==0:
                    mis+=1
                    cnt+=a[l] 
                    break
                  else:
                      if m==cnt+a[l]-1:
                          cnt+=a[l] 
                else:
                  if cha[x[m]-1]==1:
                    mis+=1
                    cnt+=a[l] 
                    break
                  else:
                      if m==cnt+a[l]-1:
                          cnt+=a[l]                
        elif mis!=0:
            break        
    if mis==0:
        ans.append(cha.count("1"))
   
    
print(max(ans))

Submission status: Wrong Answer

Solution code:
n=int(input())
data=[[]]
for i in range(n):
    a=int(input())
    xy=[list(map(int,input().split())) for i in range(a)]
    data.append(xy)
ans=0
for i in range(2**n):
    lst=[0]
    for j in range(n):
        if (i>>j)&1==1:
            lst.append(1)
        else:
            lst.append(0)
    for j in range(1,n+1):
        if lst[j]==1:
            for k,l in data[j]:
                if lst[k]==l:
                    continue
                else:
                    break
            else:
                continue
            break
        else:
            for k,l in data[j]:
                if lst[k]!=l:
                    continue
                else:
                    break
            else:
                continue
            break
    else:
        ans=max(ans,sum(lst))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
data = [[] for i in range(N+1)]

for i in range(N):
  a = I()
  for j in range(a):
    data[i].append(IL())

ans = 0
for i in range(1 << N):
  TF = [-1]*N
  cnt = 0
  for j in range(N):
    if ((i >> j) & 1) == 1: #j人目が正しい
      TF[j] = True
      cnt += 1
    else:
      TF[j] = False
  
  for k in range(N):
    f = TF[k] ^ 1
    for x,y in data[k]:
      if TF[x-1] == y ^ f:
        continue
      else:
        break
    else:
      continue
    break
  else:
    ans = max(ans, cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Dec  8 20:37:58 2019

@author: matsumotoatb
"""

def f():
    N = int(input())
    A = []
    
    for n in range(N):
        templist = []
        for a in range(int(input())):
            templist.append(list(map(int, input().split())))
        A.append(templist)
    
    # print(A)
    J = [0]
    maxlen = len(str(bin(2**len(A)-1).replace('0b','')))
    for j in reversed((range(2**len(A)))):
        tempb = str(bin(j).replace('0b',''))
        for i in range(maxlen - len(tempb)):
            tempb = '0'+tempb
        # ここでパターン仮置き確定
        tempj = list(map(int, list(tempb)))
        counter = 0
        for jj in range(len(tempj)):
            if tempj[jj] == 1: # 正直者の場合
                # 証言の数だけループを回す
                shocounter = 0
                for s in range(len(A[jj])):
                    if tempj[A[jj][s][0]-1] != A[jj][s][1]:# 本当は違う
                        break
                    else:
                        shocounter += 1
                if shocounter == len(A[jj]):
                    counter += 1
            else:
                # 証言の数だけループを回す
                shocounter = 0
                for s in range(len(A[jj])):
                    if tempj[A[jj][s][0]-1] == A[jj][s][1]:# 本当はあってる
                        break
                    else:
                        shocounter += 1
                if shocounter == len(A[jj]):
                    counter += 1
        if counter == len(A):
            J.append(tempj.count(1))
    
    list.sort(J, reverse=True)        
    return print(J[0])
    
f()

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    T = [[-1]*n for _ in range(n)]

    k = 1
    i = 1
    while k < len(args):
        a = int(args[k])
        k += 1
        for _ in range(a):
            x, y = map(int, args[k].split())
            T[i-1][x-1] = y
            k += 1
        i += 1

    ret = 0
    for combi in range(2**n):
        J = [None]*n
        for m in range(n):
            U = []

            for j in range(n):
                if T[j][m] == -1:
                    continue

                if (combi >> j) & 1:
                    U.append(T[j][m] == 1)
                else:
                    U.append(T[j][m] == 0)
            if sum(U) == len(U):
                J[m] = sum(U)

        truth = 0
        for b, j in enumerate(J):
            if j and 0 < j:
                truth += 2**b

        if combi == truth:
            ret = max(ret, ('{:b}').format(combi).count('1'))

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
n=int(input())
data=[[]]
for i in range(n):
    a=int(input())
    xy=[list(map(int,input().split())) for i in range(a)]
    data.append(xy)
ans=0
for i in range(2**n):
    lst=[0]
    for j in range(n):
        if (i>>j)&1==1:
            lst.append(1)
        else:
            lst.append(0)
    for j in range(1,n+1):
        for k,l in data[j]:
            if lst[j]!=lst[k]^l:
                continue
            else:
                break
        else:
            continue
        break
    else:
        ans=max(ans,sum(lst))
print(ans)

Submission status: Wrong Answer

Solution code:
def bin_(n):
    return str(bin(n))[2: ]

N = int(input())
syougen = [[] for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        x,y = input().split()
        x,y = int(x)-1,int(y)
        syougen[i].append((x,y))

start = 2**N-1
max_ = 0
for i in range(2**N):
    num = i
    uso = 0
    
    keta=bin(num)[2:]
    
    while(len(keta)<N):
        keta = "0"+keta
    print(keta)
    for j in range(N):
        if(keta[j]=="1"):
            for p in range(len(syougen[j])):
                
                x,y = syougen[j][p]
                if(keta[x] != str(y)):
                    uso = 1
                    break
    
    suuji = str(bin(num))[2:]
    count  = 0
    for i in range(len(suuji)):
        if(suuji[i]=="1"):
            count += 1
            
    if(uso==0):
        max_ = max(max_,count)
        
print(max_)

Submission status: Wrong Answer

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

honest = 0 
all_zero = 0 
for i in range(N):
        for j in range(A[i]):
                if x[i][j][1] == 1:
                        all_zero = 1 
                        for k in x[x[i][j][0] - 1]: 
                                if k == [i + 1, 0]: 
                                        break
                        else:
                                honest += 1
                                continue
                        break
if all_zero:
        print(honest)
else:
        print(1)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

N = int(input())
statements = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split(' '))
        statements[i].append((x, y))

ans = 0
for i in range(2**N):
    assumption = [int(num) for num in bin(i)[2:].rjust(N, '0')]
    appropriate = True
    for j, p in enumerate(assumption):
        for s in statements[j]:
            if (p == 1 and assumption[s[0] - 1] != s[1]) or (p == 0 and assumption[s[0] - 1] == s[1]):
                appropriate = False
                break
        else:
            continue
        break

    if appropriate and ans < assumption.count(1):
        ans = assumption.count(1)

print(ans)

Submission status: Wrong Answer

Solution code:

muzyun = 0
data = {}
num = int(input())
for i in range(num):
    words = int(input())
    for j in range(words):
        a, b = input().split(' ')
        if a not in data:
            data[a] = [b]
        else:
            data[a].append(b)
        #print(str(i+1) + ' ' + str(words) + ' ' + a + ' ' + b)

usotuki = 0
x = 0
#print(data)
for i in data:
    a = sum(list(map(int, data[i])))
    x  = x + a
    #print(data[i])
    #print('%s %d' % ('a = ', a))
    if len(data[i]) != a:
        x  = x + a
        usotuki = usotuki + 1
if x == 0:
    usotuki = usotuki - 1
#print('%s %d' % ('usotuki = ', usotuki))
print(num - usotuki)