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:
N = int(input())
A = [] #どこからどこまでがiさんの証言かN×2の配列
tes = []#証言を入れていく
pro_sta = []#過程の状態
tes_count = 0
suc_flag = 1 #矛盾が生じてなければ1
max_honest = 0

# 入力受け取り
for i in range(N):
    a = int(input())
    A.append([tes_count,tes_count + a])
    tes_count += a
    for k in range(a):
        x,y = list(map(int,input().split()))
        tes.append([x,y])

t = (2 ** N)
for p in range(t):
    pro_sta = []
    suc_flag = 1
    t_str = str(format(p,"0"+str(N)+"b"))
    for q in range(N):
        pro_sta.append(t_str[q])

    for q in range(N):
        if pro_sta[q] == "1":
            for r in range(A[q][0],A[q][1]):
                if tes[r][1] != int(pro_sta[tes[r][0] - 1]):
                    suc_flag = 0
    if suc_flag == 1:
        honest_count = pro_sta.count("1")
        max_honest = max(max_honest,honest_count)

print(max_honest)

Submission status: Accepted

Solution code:
N = int(input())
XY = []
for i in range(N):
    XY.append([])
    A = int(input())
    for a in range(A):
        x, y = map(int, input().split())
        XY[i].append([x, y])

answer = 0
for p in range(0, 2**N):
    ok = True
    h = 0
    for i in range(N):
        if p & (1 << i):
            h += 1
            for x, y in XY[i]:
                x -= 1
                if y == 0: # unkind
                    if p & (1 << x):
                        ok = False
                if y == 1: # x is honest
                    if not p & (1 << x):
                        ok = False
    if ok:
        answer = max(answer, h)
print(answer)

Submission status: Accepted

Solution code:
#入力はn人のx,yに分けないといけない
n = int(input())
a = []
x = [[] for i in range(n)]
y = [[] for i in range(n)]
for i in range(n):
    a.append(int(input()))
    for j in range(a[i]):
        xx, yy = (int(i) for i in input().split())
        x[i].append(xx)
        y[i].append(yy)

testimony = [[2]*n for i in range(n)]

for i in range(n):
    for j in range(a[i]):
        if (y[i][j] == 1):
            testimony[i][x[i][j] - 1] = 1
        elif(y[i][j] == 0):
            testimony[i][x[i][j]-1] = 0

ans = 0
for i in range(2**n):
    bit_list = []
    for j in range(n):
        if ((i >> j) & 1):
            bit_list.append(1)
        else:
            bit_list.append(0)
    flag = 1
    for k in range(n):
        if(bit_list[k] == 1):
            for l in range(n):
                if(testimony[k][l] != 2):
                    if(testimony[k][l] != bit_list[l]):
                        flag = 0
                        break
    if(flag == 1):
        ans = max(sum(bit_list),ans)
print(ans)

Submission status: Accepted

Solution code:
def max_honest(n_ppl, testimonies):
    formating_str = "{0:0" + str(n_ppl) + "b}"
    max = 0
    for i in range(1, 2**n_ppl + 1):
        current_val = formating_str.format(2**n_ppl - i)
        potential = True
        valid_testemonies = []
        for j in range(0, len(current_val)):
            if current_val[j] == "1":
                for k in range(0, len(testimonies[j])):
                    valid_testemonies.append(testimonies[j][k])
        for j in range(0, len(valid_testemonies)):
            if str(valid_testemonies[j][1]) != current_val[valid_testemonies[j][0] - 1]:
                potential = False
                break
        if potential:
            if current_val.count("1") > max:
                max = current_val.count("1")
    return max

testimonies = []
n_ppl = int(input())

for i in range(0, n_ppl):
    tests = []
    n_tests = int(input())
    for j in range(0, n_tests):
        test = input().split(" ")
        test = (int(test[0]), int(test[1]))
        tests.append(test)
    testimonies.append(tests)
    
print(max_honest(n_ppl, testimonies))

Submission status: Accepted

Solution code:
def ok(n, X, Y, mask):
    for i in range(n):
        for x, y in zip(X[i], Y[i]):
            z = mask & (2**(x-1))
            z = int(z > 0)
            if mask & (2**i):
                if z != y:
                    return False
    return True

def solve(n, X, Y):
    best = 0
    for mask in range(2**n):
        if ok(n, X, Y, mask):
            cnt = 0
            for i in range(n):
                if mask & (2**i):
                    cnt += 1
            best = max(best, cnt)
    return best

n = int(input())
X, Y = [], []
for i in range(n):
    a = int(input())
    x = [0] * a
    y = [0] * a
    for j in range(a):
        x[j], y[j] = map(int, input().split())
    X.append(x)
    Y.append(y)
print(solve(n, X, Y))

Submission status: Accepted

Solution code:
N = int(input())

testimony = [[] for _ in range(N)]

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])
        
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:
        honest = max(honest, bin(i)[2:].count('1'))
print(honest)

Submission status: Accepted

Solution code:
syogens = []
n = int(input())
for i in range(n):
    syogens.append([])
    a = int(input())
    for j in range(a):
        m,s=map(int,input().split())
        syogens[i].append([m,s])
ok = 0
for i in range(2**n):
    ng = False
    i2 = format(i,"b").zfill(16)
    i2 = i2[::-1]
    for k,j in enumerate(syogens):
        if i2[k] == "1":
            for l,j2 in enumerate(j):
                if str(j2[1]) != i2[j2[0]-1]:
                    ng = True
    if ng:
        ng = False
    else:
        if i2.count("1") > ok: ok = i2.count("1") 
print(ok)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    state = [(i>>j)&1 for j in range(N)]
    isOk = True
    for k in range(N):
        if state[k]==0:
            continue
        for x, y in xys[k]:
            if not state[x]==y:
                isOk = False
    if isOk:
        ans = max(ans, sum(state))

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations


def solve():
    N = int(input())
    x = [[] for _ in range(N)]
    y = [[] for _ in range(N)]
    for i in range(N):
        A = int(input())
        xi = [0 for _ in range(A)]
        yi = [0 for _ in range(A)]
        for j in range(A):
            xi[j], yi[j] = map(int, input().split())
            xi[j] -= 1
        x[i] = xi
        y[i] = yi

    ans = 0
    for i in range(1, N+1):
        for honest_peoples in combinations(range(N), i):
            flag = True
            for honest_people in honest_peoples:
                for xij, yij in zip(x[honest_people], y[honest_people]):
                    if xij in honest_peoples and yij == 0 or xij not in honest_peoples and yij == 1:
                        flag = False
                        break
                if not flag:
                    break
            if flag:
                ans = max(ans, i)

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from itertools import product

N = int(input())

adict = {}

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

ans = 0

for lst in product((0, 1), repeat=N):
    jdg = True
    for n, l in enumerate(lst):
        if l==0:continue
        for i, j in adict[n+1]:
            if lst[i-1]!=j:
                jdg = False
                break
        if not jdg:break
    if jdg:ans=max(ans, sum(lst))
      
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * n
x = [[0] * n for i in range(n)]
y = [[0] * n for i in range(n)]

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


def check(honest):
    for i in range(n):
        if not honest[i]:continue
        for j in range(a[i]):
            if y[i][j] == 1 and not honest[x[i][j]]:return False
            if y[i][j] == 0 and honest[x[i][j]]:return False
    return True
        
def dfs(honest):
    if len(honest) == n:
        if check(honest):
            return sum(honest)
        else:
            return 0
    return max(dfs(honest + [True]),
               dfs(honest + [False]))
    
print(dfs([]))

Submission status: Accepted

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

ans=0
for i in range(2**N):
  table =list( format(i,"b").zfill(N)[::-1] )
  f=1
  for j,l in enumerate(XY):
    if table[j]=="1":
      for xy in l:
        x=xy[0]-1
        y=xy[1]
        if table[x]!=str(y):
          f=0
          break
    if f==0:
      break
  if f:
    ans=max(ans,table.count("1"))
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    cnt = 0
    flag = True
    for j in range(N):
        if (i >> j) & 1:
            cnt += 1
            for k in range(len(l[j])):
                #人1, 2, 3　--> 人0, 1, 2のため、-1をする
                if (i >> (l[j][k][0] - 1)) & 1 == l[j][k][1]:
                    pass
                else:
                    flag = False
                    break
    if flag:
        ans = max(ans, cnt)
    cnt = 0
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
n = int(input())

kind = [0] * n
word = {}
correct = 0
for i in range(n):
  word[i] = []
  for _ in range(int(input())):
    word[i].append(list(map(int,input().split())))
for i in range(2**n):#正直者を1で表す。高い桁から1番目の人
  ans = 1
  for j in range(n):#ある1人の人に注目する。
    if (i >> (n-1-j)) & 1:#j番目の人が正直者ならば，
      for k in range(len(word[j])):#j番目の人の発言に注目
        if word[j][k][1] == 1 and ((i>>(n-1-(word[j][k][0]-1))) & 1) == 0:#この人が「正直者である」といった発言に関して，その人が実は正直者でないならだめ。
          ans = 0
          break
        if word[j][k][1] == 0 and ((i>>(n-1-(word[j][k][0]-1))) & 1) == 1:#この人が「正直者である」といった発言に関して，その人が実は正直者でないならだめ。
          ans = 0
          break
  if ans:
    correct = sum(list(map(int,list(format(i, 'b')))))
print(correct)

Submission status: Accepted

Solution code:
import itertools
N=int(input())
Ev=[[] for i in range(N)]
for i in range(N):
    A=int(input())
    for j in range(A):
        x, y = map(int, input().split())
        Ev[i].append([x-1, y] )
ans=0
for i in range(2**N):
    flag=True
    for j in range(N):
        if (i>>j)&1==0:
            continue
        for x,y in Ev[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())
A = []
x = []
y = []
for i in range(N):
    A.append(int(input()))
    x2 = []
    y2 = []
    for j in range(A[i]):
        xy = input().split()
        x2.append(int(xy[0]))
        y2.append(int(xy[1]))
    x.insert(i, x2)
    y.insert(i, y2)

ans = 0
for i in range(pow(2, N)):
    flag = True
    for j in range(N):
        if not(i & (1<<j)):
            continue
        else:
            for k in range(A[j]):
                if (((i>>(x[j][k]-1))&1) ^ y[j][k]):
                    flag = False
    count = 0
    if flag:
        count = bin(i).count('1')
    if ans < count:
        ans = count
print(ans)

Submission status: Accepted

Solution code:
def honestcount(i):
    return bin(i).count("1")

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

N = int(input())

A = [0] * N
shogens=[]

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

count=0
for i in range(1<<N):
    is_ok =True
    for j in range(N):
        if not is_honest(i,j):
            continue
        for x,y in shogens[j]:
            if y!=is_honest(i,x):
                is_ok=False
                break
    if is_ok:
        count=max(count,honestcount(i))
print(count)

Submission status: Accepted

Solution code:
def honestcount(i):
    return bin(i).count("1")

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

N = int(input())

A = [0] * N
shogens=[]

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

count=0
for i in range(1<<N):
    is_ok =True
    for j in range(N):
        if not is_honest(i,j):
            continue
        for x,y in shogens[j]:
            if y!=is_honest(i,x): is_ok=False
    if is_ok:
        count=max(count,honestcount(i))
print(count)

Submission status: Accepted

Solution code:
import itertools


def is_compatible(hyp, testimonies):
    return all((key in hyp) == (val == 1) for key, val in testimonies.items())


def is_compatible_all(hyp, all_testimonies):
    return all(is_compatible(hyp, all_testimonies[i]) for i in hyp)


def main():
    n = int(input())
    all_testimonies = [{}]
    for _ in range(n):
        ai = int(input())
        statements = {}
        for _ in range(ai):
            x, y = input().split()
            statements[int(x)] = int(y)
        all_testimonies.append(statements)

    for e in all_cases(n):
        if is_compatible_all(e, all_testimonies):
            print(len(e))
            return


def all_cases(n):
    for r in range(n, -1, -1):
        for ensemble in itertools.combinations(range(1, n + 1), r):
            yield set(ensemble)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools


def is_compatible(hyp, testimonies):
    return all((key in hyp) == (val == 1) for key, val in testimonies.items())


def is_compatible_all(hyp, all_testimonies):
    return all(is_compatible(hyp, all_testimonies[i]) for i in hyp)


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

    all_testimonies = [{}]
    for _ in range(n):
        ai = int(input())
        statements = {}
        for _ in range(ai):
            x, y = input().split()
            statements[int(x)] = int(y)
        all_testimonies.append(statements)

    for e in all_cases(n):
        if is_compatible_all(e, all_testimonies):
            print(len(e))
            return

    print(0)


def all_cases(n):
    for r in range(n, 0, -1):
        for ensemble in itertools.combinations(range(1, n + 1), r):
            yield set(ensemble)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools


def is_compatible(hyp, testimonies):
    return all([(key in hyp) == (val == 1) for key, val in testimonies.items()])


def is_compatible_all(hyp, all_testimonies):
    return all([is_compatible(hyp, all_testimonies[i]) for i in hyp])


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

    all_testimonies = [{}]
    for _ in range(n):
        ai = int(input())
        statements = {}
        for _ in range(ai):
            x, y = input().split()
            statements[int(x)] = int(y)
        all_testimonies.append(statements)

    for e in all_cases(n):
        if is_compatible_all(e, all_testimonies):
            print(len(e))
            return

    print(0)


def all_cases(n):
    for r in range(n, 0, -1):
        for ensemble in itertools.combinations(range(1, n + 1), r):
            yield set(ensemble)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools


def is_compatible_internal(hyp, statement):
    honests = {key for key in statement if statement[key] == 1}
    unkinds = {key for key in statement if statement[key] == 0}

    return len(honests - hyp) == 0 and len(unkinds - hyp) == len(unkinds)


def is_compatible(hyp, statements):
    for i in hyp:
        if not is_compatible_internal(hyp, statements[i]):
            return False
    return True


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

    all_statements = [{}]
    for _ in range(n):
        ai = int(input())
        statements = {}
        for _ in range(ai):
            x, y = input().split()
            statements[int(x)] = int(y)
        all_statements.append(statements)

    for e in all_cases(n):
        if is_compatible(e, all_statements):
            print(len(e))
            return

    print(0)


def all_cases(n):
    for r in range(n, 0, -1):
        for ensemble in itertools.combinations(range(1, n + 1), r):
            yield set(ensemble)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

N = int(input())
X = [None] * N
Y = [None] * N

for i in range(N):
    A = int(input())
    x_i = [None] * A
    y_i = [None] * A

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

    X[i] = x_i
    Y[i] = y_i

res = 0
for n in range(1, N+1):
    for honests in itertools.combinations(range(N), n):
        correct = True
        for honest in honests:
            for x, y in zip(X[honest], Y[honest]):
                if y == 1 and x not in honests or\
                   y == 0 and x in honests:

                    correct = False
                    break

            if not correct:
                break

        if correct:
            res = max(res, n)

print(res)

Submission status: Accepted

Solution code:
n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[0]*a
  y=[0]*a
  for j in range(a):
    x[j],y[j]=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
s=0
for i in range(2**n):
  c=0
  d=0
  B=[0]*n
  for j in range(n):
    if((i >> j) & 1):
      c=c+1
      B[j]=1
  for k in range(n):
    if B[k]==1:
      for j in range(A[k]):
        if Y[k][j]!=B[X[k][j]-1]:
          d=-1
          break
    if d<0:
      break
  if s<c and d==0:
    s=c
      
      
print(s)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
xy = [[] for _ in range(n)]

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

li = []
ans = 0

def main(li):
    if len(li) == n:
        hantei(li)
    else:
        li.append(0)
        main(li)
        li.pop(-1)
        li.append(1)
        main(li)
        li.pop(-1)

def hantei(li):
    global ans
    flag = True
    for i in range(n):
        if li[i] == 1:
            for x,y in xy[i]:
                if li[x-1] != y:
                    flag = False
    if flag:
        ans = max(ans, sum(li))

if __name__ == '__main__':
    main(li)
    print(ans)

Submission status: Accepted

Solution code:
import sys

N = int(input())
testimonies = {i: [] for i in range(N)}

for i in range(N):
    M = int(input())
    for j in range(M):
        q, r = map(int, input().split(' '))
        testimonies[i].append([q-1, r])

res = 0
for i in range(2**N):

    bit = bin(i)[2:].zfill(N)
    honests = [j for j, b in enumerate(bit) if b == '1']  # 正直者
    flag = True

    for j, b in enumerate(bit):
        # 発言を検証

        if b == '0':
            continue

        for testimony in testimonies[j]:
            if ((testimony[0] in honests) and testimony[1] == 0) or ((testimony[0] not in honests) and testimony[1] == 1):
                flag = False
        
        if not flag:
            break
    
    if flag:
        res_ = sum([1 for k in bit if k == '1'])
        if res < res_:
            res = res_
        
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


def sosu(x):
    for i in range(2, int(sqrt(x)+1)):
        if x % i == 0:
            return False
    return True


mod = 1000000007
inf = float('INF')


def A():
    v1, v2, v3 = LI()
    v = v1+v2+v3
    if(v >= 22):
        print('bust')
    else:
        print('win')
    return

# B


def B():
    S = input()
    S = S[:-1]
    count = 0
    for i in range(len(S)//2):
        if (S[i] != S[-1-i]):
            count += 1

    print(count)
    print(1 << 2)
    return

# C


def true():
    S = input()
    S = S[:-1]

    tmp = 0
    for x in range(1 << (len(S)-1)):
        func = S[-1]
        for i in range(len(S)-1):
            if(x & (1 << i)):
                tmp += int(func)
                func = S[-2-i]
            else:
                func = S[-2-i]+func
        tmp += int(func)
    print(tmp)

    return


def flagcounter(x):
    if (x == 0):
        return 0
    return flagcounter(x >> 1)+(x & 1)


def C():
    N = II()
    L = []
    A=[]

    for i in range(N):
        A.append(II())
        LL=[]

        for j in range(A[i]):
            x, y = LI()
            LL.append((x-1, y))
        L.append(LL)
    # print(L)
    #print(L[0][0])
    ans=0
    for x in range(1 << N):
        ok=True
        for i in range(N):
            if(x & (1 << i)):
                for j,k in L[i]:
                    if (((x >> j) & 1) ^ k):
                        ok=False 
        if ok :
            ans=max(ans, flagcounter(x))

    print(ans)


# D


def D():

    a, b, x = LI()
    BIG = a*a*b/2
    if x > BIG:
        y = 2*b-(2*x/a/a)
        print(math.degrees(math.atan(y/a)))
    else:
        y = 2*x/a/b
        print(math.degrees(math.atan(b/y)))
    return

# E


def E():
    N, K = LI()
    A = LI()
    F = LI()
    A.sort(reverse=True)
    F.sort()
    cost = []
    for i in range(len(N)):
        cost.append(A[i]*F[i])

    a = F[cost.index(max(cost))]

    return

# F


def F():
    N, M = LI()

    value = [0] * M
    power = [0] * M
    for i in range(M):
        a, b = LI()
        value[i] = a
        c = LI()
        L = ['0'] * N
        for k in c:
            L[k - 1] = '1'
        bint = ''.join(L)
        power[i] = int(bint, 2)
    bint = ''.join(list(['1'] * N))
    dp = [inf] * (int(bint, 2)+1)
    t = 0
    cost = 0

    dp[0] = 0
    for s in range(int(bint, 2) + 1):
        for i in range(M):
            t = s | power[i]
            cost = dp[s] + value[i]
            dp[t] = min(dp[t], cost)
    print(-1) if(dp[-1] == inf) else print(dp[-1])

    return

    # you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")


def solution(S):
    # write your code in Python 3.6
    N = len(S)

    pass


# Solve
if __name__ == '__main__':

    C()

Submission status: Accepted

Solution code:
N=int(input())
testimony={}
for i in range(N):
    Ai=int(input())
    tmp=[]
    for j in range(Ai):
        xy=list(map(int,input().split()))
        tmp.append(xy)
    testimony[i+1]=tmp
#print(testimony)

ans=0
#ビット全探索
for bit in range(2**N):
    test=[]
    for i in range(N):
        if (bit>>i)&1:
            test.append(1)
        else:
            test.append(0)
    flag=True
    for i in range(N):
        if test[i]==1:
            for j in testimony[i+1]:
                if j[1]!=test[j[0]-1]:
                    flag=False
                else:
                    pass
        else:
            pass
    if flag==True:
        ans=max(ans,sum(test))
    else:
        pass

print(ans)

Submission status: Accepted

Solution code:
#ABC147 C
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
n=int(input())
shogen=[]
for _ in range(n):
    a=int(input())
    t=[]
    for __ in range(a):
        s=list(map(int,input().split()))
        t.append(s)
    shogen.append(t)

ans=0

for i in range(2**n):
    flag=True
    for j in range(n):
        if not flag:
            break
        if ((i>>j) & 1):
            for s in shogen[j]:
                if ((i>>s[0]-1)&1) !=s[1]:
                    flag=False
    if flag:
        mnt = bin(i).count("1")
        ans=max(ans,mnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list()
xy = list()
for i in range(n):
  A = int(input())
  XY = [tuple(map(int,input().split())) for i in range(A)]
  a.append(A)
  xy.append(XY)
is_paradox = False
ans = 0
for i in range(2 ** n):
  honest = []
  for j in range(n):
    if i >> j & 1:
      honest.append(1)
    else:
      honest.append(0)
  for k,v in enumerate(a):
    if honest[k] == 0:
      continue
    for x,y in xy[k]:
      x -= 1
      if y == 1 and honest[x] != 1:
        is_paradox = True
        break
      elif y == 0 and honest[x] == 1:
        is_paradox = True
        break
  if is_paradox:
    is_paradox = False
    continue
  if is_paradox == False:
    ans = max(ans,sum(honest))
print(ans)

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict
from copy import deepcopy
import itertools
input = sys.stdin.readline
# 文字列の場合は普通のinput()を使うか下を使う
# input = sys.stdin.readline().rstrip()

N = int(input())
A = [None]
info = [None] + [[] for _ in range(N)]
for i in range(N):
    a = int(input())
    A.append(a)
    for _ in range(a):
        x, y = map(int, input().split())
        info[i+1].append((x, y))
#print('info={}'.format(info))
    
ans_bit = 0
for num in range(2**N-1, -1, -1):
    bit_pre = bin(num)
    bit_pre = bit_pre[2:]
    l = len(bit_pre)
    bit = '0' * (N - l) + bit_pre


    status = [None] * (N + 1)
    #print('bit={}'.format(bit))
    contradict = False
    for i, n in enumerate(bit):
        i += 1
        n = int(n)
        #print('i={}, n={}'.format(i, n))
    
        if n == 1:
            for x, y in info[i]:
                if int(bit[x-1]) != y:
                    contradict = True
                    
                s = status[x]
                #print('s={}'.format(s))
                if s == None:
                    status[x] = y
                elif s != y:
                    contradict = True
                #print('status={}'.format(status))
        
    if not contradict:
        ans_bit = bit
        break



#print('ans_bit={}'.format(ans_bit))
ans = 0
for x in ans_bit:
    if x == '1':
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
x = [format(i, '015b') for i in range(2**n)]
y = []
for _ in range(n):
    z = []
    for _ in range(int(input())):
        a, b = map(int, input().split())
        z.append([a, b])
    y.append(z)
ans = 0
for i in range(2**n):
    flag = True
    for j in range(n):
        if x[i][-j - 1] == '1':
            for k in range(len(y[j])):
                if y[j][k][1] == 1 and x[i][-(y[j][k][0])] == '0':
                    flag = False
                elif y[j][k][1] == 0 and x[i][-(y[j][k][0])] == '1':
                    flag = False
    if flag:
        ans = max(ans, x[i].count('1'))
print(ans)

Submission status: Accepted

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

ans=0
for i in range(2**N):
    flag=True
    for j in range(N):
        if (i>>j)&1==0:
            continue
        for x,y in evidences[j]:
            if (i>>x)&1!=y:
                flag=False
                break
        if not flag:
            break

    if flag:
        ans=max(ans,bin(i)[2:].count('1'))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [[] for _ in range(N)]
for i in range(N):
    for _ in range(int(input())):
        A[i].append([int(s) for s in input().split()])

ret = 0
for i in range(2 ** N):#2**Nだけ正解の候補がある
    bits = [i >> j & 1 for j in range(N)]#　N桁の２進数iについて、逆順に並べた配列が生成
    #print(bits)
    for i, a in enumerate(A):#i→人、a→人iの証言のリスト
        if bits[i] == 0:#人iが正直者じゃない場合、continueして次の人の証言に移行
            continue
        for x, y in a:
            # print(bits, bits[x - 1], y)
            if bits[x - 1] == y:#正解の候補と証言が一致する場合、その人の次の証言を参照
                continue
            break#そうでない場合、その人の証言を聞くのをやめて次の人の証言を聞く
        else:#breakでループを抜けなかったときにのみ、elseが実行
            continue#このcontinueは２つ上のfor文のcontinueつまり、間違った証言がある場合、一つ下のbreakが評価されて、次の正解候補にうつる
        break
    else:#breakでループを抜けなかったときにのみ、elseが実行
        ret = max(ret, sum(bits))
print(ret)

Submission status: Accepted

Solution code:
N = int(input())
a = [[] for i in range(N)]

for i in range(N):
    c = int(input())
    for j in range(c):
        x,y = map(int, input().split(" "))
        a[i].append(([x, y]))

from itertools import product

result = 0
for ans in product([0,1], repeat=N):
    flag = True
    for i,check in enumerate(a):
        if ans[i] == 0:
            continue

        for x,y in check:
            if y != ans[x-1]:
                flag =  False
                break

    if flag:
        result = max(sum(ans), result)
print(result)