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:
def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


# numpy and scipy are available for use
import numpy
import scipy
#https://atcoder.jp/contests/abc147/tasks/abc147_c
#HonestOrUnkind2


def best(bm):
    res = [-1] * N
    for i in range(N):
        if (bm & (1 << i) == 0):
            if (res[i] == 1):
                return -1

            res[i] = 0
            continue

        if (res[i] == 0):
            return -1

        res[i] = 1

        for x, y in ts[i]:
            #   print("%d %d %d" % (i, x, y))
            if res[x] == -1:
                res[x] = y
            elif res[x] != y:
                return -1

    cnt = 0

    for v in res:
        if v:
            cnt += 1

    return cnt


# reads a single line
N = gi()
ts = []

for i in range(N):
    ai = gi()
    ts.append([])
    for j in range(ai):
        x = gi() - 1
        y = gi()
        ts[i].append((x, y))

ans = 0
for bitmap in range(1 << N):
    ans = max(ans, best(bitmap))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
testimony = [[] for _ in range(N)]
#print(testimony)
for i in range(N):
 num = int(input())
 for j in range(num):
  person, state = map(int, input().split())
  testimony[i].append([person-1, state])

#print(testimony)

honest = 0
for i in range(1, 2**N):
 flag = 0
 for j in range(N):
  if (i>>j)&1 == 1:
   for x, y in testimony[j]:
    if (i>>x)&1 != y:
     flag = 1
     break
 if flag == 0:
  honest = max(honest, bin(i)[2:].count('1'))

print(honest)

Submission status: Accepted

Solution code:

#人数
N = int(input())

ans = 0

#証言テーブル
syo = [ [] for i in range(N)]

for i in range(N):
    Ai = int(input())
    for j in range(Ai):
        xi,yi = map(int,input().split())
        #xiは添字とずれるので -1 する
        xi -= 1
        syo[i].append([xi,yi])

#bit全探索
for i in range(2**N):
    mujun = True
    for j in range(N):
        #j番目の人が正直者(1)のとき
        if ( (i >> j) & 1):
            #syo[j]に格納された証言の検証を行う
            #証言があっているか
            for x,y in syo[j]:
                if (i >> x) & 1 != y:
                    mujun = False
                    break
    if mujun:
        ans = max(ans,bin(i)[2:].count("1"))

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
ans = 0
evidence = [[] for n in range(N)]

for n in range(N):
    A = int(input())
    for a in range(A):
        lis = list(map(int, input().split()))
        evidence[n].append(lis)

for n in range(1 << N):
    bits = [(n >> i) & 1 for i in range(N)]
    flag = True
    boolean = True
    for i in range(N):
        if (n >> i) & 1 == 0:
            continue
        for x, y in evidence[i]:
            if bits[x-1] == y:
                continue
            flag = False
    if flag:
        ans = max(ans, sum(bits))
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(n):
        # if jth person may be honest, verify testimony of him.
        if (i>>j) & 1 == 1:
            for xy in xys[j]:
                x, y = xy
                if (i>>x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, bin(i).count('1'))
print(ans)

Submission status: Accepted

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

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

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(n):
        # if jth person may be honest, verify testimony of him.
        if (i>>j) & 1 == 1:
            for xy in xys[j]:
                x, y = xy
                if (i>>x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, digitsum(i))
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
X=list()
for i in range(N):
   X.append([])

Y=list()
for i in range(N):
   Y.append([])

for i in range(N):
   A_i=int(input())
   A.append(A_i)

   for j in range(A_i):
      x,y=list(map(int,input().split()))
      X[i].append(x)
      Y[i].append(y)

max_nin=0
#bit全探索
for i in range(1<<N):
   honest_kamo=[]
   for j in range(N):
      if(i>>j)&1:
         honest_kamo.append(j)

   liar_kamo=[c for c in range(N)]
   liar_kamo=list(set(liar_kamo)-set(honest_kamo))
   #print("honest_kamo:",honest_kamo)
   #print("liar_kamo:",liar_kamo)

   flag=True
   for i in honest_kamo:
      for j in range(A[i]):
         if Y[i][j]==1:
            if X[i][j]-1 in liar_kamo:
               flag=False
         elif Y[i][j]==0:
            if X[i][j]-1 in honest_kamo:
               flag=False
   
   #print(flag)
   if flag:
      max_nin=max(max_nin,len(honest_kamo))

print(max_nin)

Submission status: Accepted

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

def digitsum(x, base=2):
    ret = 0
    while x>0:
        ret += x % base
        x = x // base
    return ret

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(n):
        # if jth person may be honest, verify testimony of him.
        if (i>>j) & 1 == 1:
            for xy in xys[j]:
                x, y = xy
                if (i>>x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, digitsum(i))
print(ans)

Submission status: Accepted

Solution code:
import itertools
import queue


def does_contradict(assumed_honest_men):
    table = {i: None for i in range(1, N+1)}
    table.update({man: 1 for man in assumed_honest_men})
    for honest_man in assumed_honest_men:
        for target, flag in testimonies[honest_man]:
            if table[target] is None and flag == 1:
                return True
            elif table[target] is not None and table[target] != flag:
                return True
    return False


N = int(input())
testimonies = dict()
for witness in range(1, N+1):
    testimonies[witness] = list()
    for _ in range(int(input())):
        target, flag = map(int, input().split(" "))
        testimonies[witness].append((target, flag))

for i in range(N+1, 0, -1):
    for assumption in itertools.combinations(range(1, N+1), i):
        if not does_contradict(assumption):
            print(len(assumption))
            exit(0)
else:
    print(0)

Submission status: Accepted

Solution code:
n = int(input())
t = []
for i in range(n):
  m = int(input())
  t.append({})
  for j in range(m):
    x, y = map(int, input().split())
    t[-1][x-1] = y == 1
res = 0
for i in range(1 << n):
  s = [(i & (1 << j)) > 0 for j in range(n)]
  good = True
  for j in range(n):
    if (s[j] and any(t[j][x] != s[x] for x in t[j])) or (not s[j] and all(t[j][x] == s[x] for x in t[j])):
      good = False
      break
  if good:
    res = max(res, sum(1 for x in s if x))
print(res)

Submission status: Accepted

Solution code:
n=int(input())
a=[]
syougen=[]
for i in range(n):
  a+=[int(input())]
  syougen+=[[list(map(int,input().split()))for j in range(a[-1])]]
for i in range(n):
  for j in range(a[i]):
    syougen[i][j][0]-=1
honest=0
for i in range(2**n):
  t=[0]*(n-len(str(bin(i)))+2)+list(map(int,str(bin(i))[2:]))
  flag=1
  for j in range(n):
    if t[j]:
      for k in range(a[j]):
        if t[syougen[j][k][0]]!=syougen[j][k][1]:flag=0
  if flag:
    if honest<t.count(1):honest=t.count(1)
print(honest)

Submission status: Accepted

Solution code:
n = int(input())

a = []
xy = []

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

# print(a)
# print(xy)

ans = 0

for i in range(2 ** n):
    memo = [1] * n
    for j in range(n):
        if (i >> j) & 1:
            memo[n - j - 1] = 0
    # print(memo)

    for p in range(n):
        flag = True
        for q in range(a[p]):
            x = xy[p][q][0] - 1
            y = xy[p][q][1]
            if memo[p] == 1 and memo[x] != y:
                flag = False
                break
            #elif memo[p] == 0 and memo[x] == y:
            #    flag = False
            #    break
        if not flag:
            break

    if flag:
        ans = max(ans, memo.count(1))

print(ans)

Submission status: Accepted

Solution code:
def ints():
  return [int(x) for x in input().split()]
def readi():
  return int(input())

N = readi()
SYOUGEN = [[] for _ in range(N)]

for i in range(N):
  n = readi()
  for _ in range(n):
    x, y = ints()
    x -= 1

    SYOUGEN[i].append((x, y))
  
def num1(f):
  s = 0
  while f>0:
    s += f%2
    f //= 2
  return s

def success(f):
  shoujikimono = []
  for _ in range(N):
    shoujikimono.append(f%2)
    f //= 2

  for i in range(N):
    if shoujikimono[i]:
      for x, y in SYOUGEN[i]:
        if shoujikimono[x]!=y:
          return False
  return True

maxn = 0
for f in range(2**N):
  n = num1(f)
  if success(f):
    maxn = max(maxn, n)


print(maxn)

Submission status: Accepted

Solution code:
n=int(input())
evi=[]
for i in range(n):
    a=int(input())
    l=[list(map(int,input().split())) for i in range(a)]
    evi+=[l]#証言をすべて集める
ans=0
for i in range(2**n):
    mujyun=[]
    h_list=[]
    count=0
    for j in range(n):
        if ((i>>j)&1):#各桁が１かどうか
            count+=1
            mujyun+=[[j+1,0]]#仮定が間違っているとする    
            h_list+=evi[j]#正直者の発言
        else:
            mujyun+=[[j+1,1]]
        
    for k in mujyun:
        if k in h_list:#矛盾が生じる
            count=0
            break
        
    ans=max(ans,count)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = []
proofs = []
for i in range(n):
    A.append(int(input()))
    proof = [tuple(map(int, input().split())) for _ in range(A[i])]
    proofs.append(proof)

def check_amb(true_men, proofs):
    for true_man in true_men:
        proof = proofs[true_man]
        for x, y in proof:
            if (x-1 in true_men) and (y == 0):
                return True
            if (x-1 not in true_men) and (y == 1):
                return True
    return False


max_pat = 0
for i in range(1 << n):
    true_men = []
    for j in range(n):
        if ((i >> j) & 1) == 1:
            true_men.append(j)
    is_amb = check_amb(true_men, proofs)
    if is_amb is False:
        max_pat = max(len(true_men), max_pat)

print(max_pat)

Submission status: Accepted

Solution code:
n = int(input())

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

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

ans = 0

for i in range(1, 2 ** n):
    ok = True
    for j in range(n):
        if (i >> j) & 1 == 0:
            continue
        for x, y in g[j]:
            if (i >> x)& 1 != y:
                ok = False
                break
        if not ok:
            break
    if ok:
        ans = max(ans, bin(i)[2:].count('1'))
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc147/tasks/abc147_c
# 制約が少ない→全探索可能
# 全探索によって矛盾がない場合を探す

# 問題はどうやって矛盾しているかどうかをどうやって判別するか
# katei[i]で1のあるiが成り立っているか確かめれば良い(矛盾しなければ良い)
# つまり、ある人の発言において、正直者ものの{i} in {katei[i]==1}となる
# かつ、不親切ものの{i} not in {j|katei[i]==1}となればよい。


N = int(input())
syoujiki = []
fusin = []
for _ in range(N):
    a = int(input())
    syou = set()
    fusi = set()
    for _ in range(a):
        x, y = list(map(int, input().split()))
        if y == 1:
            syou.add(x - 1)  # 0 based inexにする
        else:
            fusi.add(x - 1)
    syoujiki.append(syou)
    fusin.append(fusi)


def is_ok(n):  # katei[i]はbinaryなのでnで表現しn>>iでアクセスすることにする。
    # 過程集合の作成
    ret = 0
    katei = set()
    for i in range(N):
        if (n >> i) % 2:  # その桁が1なら
            katei.add(i)
            ret += 1

    # for syou, fusi in zip(syoujiki, fusin):
    #     for s in syou:

    for i in katei:  # 仮定でおいたi番目の人の発言を考慮する
        cond1 = syoujiki[i].issubset(katei)  # ここがおかしい。いま言及しているものしか考えられない
        cond2 = fusin[i].isdisjoint(katei)
        # cond1とcond2を最後までみたいすときにtrueにしたい
        # →満たさないときにfalseにする
        if (not cond1) or (not cond2):
            return 0
    return ret


ans = 0
for katei in range(1 << N):
    ans = max(is_ok(katei), ans)

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            for x,y in A[j]:
                if (i >> x) & 1 != y:
                    flag = False
                    break
    if flag:
        ans = max(ans, bin(i)[2:].count("1"))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = [[]] * n
cnt = 0

for i in range(n):
    xy[i] = [list(map(int, input().split())) for j in range(int(input()))]

bit = '0' + str(n) + 'b'
for k in range(2**n):
  cnt_current = 0
  flg = True
  katei = format(k, bit)
  
  for l in range(len(xy)):
    if flg == False:
      break
    if katei[l] == '0':
      continue
    else:
      for m in range(len(xy[l])):
        if int(xy[l][m][1]) != int(katei[xy[l][m][0]-1]):
          flg = False
          break
  if flg == True:
    cnt_current = katei.count('1')
  if cnt_current > cnt:
    cnt = cnt_current
    
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())

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

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

Submission status: Accepted

Solution code:
N = int(input())

shogen = [[] for _ in range(N)]
for i in range(N):
  for j in range(int(input())):
    person, state = map(int, input().split())
    shogen[i].append([person-1, state])

honest = 0
# ビット全探索
for i in range(1, 2**N):
  flag = 0
  # jは桁数
  for j in range(N):
    # iのj桁目が1だったら
    if (i>>j)&1 == 1:
      # j人目の証言を取り出し
      for person, state in shogen[j]:
        # もし証言が不一致ならフラグを立てる?
        if (i>>person)&1 != state:
          flag = 1
          break
  # 証言が一致していたら、honsetの最大値を更新
  if flag == 0:
    honest = max(honest, bin(i)[2:].count('1'))
print(honest)

Submission status: Accepted

Solution code:
n = int(input())

xyss = [[] for i in range(n)]

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

cnt = 0

for i in range(2 ** n - 1, 0, -1):
  b = format(i, '0' + str(n) + 'b')
  ok = True

  for j in range(n):
    if b[j] == "0":
      continue
    
    for xy in xyss[j]:
      x, y = xy[0], xy[1]
      if b[x - 1] != str(y):
        ok = False
        continue
  
  if ok == True:
    num = sum([int(s) for s in list(b)])
    if cnt < num:
      cnt = num
  
print(cnt)

Submission status: Accepted

Solution code:
#参考
#https://atcoder.jp/contests/abc147/submissions/8918513

#　Nは人の数。1~Nの背番号を持つ。　N<=15
N = int(input())

#証言。N個の空配列を作成。
evidences = [[] for _ in range(N)]

#作成した空配列に対し、一人につきA個の証言を格納していく。
# x:人のインデックス。-1して 0 ~ N-1の範囲にしている。
# y:正直者(1)か嘘つき(0)かの情報。
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        evidences[i].append((x - 1, y))

result = 0

#今回の解法Point　Bits探索
#最大で2^15通りなら全探索で良い！
#正直者・嘘つきの情報をN桁の2進数に置き換える。
for i in range(1, 2**N):
    consistent = True
    
    #jは(背番号-1)
    for j in range(N):
      #ビットシフト　iをjビットだけ右>>にずらす。
      #嘘つきと宣言している箇所はスキップ（continue）
        if (i >> j) & 1 == 0:
            continue
            
        #背番号jの人の証言を確認する。
        for x, y in evidences[j]:
          #もし言動に矛盾が生じたら、そのパターンiはbreakさせて、また別のiを調査する
            if (i >> x) & 1 != y:
                consistent = False
                break
        if not consistent:
            break
            
    #もし証言が全て一致した場合のみ、この先のifを通過する
    if consistent:
      #bin(i) で10進数の整数iを2進数に変換
      #その際、0b111111...のように、文頭に数字以外がつくため、
      #数字だけを見たい場合は[2:]をつけて、0bの部分を除外してる
      #
      #その残った文字列に対し、.count('1')で1の数をカウントしている。
        result = max(result, bin(i)[2:].count('1'))
print(result)

Submission status: Accepted

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

ans=0
for i in range(2**n):
	kind_l=[0 for _ in range(n)]
	for j in range(n):
		if ((i>>j) & 1):
			kind_l[j]=1
	flag=True
	for k in range(n):
		if kind_l[k]:
			for m in range(n-1):
				subject=testimony_list[k][m][0]
				judge=testimony_list[k][m][1]
				if subject==-1:continue
				if kind_l[subject]!=judge:
					flag=False
	if flag:
		ans=max(ans,sum(kind_l))
print(ans)

Submission status: Accepted

Solution code:
g = [[-1] * 15 for _ in range(15)]
n = int(input())
for i in range(n):
    m = int(input())
    for j in range(m):
        a, x = map(int, input().split())
        a -= 1
        g[i][a] = x
def count_ones_by_minus(num):
    count = 0
    while num:
        num &= num -1
        count += 1
    return count
ans = 0
for i in range(1 << n):
    d = [0] * 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, count_ones_by_minus(i))
print(ans)

Submission status: Accepted

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

tf = [0]*n
ans = 0
for i in range(2**n):
  for j in range(n):
    if (i >> j) & 1:
      tf[j] = 1
    else:
      tf[j] = 0
  b = 1
  for k in range(n):
    if tf[k] == 1:
      for l in range(a[k]):
        if tf[xy[k][l][0]-1] != xy[k][l][1]:
          b = 0
          break
  if b == 1 and sum(tf) > ans:
    ans = sum(tf)

print(ans)

Submission status: Accepted

Solution code:
# C - HonestOrUnkind2
G = [[-1] * 15 for _ in range(15)]
N = int(input())
for i in range(N):
    Ai = int(input())
    for _ in range(Ai):
        x, y = map(int, input().split())
        G[i][x - 1] = y;
        
ans = 0
for i in range(1<<N):
    d = [0] * N
    for j in range(N):
        if (i>>j&1):  # iのjビット目が1であるかどうか 
            d[j] = 1  #  嘘つきと正直の割り当て
            
    ok = True
    for j in range(N):
        if d[j] == 1:
            for k in range(N):
                if G[j][k] == -1:
                    continue
                if G[j][k] != d[k]:
                    ok = False
    if ok:
        ans = max(ans, bin(i).count('1'))
    
print(ans)

Submission status: Accepted

Solution code:
import sys

def kensho(x,tlist):
    for lis in tlist:
        if((x>>(lis[1]-1)) & 1 == lis[2]):
            pass
        else:
            return -1

    return bin(x).count('1')


def main():
    N = int(input())
    xy=[]
    ans=0

    for i in range(1,N+1):
        An= int(input())
        for j in range(0,An):
            x, y = map(int, input().split())
            xy.append([i,x,y])

    cnt = N

    tlist=[]
    for x in range (2 ** cnt):
        for y in range(cnt):
            if((x>>y) & 1):
                for z in xy:
                    if(z[0]==y+1):
                        tlist.append(z)

        anstack = kensho(x,tlist)
        if(ans<anstack):
            ans=anstack

        del tlist[:]

    print(ans)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
    
################ DANGER ################
test = ""
#test = \
"""
3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0
ans 0
"""

"""
3
1
2 1
1
1 1
1
2 0
ans 2
"""

"""
2
1
2 0
1
1 0
ans 1
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################

n = int(input2())
a = [None] * (n+1)
for i in range(1, n+1):
    ai = int(input2())
    a[i] = [tuple(map(int, input2().split())) for i in range(ai)]
    

def bitsearch(bit, *, start=0):
    end = 2 ** bit
    len0 = len(format(end, "b"))
    return [format(i, "b").zfill(len0) for i in range(start, end)] 


cand = [0]
for b in bitsearch(n):
    lie, i = 0, 1
    while (not lie) and i < n+1:
        for c in a[i]:
            if int(b[i]) and c[1] ^ int(b[c[0]]):
                lie += 1            
        i += 1
        
    if not lie:
        cand.append(b.count("1"))
        
print(max(cand))

Submission status: Accepted

Solution code:
import itertools
import copy

n = int(input())
indexes = [_ for _ in range(1, n+1)]

def ifCorrect(data, fakes):
    answer_sheet = [-1 for i in range(n+1)]
    for i in fakes:
        answer_sheet[i] = 0

    #このあたりで、fakeでない人の情報とも比較して、正直者の証言がそれらのリストと合致しているかを確認すれば良い
    for i in range(len(data)):
        for j in data[i]:
            if not i in fakes:
                if answer_sheet[j[0]] == -1:
                    if j[1] == 0 and not j[0] in fakes:
                        return False
                    else:
                        answer_sheet[j[0]] = j[1]
                elif not answer_sheet[j[0]] == j[1]:
                    return False
                    
    return True

data = [[] for _ in range(n+1)]
for i in range(n):
    id = int(input())
    for _ in range(id):
        x, y = map(int, input().split(" "))
        data[i+1].append([x,y])

fakePersonCount = 0
flag = True
while fakePersonCount <= n and flag:
    comb = itertools.combinations(indexes, fakePersonCount)
    for fakePeople in comb:
        if ifCorrect(data, fakePeople):
            print(n - fakePersonCount)
            flag = False
            break
    fakePersonCount += 1

if flag:
    print(0)

#[[], [[2, 1], [3, 0]], [[3, 1], [1, 0]], [[1, 1], [2, 0]]]

Submission status: Accepted

Solution code:
import itertools
import copy

n = int(input())
indexes = [_ for _ in range(1, n+1)]

def ifCorrect(data, fakes):
    answer_sheet = [1 for i in range(n+1)]
    answer_sheet[0] = -1
    for i in fakes:
        answer_sheet[i] = 0

    #このあたりで、fakeでない人の情報とも比較して、正直者の証言がそれらのリストと合致しているかを確認すれば良い
    for i in range(len(data)):
        for j in data[i]:
            if not i in fakes and not answer_sheet[j[0]] == j[1]:
                return False
                    
    return True

data = [[] for _ in range(n+1)]
for i in range(n):
    id = int(input())
    for _ in range(id):
        x, y = map(int, input().split(" "))
        data[i+1].append([x,y])

fakePersonCount = 0
flag = True
while fakePersonCount <= n and flag:
    comb = itertools.combinations(indexes, fakePersonCount)
    for fakePeople in comb:
        if ifCorrect(data, fakePeople):
            print(n - fakePersonCount)
            flag = False
            break
    fakePersonCount += 1

if flag:
    print(0)

#[[], [[2, 1], [3, 0]], [[3, 1], [1, 0]], [[1, 1], [2, 0]]]

Submission status: Accepted

Solution code:
N = int(input())

testimonies_all = []
for i in range(N):
    A = int(input())
    testimonies = []
    for j in range(A):
        x, y = map(int, input().split())
        testimonies.append((x, y))
    testimonies_all.append(testimonies)

import itertools
assumptions = list(itertools.product((0, 1), repeat = N))

answers = []
for i in assumptions:
    assumptions2 = []
    for j in range(N):
        assumptions2.append((j + 1, i[j]))
        if i[j] == 1:
            for k in testimonies_all[j]:
                assumptions2.append(k)
    assumptions2.sort()
    count = 0
    for j in range(len(assumptions2) - 1):
        if assumptions2[j][0] == assumptions2[j + 1][0] and assumptions2[j][1] != assumptions2[j + 1][1]:
            count += 1
            break
    if count == 0:
        answers.append(sum(i))

print(max(answers))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
N = int(input())
S = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    temp = []
    for _ in range(A):
        temp.append([str(x) for x in input().split()])
        S[i] = temp
ans = 0
for i in range(2 ** N - 1, -1,-1):
    biti = list(bin(i)[2:].zfill(N))
    flag = 0
    for j in range(N):
        if biti[j] == "1":
            for k in S[j]:
                if biti[int(k[0])-1] != k[1]:
                    flag = 1
                    break
        if flag:
            break
    if not flag:    
        biti = np.array(biti)
        ans = max(ans, np.count_nonzero(biti == "1"))
print(ans)

Submission status: Accepted

Solution code:
class Info:
    def __init__(self, A):
        self.A = A
        self.info = [[0] * 2 for i in range(A)]
        for i in range(A):
            x, y = map(int, input().split())
            self.info[i][0] = x - 1
            self.info[i][1] = y

def solve():
    N = int(input())
    infos = []
    for i in range(N):
        A = int(input())
        infos.append(Info(A))
    
    mx = 0
    for i in range(2 ** N):
        isKind = []
        for j in range(N):
            if (i >> j) & 1:
                isKind.append(1)
            else:
                isKind.append(0)
        
        isConsistent = True
        p = 0
        for info in infos:
            for j in range(info.A):
                if isKind[p]==1 and isKind[info.info[j][0]] != info.info[j][1]:
                    isConsistent = False
            p += 1
        
        if isConsistent:
            Nkind = sum(isKind)
            mx  = max(mx, Nkind)


    print(mx)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def main():
    N = int(input())
    A = [None]*N
    X = [None]*N
    Y = [None]*N
    for i in range(N):
        A[i] = int(input())
        x, y = [None]*A[i], [None]*A[i]
        for j in range(A[i]):
            x_, y_ = map(int, input().split())
            x[j] = x_
            y[j] = y_
        X[i] = x
        Y[i] = y

    m = 0
    for table in range(2**N):
        # tableの表のうち
        flag = True
        for i in range(N):
            # iビット目が真ならi番目の人の発言をチェック
            if table & (1 << i):
                for j in range(A[i]):
                    if not ((table >> (X[i][j]-1)) & 1) == Y[i][j]:
                        flag = False
                        break
            if flag == False:
                break
        if flag == True:
            # 矛盾はないのでカウントしてよい。
            tot = 0
            for i in range(N):
                tot += (table >> i) & 1
            m = max(tot, m)

    print(m)
    pass


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import numpy as np
# import scipy as sp

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

ans = 0
for i in range(2 ** n):
    bit = [0] * n
    for j in range(n):
        if ((i >> j) & 1):
            bit[j] = 1

    flag = True
    # print(bit)
    for idx, j in enumerate(bit):
        if not flag:
            break
        if j == 1:
            for k in [x for x in info if x[0] == idx]:
                # print(' ', k)
                if bit[k[1]] != k[2]:
                    flag = False
    if flag:
        ans = max(ans, sum(bit))
    # print(ans)
print(ans)

Submission status: Accepted

Solution code:
import itertools


def main():
    N = int(input())
    remarks = []
    for i in range(N):
        A = int(input())
        remark = []
        for j in range(A):
            x, y = [int(i) for i in input().split()]
            remark.append((x-1, y))
        remarks.append(remark)

    ans = 0
    for is_honest in itertools.product([1, 0], repeat=N):
        # 矛盾があればFalse
        ok = True
        for i, h in enumerate(is_honest):
            if not ok:
                break
            # 正直者でなければスルー
            if h == 0:
                continue
            # 正直者の場合
            # 正直者の発言と審議が一致しているか調べる
            for one_remark in remarks[i]:
                if is_honest[one_remark[0]] != one_remark[1]:
                    ok = False
                    break
        if ok:
            ans = max(ans, sum(is_honest))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def popcnt(n):
    return bin(n).count("1")

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



ans = 0
for i in range(2**N) :
    d = [0 for _ in range(N)]
    for j in range(N) :
        if((i >> j) & 1) :
            d[j] = 1
    flg = True
    for j in range(N) :
        if(d[j]) :
            for k in range(N) :
                if(evi[j][k] == -1): continue
                if(evi[j][k] != d[k]): flg=False
    if(flg) :
        ans = max(ans, popcnt(i))
        
print(ans)