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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
A = []
for i in range(N):
	tmp = []
	n = INT()
	shougen = []
	for j in range(n):
		shougen = MAP()
		tmp.append(shougen)
	A.append(tmp)

cand = []
for i in range(2**N):
	shojiki = [0]*N
	for j in range(N):
		if (i>>j & 1):
			shojiki[N-j-1]=1
	cand.append(shojiki)
# print(cand)

ans = []
for c in cand:
	list = [-1]*(N+1)
	success = True
	for idx,a in enumerate(A):
		# idxの人が正直者であると仮定
		if c[idx] == 1:
			for aa in a:
				if list[aa[0]] == -1:
					list[aa[0]] = aa[1]
				else:
					if list[aa[0]]!=aa[1]:
						success=False
		# そうでなければ、その人の発言は無視
		else:
			for aa in a:
				list[aa[0]] = 0 if aa[1] == 1 else 1
	for k in range(len(c)):
		if c[k]==1 and list[k+1]==0:
			success = False
		if c[k]==0 and list[k+1]==1:
			success = False
	if success:
		#print(c, list)
		ans.append(sum(c))
	
#print(ans)
print(max(ans))

Submission status: Runtime Error

Solution code:
p = input()
honest = 0
for j in range(p):
  A = input()
  xy = input()
  arr = [int(i) for i in xy.split('')]
  if(arr[-1]==1):
    honest += 1
print(honest)

Submission status: Runtime Error

Solution code:
num = int(input())
my_list = [u for u in range(1,num+1)]
for i in range(0,num):
    t = int(input())
    for j in range(t):
        lide = input().split()
        x = int(lide[0])
        y = int(lide[1])
        if y==0:
            my_list.remove(x)

print(len(my_list))

Submission status: Runtime Error

Solution code:
n=int(input())
k=[]
for i in [0]*n:
    p=[]
    for j in range(int(input())):
        p+=[int(i)for i in input().split()]
    k.append(p)
q=0
for i in range(2**n):
    s=bin(i)[2:].zfill(n)
    l=1
    for j in range(n):
        p=k[j];t=s[j]
        a,b=p[0],p[1]
        if t=="0":b=1-b
        if s[a-1]!=str(b):
            l=0
    if l==1:
        u=s.count("1")
        if q<u:
            q=u
print(q)

Submission status: Runtime Error

Solution code:
N = int(input())

talk = [[-1 for i in range(N)] for j in range(N)]

for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        talk[i][x-1] = y

ans = 0

for i in range(1 << N):
    honest = []
    ansi = 0
    for j in range(N):
        if(1 << j and i):
            honest.append(1)
        else:
            honest.append(0)

    for j in range(N):
        if(honest[i] == 0):
            continue
        flag = True
        for k in range(N):
            if(honest[k] != talk[j][k] and talk[j][k] != -1):
                flag = False

        if(flag):
            ansi += 1

    ans = max(ans, ansi)

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
lsx = []
lsy = []
ans = 0
if n==1:
    a = int(input())
    x,y=map(int,input().split())
    if y==0:
        print(0)
    else:
        print(1)
else:
    for i in range(n):
        a = int(input())
        for j in range(a):
            x,y = map(int,input().split())
            lsx.append(x)
            lsy.append(y)
            if x in lsx:
                if lsy[lsx.index(x)]!=lsy[-1]:
                    ans+=1
    test=0        
    for i in lsy:
        if i == 0:
            test+=1
    if test==len(lsy):
        print(1)
    else:
        print(n-ans)

Submission status: Runtime Error

Solution code:
2
1
2 0
1
1 0