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:
# -*- coding: utf-8 -*-
# C

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)
from itertools import product

N = int(input())
A = [0] * N
x = []

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

ans = 0

# for case in list(product([0,1], repeat=N)):
for m in range(2**N):
    # print(case)
    flg = [-1] * N
    cond = True
    for i in range(N):
        if not cond:
            continue
        if m >> i & 1 == 0:
            continue

        for a in range(A[i]):
            c, d = x[i][a]
            c = c-1

            # print(c, d)
            if m >> c & 1 != d:
                cond = False
                # print('矛盾')
    if cond:
        # ans = max(ans, sum(case))
        ans = max(ans, bin(m).count('1'))

print(ans)

Submission status: Accepted

Solution code:
def main():
  n=int(input())
  a=[]
  xy=[]
  for _ in range(n):
    a.append(int(input()))
    xy.append([list(map(int,input().split())) for _ in range(a[-1])])
  ans=0
  for i in range(2**n):
    ch=0
    seen=[0]*n # まず全員を不誠実と仮定
    for j in range(n):
      if ((i>>j) & 1): #正直者だと仮定
        seen[j]=1
    f=True
    j=0
    while j<n and f:
      if seen[j]==1:
        for x,y in xy[j]:
          if seen[x-1]!=y:
            f=False
            break
      j+=1
    if f:
      ans=max(sum(seen),ans)
  print(ans)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
n = int(input())
A = []
xy = []
max = 0
for i in range(n):
  a = int(input())
  A.append(a)
  xy.append([list(map(int,input().split())) for i in range(a)])
for i in range(2**n):
    ls = [0]*n
    check = 0
    for j in range(len(ls)):
        if (i >> j) & 1:
            ls[j] = 1
    for p in range(len(xy)):
      for t in xy[p]:
        if t[1] == 1 and ls[p] == 1:
          if ls[t[0]-1] != 1:
            check = 1
            break
        elif t[1] == 0 and ls[p] == 1:
          if ls[t[0]-1] != 0:
            check = 1
            break
      else:
        continue
      break
    if check == 0:
      if ls.count(1) > max:
        max = ls.count(1)
print(max)

Submission status: Accepted

Solution code:
n = int(input())
A = []
xy = []
max = 0
for i in range(n):
  a = int(input())
  A.append(a)
  xy.append([list(map(int,input().split())) for i in range(a)])
for i in range(2**n):
    ls = [0]*n
    check = 0
    for j in range(len(ls)):
        if (i >> j) & 1:
            ls[j] = 1
    for p in range(len(xy)):
      for t in xy[p]:
        if t[1] == 1 and ls[p] == 1:
          if ls[t[0]-1] != 1:
            check = 1
            break
        elif t[1] == 0 and ls[p] == 1:
          if ls[t[0]-1] != 0:
            check = 1
            break
    if check == 0:
      if ls.count(1) > max:
        max = ls.count(1)
print(max)

Submission status: Accepted

Solution code:
N = int(input())

# 証言者ごとに整理する
testimony_list = []
for i in range(N):
    array = [-1] * N
    testimony_list.append(array)
for i in range(N):
    A = int(input())
    for j in range(A):
        x, y = map(int, input().split())
        # iさんの、xさんへの証言
        testimony_list[i][x - 1] = y

max_count = 0
for i in range(2 ** N):
    failed = False
    for j in range(N):
        if not (i >> j & 1):
            continue
        array = testimony_list[j]
        for k in range(N):
            if array[k] != -1 and (i >> k & 1) != array[k]:
                failed = True
                break
    if failed is False:
        max_count = max(max_count, bin(i)[2:].count("1"))
print(max_count)

Submission status: Accepted

Solution code:
N = int(input())
A = []
for i in range(N):
  tmp = int(input())
  tmp_list = []
  for j in range(tmp):
    xy = list(map(int, input().split()))
    tmp_list.append(xy)
  A.append(tmp_list)
ans = 0
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f
for bit in range(2**N):
  flag = True
  for i in range(N):
    if bit >> i & 1:
      for j in range(len(A[i])):
        if (A[i][j][1]^(bit >> (A[i][j][0]-1)&1)):
          flag = False
          break
    else:
      continue
    if not flag:
      break
  if flag:
    ans = max(ans, popcount(bit))
print(ans)

Submission status: Accepted

Solution code:

def main():
    n = int(input())
    ans = []
    for _ in range(n):
        a_num = int(input())
        t = []
        for _ in range(a_num):
            t.append(tuple(map(int, input().split())))
        t = tuple(t)
        ans.append(t)

    r = 0
    for bit in range(1 << n):
        honest = []
        for i1 in range(n):
            mask = 1<<i1
            if bit & mask:
                honest.append(i1)
        flag = 1       
        for eh in honest:
            say = ans[eh]
            for esay in say:
                if esay[0] - 1 in honest:
                    if esay[1] == 0:
                        flag = 0
                else:
                    if esay[1]:
                        flag = 0
        if flag:
            r = max(r, len(honest))
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

# print("")
# 証言者ごとに整理する
testimony_list = []
for i in range(N):
    array = [-1] * N
    testimony_list.append(array)
for i in range(N):
    A = int(input())
    for j in range(A):
        # iさんの、xさんへの証言
        x, y = map(int, input().split())
        # print("test:{} {}".format(x, y))
        # iさんの、xさんへの証言
        # print("test:{} {} {}".format(x - 1, i, y))
        # print(testimony_list)
        testimony_list[i][x - 1] = y

# print(testimony_list)
max_count = 0
failed = False
for i in range(2 ** N):
    results = [-1] * N
    shoujiki = 0
    for j in range(len(testimony_list)):
        # check = (i >> j & 1)
        # print("チェック: {} {}".format(i, j))
        # print(i >> j & 1)
        if i >> j & 1:
            shoujiki += 1
            # print("{}:{}".format(bin(i), j))
            array = testimony_list[j]
            for k in range(len(array)):
                # print(
                #     "k={} result[k]:array[k] {}:{}".format(
                #         k, results[k], array[k]))
                # print(i >> k & 1)
                if not (i >> k & 1) and array[k] == 1:
                    # print("矛盾2")
                    failed = True
                    break
                elif (i >> k & 1) and array[k] == 0:
                    # print("矛盾3")
                    failed = True
                    break
                if array[k] == -1:
                    continue
                if results[k] == -1:
                    results[k] = array[k]
                elif results[k] != array[k]:
                    # print("矛盾1")
                    failed = True
                    break
        if failed is True:
            # print("failed")
            # results = [-1] * N
            break
    if failed is True:
        failed = False
        continue
    # print("計算: {}".format(i))
    # print(results)
    # count = 0
    # for result in results:
    #     if result != -1:
    #         count += 1
    # print(count)
    if max_count < shoujiki:
        max_count = shoujiki
print(max_count)

Submission status: Accepted

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

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)
from itertools import product

N = int(input())
A = [0] * N
x = []

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

# print(x)

ans = 0
for case in list(product([0,1], repeat=N)):
    # print(case)

    flg = [-1] * N
    cond = True
    for i in range(N):
        if not cond:
            continue
        if case[i] == 0:
            continue

        for a in range(A[i]):
            c, d = x[i][a]
            c = c-1

            # print(c, d)
            if case[c] != d:
                cond = False
                # print('矛盾')
    if cond:
        ans = max(ans, sum(case))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
shougen=[[-1]*(n+1) for _ in range(n+2)]
for i in range(1,n+1):
  a = int(input())
  for j in range(a):
    x,y = map(int, input().split())
    # 人iのxに対する証言はy
    shougen[i][x]=y

ans=0
# bit全探索
for i in range(2**n):
  f=True
  for j in range(n):
    if i>>j & 1:
      for k,s in enumerate(shougen[j+1][1:],start=0):
        if s == 1 and not i>>k & 1:
          f=False
        if s == 0 and i>>k & 1:
          f=False
  else:
    if f:
      ans=max(ans, str(bin(i)).count("1"))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
test = []
for i in range(n):
  m = int(input())
  said = [list(map(int, input().split())) for _ in range(m)]
  test.append(said)
  
def NotContradict(i):
  lst = [0]*n
  for j in range(len(bin(i))):
    if (i >> j) & 1:
      lst[j] = 1
  for j in range(n):
    if lst[j]:
      for k in range(len(test[j])):
        if lst[test[j][k][0]-1] != test[j][k][1]: 
          return False
  return True

ans = 0
for i in range(2**n):
  if NotContradict(i):
    count = 0
    for j in range(len(bin(i))):
      if (i >> j) & 1:
        count += 1
    ans = max(ans, count)
        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
shogens = []

for i in range(n):
    a = int(input())
    shogens.append([])

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


def is_honest(i, j):
    return (i >> j) % 2 == 0


def honest_cnt(i):
    ans = 0
    for j in range(n):
        ans += is_honest(i, j)

    return ans


ans = 0
for i in range(1 << n):
    ok = True
    for j in range(n):
        if not is_honest(i, j):
            continue
        for x, y in shogens[j]:
            if y == 0 and is_honest(i, x):
                ok = False
            if y == 1 and not is_honest(i, x):
                ok = False

    if ok:
        ans = max(ans, honest_cnt(i))


print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    res = 0
    for pattern in product([0, 1], repeat=n):
        for idx, p in enumerate(pattern):
            if p == 1:
                for x, y in query[idx]:
                    if pattern[x] != y:
                        break
                else:
                    continue
                break
        else:
            res = max(res, sum(pattern))

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
lst = []

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

ans = 0
# 全探索
# iのビットに含まれる'1'が正直者
# 0000 0000 0000 0001
# ~
# 0111 1111 1111 1111
for i in range(2**n):
    flag = 0
    # 全ての人の証言を検証
    for j in range(n):
        # 正直者か確認(不親切な人の証言はどうでもいい)
        if (i >> j) & 1:
            # 証言の確認
            for x, y in lst[j]:
                # x番の人に対する証言が間違っていれば終了
                if (i >> x) & 1 != y:
                    flag = 1
                    break
    # 全ての正直者の証言に異常がなければ
    if flag == 0:
        # 2進数表記の'1'の数が正直者の数
        ans = max(ans, bin(i).count('1'))
print(ans)

Submission status: Accepted

Solution code:

def main():
  N = int(input())

  ## 証言を入れる
  p = [[-1 for i in range(N)] for j in range(N)]

  ans = 0

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

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


  for i in range(1 << N):
    d = [0] * N

    for j in range(N):
      # 0-indexedで考える
      # 下i桁目を0桁目に持ってきて1と&をとると、i番目の人が正直者のフラグが立っているかどうかが判定できる
      if(i >> j & 1):
        d[j] = 1

    ok = True
    
    for j in range(N):
      if(d[j]):
        for k in range(N):
          if(p[j][k] == -1):
            continue
          if(p[j][k] != d[k]):
            ok = False

    if(ok):
      ans = max(ans, bin(i).count("1"))

  print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

def main():
  N = int(input())

  ## 証言を入れる
  p = [[] for _ in range(N)]

  ans = 0

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

    for j in range(A):
      p[i].append(list(map(int, input().split())))

  for i in range(1 << N):
    d = [0] * N

    for j in range(N):
      # 0-indexedで考える
      # 下i桁目を0桁目に持ってきて1と&をとると、i番目の人が正直者のフラグが立っているかどうかが判定できる
      if(i >> j & 1):
        d[j] = 1

    ok = True
    
    for j, _ in enumerate(p):
      #j人目の証言について確認する
      #j人目に正直者フラグが立っていた時だけ確認すれば良い
      if(d[j]):

        for k, _ in enumerate(p[j]):
          x, y = p[j][k]
          x -= 1
          if(d[x] != y):
            ok = False

    if(ok):
      # あり得る人数を知りたいので条件をパスしたものでbitの1が立っている箇所を調べる
      ans = max(ans, bin(i).count("1"))

  print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
N = int(input())
dic = {}
cnt = 0
ok = []
for i in range(N):
  A = int(input())
  for j in range(A):
    x,y = (int(t) for t in input().split())
    dic[(i,x)] = y
for i in itertools.product([0,1],repeat=N):
  for k in dic.keys():
    if i[k[0]] == 0:
      continue
    if dic[k] != i[k[1]-1]:
      break
  else:
    ok += [i]
mm = 0
for i in ok:
  mm = max(mm,sum(i))
print(mm)

Submission status: Accepted

Solution code:
import itertools
def main():
    N = int(input())
    syougen = [None]
    for _i in range(N):
        A = int(input())
        aa = []
        for _j in range(A):
            aa.append(tuple(int(c) for c in input().split(' ')))
        syougen.append(aa)
    #print(syougen)
    max_t = 0
    for baai in itertools.product([True, False], repeat=N):
        #print(baai)
        mujun = False
        for i in range(1, N+1):
            flag = baai[i-1]
            for x, y in syougen[i]:
                if flag:
                    if y==1 and baai[x-1]==False:
                        mujun=True
                        break
                    elif y==0 and baai[x-1]==True:
                        mujun=True
                        break
        if mujun:
            continue
        else:
            max_t = max(max_t, sum(baai))

    print(max_t)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n = int(input())
dic_ = {}
for i in range(n):
    m = int(input())
    for j in range(m):
        x, y = map(int, input().split())
        dic_[(i,x)] = y

ok = []
for i in itertools.product([0,1],repeat=n):
    for k in dic_.keys():
        if i[k[0]] == 0:
            continue
        if dic_[k] != i[k[1]-1]:
            break
    else:
        ok += [i]
mm = 0
for i in ok:
    mm = max(mm, sum(i))
print(mm)

Submission status: Accepted

Solution code:
n = int(input())
l = [[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):
    m = int(input())
    for j in range(m):
        x,y = [int(i) for i in input().split()]
        l[i][x-1] = y
        
ans = 0
for i in range(1<<n):
    honests = [0 for _ in range(n)]
    for j in range(n):
        if (i >> j) & 1:
            honests[j] = 1
    flg = 1
    for k in range(n):
        if honests[k]:
            for h in range(n):
                if l[k][h] == -1 : continue
                if l[k][h] != honests[h] : flg = 0
    
    if flg:
        ans = max(ans,sum(honests))
        
print(ans)

Submission status: Accepted

Solution code:

n=int(input())
a=[0]*n
x=[[]*n for i in range(n)]
for i in range(n):
    a[i]=int(input())
    for ii in range(a[i]):
        xi,yi=map(int,input().split())
        x[i].append([xi-1,yi])
        
import itertools
ans=0
for i in itertools.product([0,1], repeat=n):
    yn=""
    for j in range(n):
#        print(i,j,"-----------------")
        if i[j]==1:
            for xx in x[j]:
#                print(i[xx[0]]==xx[1],xx)
                if i[xx[0]]!=xx[1]:
                    yn="No"
                    break
#    print(i,"yn:",yn)
    if yn!="No":
        ans=max(ans,sum(i))

print(ans)

Submission status: Accepted

Solution code:
def make_bit(n):
    bit = []
    for i in range(2**n):
        bit.append(bin(i)[2::])
    i = 0
    while i < len(bit):
        while len(bit[i]) < len(bin(2**n-1)[2::]):
            bit[i] = "0" + bit[i]
        i += 1

    return bit

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

# print(xy_list)

bit = make_bit(n)
ans = 0
for i in bit:
    tmp = [0 for _ in range(n)]
    NO = 0
    cnt = 0
    for j in range(n):
        if i[j] == "1":
            cnt += 1
            for x, y in xy_list[j]:
                if y and i[x-1] == "0":
                    NO = 1
                    break
                if not y and i[x-1] == "1":
                    NO = 1
                    break
        if NO:
            break

    if not NO:
        # print(i, tmp)
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import itertools


def main():
    N = int(input())
    # testimony[i][y]: person list which i-th person says that is y (1: honest, 0: non-honest)
    testimony = [[[] for _ in range(2)] for _ in range(N)]
    for i in range(N):
        A = int(input())
        for _ in range(A):
            x, y = list(map(int, input().split(' ')))
            x -= 1
            testimony[i][y].append(x)
    # Check each honesty pattern
    max_honest = 0
    for pattern in itertools.product([0, 1], repeat=N):
        num_honest = sum(pattern)
        if max_honest > num_honest:
            continue
        is_valid = True
        for i, y in enumerate(pattern):
            # i-th person is y
            if y == 0:
                # skip testimony of non-honest person
                continue
            for yy in [0, 1]:
                ith_testimony = testimony[i][yy]
                for j in ith_testimony:
                    if pattern[j] != yy:
                        is_valid = False
                        break
                if not is_valid:
                    break
            if not is_valid:
                break
        if is_valid:
            max_honest = sum(pattern)
    print(max_honest)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
def dfs(i,tf):
    global ans
    if i == n:
        ok = True
        for j,a in enumerate(tf):
            if a == True:
                for x,y in shogen[j]:
                    if tf[x-1] == y:
                        pass
                    else:
                        ok = False
        if ok==True:
            ans = max(ans,tf.count(1))
        return
    else:
        dfs(i+1,tf+[True])
        dfs(i+1,tf+[False])

dfs(0,[])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
XY = [[] for _ in range(N)]
for i in range(N):
    c = int(input())
    XY[i] = [[int(j) for j in input().split()] for _ in range(c)]

"""
・N < 15
・O(N * 2^N)
"""


def popcnt(n):
    return bin(n).count('1')


def func(bits):
    for i in range(N):
        if (bits >> i) & 1 == 0:
            continue
        for x, y in XY[i]:
            x -= 1  # 0-indexed
            if (bits >> x) & 1 != y:
                return False
    return True


ans = 0
for mask in range(1 << N):
    if func(mask):
        tmp = popcnt(mask)
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(input())
XY = [[] for _ in range(N)]
max_honest = 0

for i in range(N):
    A = int(input())
    for j in range(A):
        xy = list(map(int,stdin.readline().rstrip().split()))
        XY[i].append(xy)

for i in range(2**N):
    honest = True
    bin_list = list(format(i,'015b'))
    bin_list.reverse()
    for j in range(N):
        if bin_list[j] == '1':
            for p in XY[j]:
                if int(bin_list[p[0]-1]) != p[1]:
                    honest = False
    if honest:
        max_honest = max(max_honest,bin_list.count('1'))

print(max_honest)

Submission status: Accepted

Solution code:
# Problem C - HonestOrUnkind2

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

# initialization
pattern = []
for i in range(2**N):
    p = [0]*N
    for j in range(N):
        if (i>>j)&1==1:
            p[j] = 1
    pattern.append(p)
max_count = 0

# count
for p in pattern:
    is_ok = True
    num_count = 0
    for i in range(N):
        # 正直者であればチェック
        if p[i]==1:
            num_count += 1
            shogen = shogen_list[i]
            if len(shogen)==0:
                continue
            else:
                for s in shogen:
                    x = s[0]
                    y = s[1]
                    if not p[x-1]==y:
                        is_ok = False
                        break
    if is_ok:
        max_count = max(max_count, num_count)

# output
print(max_count)

Submission status: Accepted

Solution code:
N=int(input())
tlst=[]

for i in range(N):
    t=int(input())
    tlst.append([list(map(int,input().split())) for _ in range(t)])
ans=0
for i in range(2**N):
    bit=[0]*N
    cnt=0
    for j in range(N):
        if (i>>j)&1==1:
            bit[j]=1
            cnt+=1
    
    for j in range(N):
        if bit[j]==1:
            for xt,yt in tlst[j]:
                if bit[xt-1]!=yt:
                    cnt=-1
                    break
            
            if cnt==-1:
                break
    
    ans=max(ans,cnt)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = []
xy = []
for i in range(N):
    a = int(input())
    A.append(a)
    temp = []
    for j in range(a):
        x,y= map(int,input().split())
        temp.append((x,y))
    xy.append(temp)

ans = 0
for i in range(2**N):
    b = bin(i)[2:].zfill(N)
    valid = True
    for i in range(N):
        if b[i] == '0':
            continue
        else:
            for x,y in xy[i]:
                if int(b[x-1]) != y:
                    valid = False
                    break
    if valid:
        ans = max(ans, b.count('1'))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
x = []
for i in range(n):
    a = int(input())
    tmp = [list(map(int, input().split())) for _ in range(a)]
    x.append(tmp)
    
max_ = 0
for bit in range(1 << n):
#     print(bin(bit))
    flag = 0
    cnt = 0
    for i in range(n):
        if (bit & (1<<i)):
#             print("honest",i)
            cnt += 1
            for v in x[i]:
                if bool(bit & (1<<(v[0] - 1))) != bool(v[1]):
#                     print("    ng",v[0] - 1,bit & (1<<(v[0] - 1)),v[1])
                    flag = 1
                    break
            if flag == 1:
                break
#             print("    ok",v[0] - 1,bit & (1<<(v[0] - 1)),v[1])
    if flag == 0:
        if max_ < cnt:
#             print("renew")
            max_ = cnt
print(max_)

Submission status: Accepted

Solution code:
n=int(input())#11:02
facts=[]
lies=[]
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

for i in range(n):
    fact=0
    lie=0
    q=int(input())
    for j in range(q):
        x,y=map(int,input().split())
        if y==0:
            lie+=1<<(x-1)
        else:
            fact+=1<<(x-1)
    lies.append(lie)
    facts.append(fact)

ans=0
for i in range(1<<n):
    flag=True
    for j in range(n):
        if i&(1<<j):
            fact=facts[j]
            lie=lies[j]
            if (fact != (fact&i)) or (lie!=(lie&~i)):
                flag=False
                break
    if flag:
        ans=max(ans,popcnt(i))
print(ans)
"""
3
3
1 1
2 1
3 1
1
1 1
1
1 1

"""

Submission status: Accepted

Solution code:
def main():
    hatsugen_dic = {}
    inlis = []
    anslis = []

    n= int(input())
    for s in range(n):
        a = int(input())
        for _ in range(a):
            inlis.append(list(map(int, input().split())))
        hatsugen_dic[s] = inlis
        #print(s, inlis)
        inlis = []
    #print(hatsugen_dic)

    for i in range(2**n - 1, -1, -1):   #iは正直/嘘を全列挙（人数n人に対して2^n個のケースを順番に試す）
        cnt = 0
        for j in range(n):              #jはj番目の発言者の辞書から発言リストを取り出し、それぞれiのケースと正しいかを見る
            #print(i, j)
            if ((i >> j) & 1):          #iを二進数でj桁ずらした時に、1（正直者）かどうかチェック。1ならばチェック、0ならシカト
                hatsugen_j = hatsugen_dic[j]            #hatsugen_dicからj番目の発言のリストを取得
                for k in range(len(hatsugen_j)):        #kはjの発言の個数。何人分言及しているかをリスト内のものすべてで探索
                    if ((i>>(hatsugen_j[k][0]-1)) + hatsugen_j[k][1]) % 2 == 0:
                        #print(i, j, k, lis_j, lis_j[k][0], lis_j[k][1])
                        pass
                    else:
                        #print("i>>lis_j[k][0]-1:", (i + hatsugen_j[k][1]) % 2)
                        #print(i, j, k, lis_j, lis_j[k], lis_j[k][0], lis_j[k][1] , cnt)
                        cnt += 1
        if cnt == 0:
            count = 0
            while i:
                count += i & 1
                i >>= 1
            #print(count)
            anslis.append(count)
    print(max(anslis))




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a = [0]*20
x=[[0 for i in range(20)]for j in range(20)]
y=[[0 for i in range(20)]for j in range(20)]
 
for i in range(n):
	a[i]=int(input())
	for j in range(a[i]):
		x[i][j], y[i][j] = map(int,input().split())
		x[i][j]-=1
 
ans=0
for bits in range(1<<n):
	isok=True
	for i in range(n):
		if (bits>>i)&1 == 0:
			continue
		for j in range(a[i]):
			if y[i][j]^((bits>>x[i][j])&1):
				isok=False
	if isok:
		tmp=bits
		an=0
		while(tmp):
			if tmp&1:
				an+=1
			tmp//=2
		ans = max(ans,an)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
#S=  [ [-1] * N for i in range(N)]
S=[ [] * N for i in range(N)]
#print(S)
for i in range(N):
  a=int(input())
  for j in range(a):
    x,y=map(int,input().split())
    #S[i][x-1]=y
    S[i].append([x-1,y])
#print(S)
ans=0
P=[0]*N
#print(P)
for i in range(2**N):
  tmp=0
  for j in range(N):
    if P[j]==0:
      P[j]=1
      break
    else:
      P[j]=0
  #print(P,sum(P))
  if sum(P)<=ans:
    continue
  flag=0
  for p in range(len(P)):
    if P[p]==1:
      for s in S[p]:
        if s[1]!=P[s[0]]:
          flag=1
  if flag==1:
    continue
  else:
    ans=sum(P)
print(ans)

Submission status: Accepted

Solution code:
ii = lambda:int(input())
li = lambda:list(map(int,input().split()))
lix = lambda x:list(li() for _ in range(x))
##########
def main(n,a):
    res = 0
    ran = 2**n
    for tar in range(1,ran):
        check = True
        for i in range(n):
            if tar>>i & 1 and not isHonest(tar, a[i]):
                check = False
                break
        if check : res = max(res, count(tar,n))
    return res                

def count(tar, n):
    res = 0
    for i in range(n):
        if tar>>i & 1 : res += 1
    return res

def isHonest(tar, a):
    res = True
    for i in range(len(a)):
        x,y = a[i]
        if tar>>(x-1) & 1 != y : return False
    return True

n = ii()
a = []
for i in range(n):
    c = ii()
    a.append(lix(c))
print(main(n,a))

Submission status: Accepted

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

ans = 0
for j in range(2**N):
  x = 0
  for k in range(N):
    if ((j >> k) & 1):
      for l in range(len(List[k])):
        if ((j >> (List[k][l][0]-1)) & 1) != List[k][l][1]:
          break
      else:
        x += 1
        continue
      break
  else:
    if ans < x:
      ans = x
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ls = []
for i in range(n):
    a = int(input())
    p = []
    for i 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'))#2進数表記の'1'の数が正直者の数
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0
for i in product([1, 0], repeat=n):
    s = True
    for j in data:
        if i[j[0]] == 1 and i[j[1]] != j[2]:
            s = False
            break
    if s:
        ans = max(ans, sum(i))
print(ans)