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: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def count_bit_one(bits, n):
    ret = 0
    for keta in range(n):
        if bits & 2**keta:
            ret += 1
    return ret

def is_honest(bits, i):
    return bits & 2**i != 0

n = int(input())
aaa = [None] * n
for i in range(n):
    a = int(input())
    aaa[i] = [ get_nums_l() for _ in range(a)]

# log(aaa)

ans = -1
# 0:不親切 1:正直
for bits in range(2**n):
    ng = False
    for keta in range(n):
        if is_honest(bits, keta):
            for a in aaa[keta]:
                if is_honest(bits, a[0]-1) != (a[1]==1):
                    ng = True
                    break
        if ng:
            break
    if not ng:
        # log("OK:", bits)
        ans = max(ans, count_bit_one(bits, n))

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[0 for j in range(N)]
B=[[] for j in range(N)]
for i in range(N):
 A[i]=int(input())
 for j in range(A[i]):
  x,y=map(int,input().split())
  B[i].append([x,y])
F=0
for i in range(2**N):
 E=0
 Sui=[0]*N
 for j in range(N):
  if ((i >> j) & 1):
   Sui[j]+=1
 E=0
 for k in range(N):
  if Sui[k]==0:
   E+=1
  else:
   D=0
   for l in range(A[k]):
    if (Sui[B[k][l][0]-1]+B[k][l][1])%2==0:
     D+=1
   if D==A[k]:
    E+=1
 if E==N:
  H=0
  for h in range(N):
   H+=Sui[h]
  F=max(F,H)
print(F)

Submission status: Accepted

Solution code:
n = int(input())
tests = []
for i in range(n):
    a = int(input())
    xys = [ list(map(int, input().split())) for j in range(a) ]
    tests.append(xys)

patterns = []
def dfs(N, li):
    if len(li) == N:
        patterns.append(li)
        return
    for i in range(2):
        new = li[::]
        new.append(i)
        dfs(N, new)
dfs(n, [])
ans = 0
for pattern in patterns:
    contradict = False
    for i in range(len(pattern)):
        if pattern[i] == 0:
            continue
        test = tests[i]
        for xy in test:
            x = xy[0]-1
            y = xy[1]
            if pattern[x] != y:
                contradict = True
                break
        if contradict:
            break
    if contradict:
        continue
    ans = max(ans, sum(pattern))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a_list_sum = []
for i in range(n):
    a_tmp=int(input())
    a_list_tmp=[list(map(int,input().split())) for _ in range(a_tmp)]
    a_list_sum_tmp=[]
    a_list_sum_tmp.append(a_tmp)
    a_list_sum_tmp.append(a_list_tmp)
    a_list_sum.append(a_list_sum_tmp)
    
import itertools
L = [0, 1] #生成する数字
bit_list = list(itertools.product([0, 1], repeat=n))

#bit全探索
for i in range(len(bit_list)):
    count = 0
    #証言者
    for j in range(len(a_list_sum)):
        #正直者について
        if bit_list[i][j] == 1:
            #証言数
            for k in range(len(a_list_sum[j][1])):
                #対象者
                person_id = a_list_sum[j][1][k][0] - 1
                #審議
                is_honest = a_list_sum[j][1][k][1]
                #countが増えることが食い違いを生む
                if bit_list[i][person_id] != is_honest:
                    count += 1
    if count == 0:
        ans = sum(bit_list[i])
print(ans)

Submission status: Accepted

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

def A(s):
    count = 0
    for j in range(n):
        if s[j] == 1:
            count += 1
            for k in range(len(xy[j])):
                if s[xy[j][k][0]] != xy[j][k][1]:
                    return 0
    return count

ans = 0

for i in range(2 ** n):
    ss = []
    for h in range(n):
        if ((i >> h) & 1):
            ss.append(1)
        else:
            ss.append(0)
    ans = max(ans, A(ss))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
people = []
for _ in range(N):
    A = int(input())
    ts = []
    for _ in range(A):
        x, y = map(int, input().split())
        x -= 1
        ts.append((x, y))
    people.append(ts)

ans = 0
for bit in range(1, (1 << N)):
    ok = True
    count = 0
    for i in range(N):
        if bit & (1 << i):
            count += 1
            for x, y in people[i]:
                if (bit & (1 << x) > 0) != (y == 1):
                    ok = False
                    break
            if not ok:
                break
    if ok and ans < count:
        ans = count
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
  m = int(input())
  for _ in range(m):
    x,y = map(int,input().split())
    x -= 1
    A[i].append((x,y))
ans = 0

for i in range(1<<N):
  d = [0]*N
  for j in range(N):
    if (i>>j&1):
      d[j] = 1
  flag = True
  for j in range(N):
    if d[j]:
      for k,l in A[j]:
        if d[k] == l:
          continue
        if d[k] != l:
          flag = False
      if not flag:
        break
  if flag:
    ans = max(ans,sum(d))
print(ans)

Submission status: Accepted

Solution code:
from itertools import *
n = int(input())
xy =[]
for i in range(n):
    tmp = int(input())
    testimony = []
    for j in range(tmp):
        testimony.append(list(map(int, input().split())))
    xy.append(testimony)
ans = 0
for p in product([0,1],repeat=n):

    flag = True
    if sum(p) <= ans:
        continue
    for i in range(n):
        if p[i] == 0:
            continue
        for test in xy[i]:
            if p[test[0]-1] != test[1]:
                flag = False
    if flag:
        ans = sum(p)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

s =[[] for _ in range(n)]

for i in range(n):
    a_tmp = int(input())
    for _ in range(a_tmp):
        x,y = map(int,input().split())
        s[i].append([x,y])

#print(s)

mx = 2**n


def hantei(num):
    flag=0
    bi =[0 for _ in range(n)]
    for j in range(n):
        bi[j] = (num>>j)%2
    
    for j in range(n):
        if((num>>j)%2 == 1):
            for x,y in s[j]:
                if(y != bi[x-1]):
                    flag = 1
                    return flag
    
    return flag

ans = 0 
for i in range(mx):
    if(hantei(i) == 0):
        #print(i)
        ans = max(ans,bin(i)[2::].count("1"))
        
print(ans)

#print(bin(3)[2::].count("1"))
#print(hantei(3))

Submission status: Accepted

Solution code:
n=int(input())
a=[0]*n
x=[0]*n
y=[0]*n
for i in range(n):
  a[i]=int(input())
  x[i]=[0]*a[i]
  y[i]=[0]*a[i]
  for j in range(a[i]):
    x[i][j],y[i][j]=map(int,input().split())
#print(a)
#print(x)
#print(y)

pattern=[]
ans=0
for i in range(2**n):
  tmp=[0]*(n)
  for j in range(n):
    if i>>j & 1:
      tmp[j]=1
  pattern.append(tmp)
  #print(pattern[i])
  count=0
  flag=-1
  for j in range(n):
    if (pattern[i][j]==1):
      if (flag==-1):
        flag=0
      for k in range(a[j]):
          if (y[j][k]!=pattern[i][x[j][k]-1]):
            flag=1
            #print("x[j][k]",x[j][k],"y[j][k]",y[j][k])
      #print("for end")
  if (flag==0):
    count=sum(pattern[i])
    #print(j,flag)
  ans=max(ans,count)
  
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
testimony = [[] for _ in range(N)]

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

Submission status: Accepted

Solution code:
#abc147c
n=int(raw_input())
p=[[] for i in range(n)]
for i in range(n):
 a=int(raw_input())
 for j in range(a):
  p[i].append(map(int,raw_input().split()))
res=0
for i in range(2**n):
 a=[(i>>j) & 1 for j in range(n-1,-1,-1)]
 x=1
 for k in range(n):
  if a[k]*x==1:
   for l in p[k]:
    if a[l[0]-1]!=l[1]:
     x=0
 res=max(res,x*sum(a))
print res

Submission status: Accepted

Solution code:
def resolve():
    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 p in range(2**N):
        ok = True
        for i in range(N):
            for x, y in L[i]:
                if p & (1 << i):
                    if p & (1 << (x-1)) > 0 and y == 0:
                        ok = False
                        break
                    elif p & (1 << (x-1)) == 0 and y == 1:
                        ok = False
                        break

            if not ok:
                break

        if ok:
            ans = max(ans, bin(p).count('1'))

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
a_list = []
for i in range(n):
  a = int(input())
  list_ = []
  for _  in range(a):
    tuple_a = list(map(int,input().split()))
    list_.append(tuple_a)
  a_list.append(list_)
case_list = []
for i in range(2**n):
  case = [0 for i in range(n)]
  for j in range(n):
    if ((i >> j) & 1): 
      case[j] = 1
  case_list.append(case)

ok_case = []
for case in case_list:
  frug = True
  for i  in range(n):
    if case[i] == 1:
      cheker = a_list[i]
      for c in cheker :
        if c[1] != case[c[0] - 1]:
          frug = False
  if frug == True:
    ok_case.append(case)
result_list = []
for ok in ok_case:
  result_list.append(sum(ok))
print(max(result_list))

Submission status: Accepted

Solution code:
N = int(input())
box = []
for i in range(N):
    temp = int(input())
    box.append([])
    for _ in range(temp):
        box[i].append(list(map(int, input().split())))


ans = 0


# bit全探索
for i in range(2 ** N):
    temp = [True for _ in range(N)]
    flg = True
    for j in range(N):
        if ((i >> j) & 1):
            temp[j] = True
                
        else:
            temp[j] = False
        
    for nn, n in enumerate(temp):
        if n:
            for l, m in box[nn]:
                if m == 0:
                    if temp[l-1]:
                        flg = False
                        break
                else:
                    if not temp[l-1]:
                        flg = False
                        break
            
    if flg:
        ans = max(ans, temp.count(True))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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


def judge(bit):
    for i in range(N):
        if not (bit & (1 << i)):
            continue
        for x, y in XY[i]:
            if y == 1 and (not (bit & (1 << x))):
                return False
            if y == 0 and (bit & (1 << x)):
                return False
    return True


ans = 0
for bit in range(1 << N):
    if (judge(bit)):
        # print('bit', bit, bin(bit))
        cnt = 0
        for i in range(N):
            if (bit & (1 << i)):
                cnt += 1
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

S=[[-1]*N for _ in range(N)]
for i in range(N):
  A=int(input())
  for _ in range(A):
    x, y=map(int, input().split())
    S[i][x-1]=y
ans=0   
for s in range(2**N):
  ok=True
  for i in range(N):
    #正直者について見ていく
    if (s>>i&1)==1:
      for j in range(N):
        #それぞれ正直者の証言が矛盾ないか
        if S[i][j]!=-1 and (s>>j&1)!=S[i][j]:
          ok=False
  if ok:
    ans=max(ans, bin(s).count("1"))
    
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

g = [[-1 for j in range(n)] for i in range(n)]

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

ans = 0
for s in range(2**n):
	ok = True
	for i in range(n):
		if (s>>i&1) == 1:
			for j in range(n):
				if g[i][j] != -1 and (s>>j&1) != g[i][j]:
					ok = False
	if ok:
		ans = max(ans, bin(s).count("1"))

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    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 p in range(1, 2**N):
        isOk = True
        for i in range(N):
            for x, y in L[i]:
                if p & (1 << i):
                    if p & 1 << (x-1) and not y:
                        isOk = False
                        break
                    elif not(p & 1 << (x-1)) and y:
                        isOk = False
                        break

                if not isOk:
                    break

        if isOk:
            ans = max(ans, bin(p).count('1'))

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
w = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        w[i].append([int(x) for x in input().split()])

ans = 0
for i in range(2**n):
    flag = 1
    f = [0]*n
    num = 0
    for j in range(n):
        if i & 1<<j:
            f[j] = 1
            num += 1
    for j in range(n):
        if f[j]==1:
            for k in w[j]:
                if k[1]!=f[k[0]-1]:
                    flag = 0
    
    if flag == 1:
        ans = max(ans,num)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

g = [[-1]*n for i in range(n)]

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

ans = 0
for s in range(2**n):
	ok = True
	for i in range(n):
		if (s>>i&1) == 1:
			for j in range(n):
				if g[i][j] == -1: continue
				if (s>>j&1) != g[i][j]: ok = False
	if ok:
		ans = max(ans, bin(s).count("1"))

print(ans)

Submission status: Accepted

Solution code:
def judge(bit): #選び方をひとつ固定
  ok = True
  for i in range(n):
    if ((bit >> i) & 1) == 1: #正直者なら確かめる
      for j in range(len(li[i])):
        x = li[i][j][0]
        y = li[i][j][1]
        if y == 1 and ((bit >> (x-1)) & 1) == 0:
          ok = False
        if y == 0 and ((bit >> (x-1)) & 1) == 1:
          ok = False
  return ok
n = int(input())
li = []
ans = 0
for i in range(n):
  a = int(input())
  xy =  [list(map(int, input().split())) for _ in range(a)]
  li.append(xy)
for bit in range(1<<n):
  if judge(bit):
    cnt = 0
    for i in range(n):
      if ((bit >> i) & 1) == True:
        cnt += 1
    ans = max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ls = []
for i in range(n):
    a = int(input())
    p = []
    for _ in range(a):
        x,y = map(int,input().split())
        p.append([x-1,y])
    ls.append(p)
ans = 0

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    testimony = [[] for i in range(N)]
    for i in range(N):
        for j in range(int(input())):
            x,y = map(int,input().split())
            testimony[i].append([x-1,y])##0-indexに直す
    
    ans = 0
    for i in range(2**N):##証言について、2^N通り
        for j in range(N):##N人について検証
            flag = True
            if (i>>j)&1:##正直者である場合
                for x,y in testimony[j]:
                    if ((i>>x)&1) != y:##嘘をついている
                        flag = False
                        break
                if not flag:
                    break        
        if flag:##全員正直であった場合
            tmp = list(bin(i))
            ans = max(ans,tmp[2:].count("1"))

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

g = [[-1 for j in range(n)] for i in range(n)]

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

ans = 0
for s in range(2**n):
	ok = True
	for i in range(n):
		if (s>>i&1) == 1:
			for j in range(n):
				if g[i][j] == -1: continue
				if (s>>j&1) != g[i][j]: ok = False
	if ok:
		ans = max(ans, bin(s).count("1"))

print(ans)

Submission status: Accepted

Solution code:
import itertools
 
n = int(input())
l =[]
 
for _ in range(n):
  a = int(input())
  m = []
  for _ in range(a):
    xn, yn = map(int, input().split())
    m.append([xn-1, yn])
  l.append(m)
 
for i in itertools.product([1, 0], repeat=n):
  i = list(i)
  flg = 0
  for j in range(n):
    for x, y in l[j]:
      if i[j] == 1 and i[x] != y:
        flg += 1
        break
  if flg == 0:
    break
    
print(sum(i))

Submission status: Accepted

Solution code:
import itertools
 
n = int(input())
l =[]
 
for _ in range(n):
  a = int(input())
  m = []
  for _ in range(a):
    xn, yn = map(int, input().split())
    m.append([xn-1, yn])
  l.append(m)
 
for i in itertools.product([1, 0], repeat=n):
  i = list(i)
  flg = 0
  for j in range(n):
    for k in l[j]:
      if i[j] == 1:
        if i[k[0]] != k[1]:
          flg += 1
          break
  if flg == 0:
    break
    
print(sum(i))

Submission status: Accepted

Solution code:
import itertools

n = int(input())
l =[]

for _ in range(n):
  a = int(input())
  m = []
  for _ in range(a):
    xn, yn = map(int, input().split())
    m.append([xn-1, yn])
  l.append(m)

for i in itertools.product([1, 0], repeat=n):
  i = list(i)
  flg = 0
  for j in range(n):
    for k in l[j]:
      if i[j] == 1:
        if i[k[0]] != k[1]:
          flg += 1
          break
      if flg != 0:
        break
  if flg == 0:
    break
    
print(sum(i))

Submission status: Accepted

Solution code:
def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

n = iip()
people = []

for i in range(n):
    ret = [None for i in range(n)]
    for j in range(iip()):
        x, y = iip()
        ret[x-1] = y
    people.append(ret)

def collect(mode):
    mode = bin(mode)[2:].zfill(n)
    result = mode.count("1")

    #print(mode)
    for i in range(n):
        if mode[i] == "0":
            continue

        for j, say in enumerate(people[i]):
            if say == 1 and mode[j] == "0":
                return 0
            if say == 0 and mode[j] == "1":
                return 0
    return result


maxx = 0
for i in range(2**(n)):
    maxx = max(maxx, collect(i))

print(maxx)

Submission status: Accepted

Solution code:
# HonestOrUnkind2
# input
N = int(input())
maxlen = len(bin(2**N-1)[2:])
testimonies = []
res = 0

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

    testimonies.append(testimony)

for _ in range(1 << N):
    # 仮定とした正直者と，仮定とした正直者の証言を比較すれば十分であることに注意(仮定により，どうあるべきかは決まっているので)
    ok = True
    ans = [int(e) for e in bin(_)[2:].zfill(maxlen)]
    for i, t in enumerate(ans.copy()):
        if t==1: # 正直者の仮定により証言を検証
            for j, v in enumerate(testimonies[i]):
                if v != -1: # -1は言及なし
                    if ans[j] == -1:
                        ans[j] = v 
                    elif ans[j] != v:
                        ok = False
    # print('modified ans: ', ans)
    if ok:
        # print('here')
        res = max(res, sum(e for e in ans if e==1))
    
    
# output
print(res)

Submission status: Accepted

Solution code:
n=int(input())
A=[[2]*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())
    A[i][x-1]=y
ans=0
for i in range(2**n):
  aa=0
  s=format(i,'18b')
  H=[]
  for j in range(n):
    if s[-1-j]=="1":
      H.append(j)
      aa=aa+1
  h=set(H)
  f=0
  for j in range(len(H)):
    for k in range(n):
      if A[H[j]][k]==2:
        continue
      if A[H[j]][k]==1:
        if k not in h:
          f=1
      else:
        if k in h:
          f=1
  if f==0:
    if aa>ans:
      ans=aa
print(ans)

Submission status: Accepted

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

ans = 0
for bit in range(2**N):
  # 正直者の証言の整合性確認
  are_correct = True
  n_honest = 0
  for i in range(N):
    a = (bit >> i) & 1
    if a == 0:
      continue
    else:
      n_honest += 1
    for j in xy[i]:
      b = (bit >> (j[0]-1)) & 1
      if b != j[1]:
        are_correct = False
  # 整合性の確認が取れた場合，正直者の最大人数を更新
  if are_correct:
    if ans < n_honest:
      ans = n_honest

print(ans)

Submission status: Accepted

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

ans = 0
for bit in range(2**N):
  # 正直者と不親切者の組み合わせ決定
  a = [0] * N
  for i in range(N):
    a[i] = (bit >> i) & 1
  # 正直者の証言の整合性確認
  are_correct = True
  for i in range(N):
    if a[i] == 0:
      continue
    for j in xy[i]:
      if a[j[0]-1] != j[1]:
        are_correct = False
  # 整合性の確認が取れた場合，正直者の最大人数を更新
  if are_correct:
    if ans < sum(a):
      ans = sum(a)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = []
for _ in range(N):
    a = int(input())
    S_ = []
    for _ in range(a):
        S_.append(tuple(map(int,input().split())))
    S.append(S_)

def judge(S,bin):
    #矛盾があるかどうかの判定
    #正直者:1,不親切な人:0
    for i in range(N):
        if bin[i] == 1:
            for j in range(len(S[i])):
                if (S[i][j][1] == 1 and bin[S[i][j][0]-1] != 1) \
                or (S[i][j][1] == 0 and bin[S[i][j][0]-1] != 0):
                    return False
    return True

ans = 0
for i in range(2**N):
    b = bin(i)
    b = b[2:]
    while len(b) < N:
        b = "0"+b
    bit = []
    for j in range(len(b)):
        if b[j] == "0":
            bit.append(0)
        else:
            bit.append(1)
    if judge(S,bit):
        ans = max(ans,sum(bit))

print(ans)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.buffer.readline
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

N = int(input())
ys = [[-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())
        ys[i][x-1] = y
# print(ys)

ans = 0
for b in range(1<<N):
    chk = [-1] * N      # 1: 正直 0:不親切
    flg = True
    for i in range(N):
        if b>>i&1:
            if chk[i] == 0:
                flg = False
                break
            chk[i] = 1
            for j in range(N):
                if ys[i][j] == -1: continue
                if chk[j] != -1 and chk[j] != ys[i][j]:
                    flg = False
                    break
                chk[j] = ys[i][j]
        else:
            if chk[i] == 1:
                flg = False
                break
            chk[i] = 0
    if flg:
        ans = max(ans, sum(chk))    # chk が 1の数
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
testimonies = []
for _ in range(n):
    a = int(input())
    testimony = [list(map(int, input().split()))  for _ in range(a)]
    testimonies.append(testimony)
    
ans = 0
for i in range(2 ** n):
    honesty = [0 for _ in range(n)]
    for j in range(n):
        if ((i >> j) & 1):
            honesty[j] = 1
    #print(f'---- honesty: {honesty} ----')
    
    for j in range(n):
        contradiction = True
        if honesty[j]:
            #print(f'all of what {j+1} said are {testimonies[j]}')
            for testimony in testimonies[j]:
                #print(f'testimony: {testimony[0]} is {testimony[1]}')
                #print(f'fact: {testimony[0]} is {honesty[testimony[0] - 1]}')
                if honesty[testimony[0] - 1] == testimony[1]:
                    continue
                #print('contradiction happened!')
                contradiction = False
                break
            
        if not contradiction:
            break
    
    if contradiction:
        ans = max(ans, honesty.count(1))
    #print(f'ans: {ans}')

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    flag = True
    for j in range(n):
        if (i >> j) & 1 == 0:
            continue
        for k in xy[j]:
            x, y = k[0], k[1]
            if not((1 & (i >> (x-1))) == y):
                flag = False
    if flag:
        ans = max(ans, bin(i).count("1"))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
xy = []
for i in range(N):
  a = int(input())
  A.append(a)
  xykari = []
  for j in range(a):
    xykari2 = list(map(int, input().split()))
    xykari.append(xykari2)
  xy.append(xykari)

ans = 0

for i in range(2**N): # iはケース名
  honest = 0
  ng = 0
  for j in range(N):  # jはケースiでチェックする人j
    if ((i>>j)&1)==0:
      continue        # jが不親切なら次の人（j+1）のチェックに移る
    else:
      for k in range(A[j]):
        taisho = xy[j][k][0] - 1
        if xy[j][k][1] != ((i>>taisho)&1):
          ng = 1
          break
    if ng == 1:
      break
    honest += 1
  if ans < honest and ng == 0:
    ans = honest      # ansを更新

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
xy = []
for i in range(N):
  a = int(input())
  A.append(a)
  xykari = []
  for j in range(a):
    xykari2 = list(map(int, input().split()))
    xykari.append(xykari2)
  xy.append(xykari)

ans = 0

for i in range(2**N): # iはケース名
  honest = 0
  ng = 0
  for j in range(N):  # jはケースiでチェックする人j
    if ((i>>j)&1)==0:
      continue        # jが不親切なら次の人（j+1）のチェックに移る
    else:
      for k in range(A[j]):
        taisho = xy[j][k][0] - 1
        if xy[j][k][1] != ((i>>taisho)&1):
          ng = 1 
    honest += 1
  if ans < honest and ng == 0:
    ans = honest      # ansを更新

print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
evidence = list()
for _ in range(N):
    A_k = int(input())
    A_dict = dict()
    for i in range(A_k):
        x, y = map(int, input().split())
        A_dict[x-1] = y
    evidence.append(A_dict)
    
A = [0, 1]
product = list(itertools.product(A, repeat=N))
count_max = 0
for evi in product:
    check = 0
    for i, e in enumerate(evi):
        if e == 1:
            for k, v in evidence[i].items():
                if evi[k] != v:
                    check = 1
                    break
    if check == 0:
        count = sum(evi)
        if count > count_max:
            count_max = count
print(count_max)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N = inputI()
l = []
for i in range(N):
  a = inputI()
  l.append(inputILL(a))

best = 0
for i in range(pow(2,N)):
  OKAY = True
  count = 0
  temp = i
  while temp:
    temp &= temp -1
    count += 1
  for n in range(N):
    if ((pow(2,n)&i )>> n) & 1:
      for statement in l[n]:
        if ((pow(2,statement[0]-1)&i)>>(statement[0]-1) ) != statement[1]:
          OKAY = False
  if OKAY == True:
    best = max(best,count)

print(best)