Problem:


Score : 300 points

Problem Statement

There are N people numbered 1 to N. Each of them is either an honest person whose testimonies are always correct or an unkind person whose testimonies may be correct or not.

Person i gives A_i testimonies. The j-th testimony by Person i is represented by two integers x_{ij} and y_{ij}. If y_{ij} = 1, the testimony says Person x_{ij} is honest; if y_{ij} = 0, it says Person x_{ij} is unkind.

How many honest persons can be among those N people at most?

Constraints

All values in input are integers.

1 \leq N \leq 15

0 \leq A_i \leq N - 1

1 \leq x_{ij} \leq N

x_{ij} \neq i

x_{ij_1} \neq x_{ij_2} (j_1 \neq j_2)

y_{ij} = 0, 1

Input

Input is given from Standard Input in the following format:

N
A_1
x_{11} y_{11}
x_{12} y_{12}
:
x_{1A_1} y_{1A_1}
A_2
x_{21} y_{21}
x_{22} y_{22}
:
x_{2A_2} y_{2A_2}
:
A_N
x_{N1} y_{N1}
x_{N2} y_{N2}
:
x_{NA_N} y_{NA_N}

Output

Print the maximum possible number of honest persons among the N people.

Sample Input 1

3
1
2 1
1
1 1
1
2 0

Sample Output 1

2

If Person 1 and Person 2 are honest and Person 3 is unkind, we have two honest persons without inconsistencies, which is the maximum possible number of honest persons.

Sample Input 2

3
2
2 1
3 0
2
3 1
1 0
2
1 1
2 0

Sample Output 2

0

Assuming that one or more of them are honest immediately leads to a contradiction.

Sample Input 3

2
1
2 0
1
1 0

Sample Output 3

1



Sample input:
3
1
2 1
1
1 1
1
2 0


Sample output:
2

Submission status: Accepted

Solution code:
import heapq as h
import math
import numpy as np
import copy
import itertools
import sys
 

# n, w = map(int, input().split())
n = int(input())
g = [[-1 for _ in range(n)] for _ in range(n)]

for i in range(n):
    a_cn = int(input())
    for j in range(a_cn):
        x,y = map(int, input().split())
        if y == 1:
            g[i][x-1] = 1
        elif y == 0:
            g[i][x-1] = 0


ans2 = 0
for i in range(2**n):
    cnt = 0
    bag = [0] * n 
    for j in range(n):
        if ((i >> j) & 1):
            bag[j] = 1
    ok = True
    for ix, v in enumerate(bag):
        if v == 1:
            for jx, jv in enumerate(g[ix]):
                if jv == 1:
                    if bag[jx] != 1:
                        ok = False
                elif jv == 0:
                    if bag[jx] != 0:
                        ok = False
    if ok == True:
        ans = sum(bag)
    else:
        ans = 0
    ans2 = max(ans2,ans)
print(ans2)

Submission status: Accepted

Solution code:
import sys
from itertools import islice
read = map(int, sys.stdin.read().split())

N = next(read)
candidates = [format(i, 'b').zfill(N) for i in range(2 ** N)]
A = [0] * N
xy = [[] for _ in range(N)]
for i in range(N):
    A[i] = next(read)
    xy[i].extend(list(islice(read, A[i] * 2)))

answer = 0

for candidate in candidates:
    tmp = 0
    truth = set()
    false = set()
    for k in range(N):
        if candidate[k] == '1':
            if k in false:
                break
            truth.add(k)
            for i, j in zip(*[iter(xy[k])] * 2):
                i -= 1
                if j == 1:
                    if i in false:
                        break
                    truth.add(i)
                else:
                    if i in truth:
                        break
                    false.add(i)
            else:
                continue
            break
        else:
            if k in truth:
                break
            false.add(k)
    else:
        if len(truth) > answer:
            answer = len(truth)

print(answer)

Submission status: Accepted

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

for i in range(2**N):
  f=1
  h=[]
  u=[]
  for j in range(N):
    if (i>>j)&1:
      h.append(j)
    else:
      u.append(j)
  for k in h:
    for l in I[k]:
      if l[1]==1 and l[0] in u:
        f=0
        break
      elif l[1]==0 and l[0] in h:
        f=0
        break
  if f==1:
    a=max(a,len(h))
print(a)

Submission status: Accepted

Solution code:
N=int(input())
Ins=[[] for _ in range(N)]
ans=0

#bit演算用にx-1
for i in range(N):
  A=int(input())
  for _ in range(A):
    x,y=map(int,input().split())
    Ins[i].append((x-1,y))

for i in range(2**N):
  flag=1
  honest=[]
  unkind=[]
  for j in range(N):
    if (i>>j)&1:
      honest.append(j)
    else:
      unkind.append(j)
  for k in honest:
    for l in Ins[k]:
      if l[1]==1 and l[0] in unkind:
        flag=0
        break
      elif l[1]==0 and l[0] in honest:
        flag=0
        break
  if flag==1:
    ans=max(ans,len(honest))
print(ans)

Submission status: Accepted

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

N = int(input())
A = []
x_y = []

for i in range(N):
    x = int(input())
    A.append(x)
    x = [list(map(int,input().split()))
        for _ in range(A[i])]
    x_y.append(x)


zerone = [0,1]

# 0,1の組み合わせを作る
HOU_all = list(itertools.product(zerone,
repeat = N))



Honer_Count = 0

for HOU_state in HOU_all:

    count_N = 0

    for i in range(N):
        count_A = 0
        if HOU_state[i] == 1:
            for j in range(A[i]): 
                if HOU_state[x_y[i][j][0]-1] != x_y[i][j][1]:
                    break
                else:
                    count_A += 1
                    continue
            
            if count_A == A[i]:
                count_N += 1

    if count_N == sum(HOU_state):
        Honer_Count = max([sum(HOU_state),Honer_Count])
        

print(Honer_Count)

Submission status: Accepted

Solution code:
N=int(input())
all=[]
for i in range(N):
    A_N=int(input())
    grid=[]
    for j in range(A_N):
        a=list(map(int, input().split()))
        grid.append(a)
    all.append(grid)
ans=[]
for i in range(2**N):# 二進数のリスト作成
    b = format(i,'b').zfill(N)
    c_l = [int(p) for p in list(b)]
    for l in range(N):# checkの開始（lは人）
        for m in range(len(all[l])):# その人の主張の数
            if c_l[l]==1:# 不親切な奴は無視
                if c_l[all[l][m][0]-1]!=all[l][m][1]:
                    c_l=[0]*N
    ans.append(c_l.count(1))
print(max(ans))

Submission status: Accepted

Solution code:
N = int(input())
data = []
for _ in range(N):
	A = int(input())
	items = []
	for __ in range(A):
		x, y = map(int, input().split())
		items.append((x - 1, y))
	data.append(items)
 
best = 0
 
def check(i):
    for j in range(N):
        if ((i >> j) & 1) == 1:           
            for x, y in data[j]:
                if y !=((i >> x) & 1):return False						
    return True
 
for i in reversed(range(0, 2**N)):
    count=0
    for j in range(N):count += ((i >> j) & 1)
    if count>best:
        if check(i):best = count
	
print(best)

Submission status: Accepted

Solution code:
N = int(input())
data = []
for _ in range(N):
	A = int(input())
	items = []
	for __ in range(A):
		x, y = map(int, input().split())
		items.append((x - 1, y))
	data.append(items)
 
best = 0
 
def check(i):
    for j in range(N):
        if ((i >> j) & 1) == 1:           
            for x, y in data[j]:
                if y !=((i >> x) & 1):return False						
    return True
 
for i in range(2**N):
    count=0
    for j in range(N):count += ((i >> j) & 1)
    if count>best:
        if check(i):best = count
	
print(best)

Submission status: Accepted

Solution code:
n = int(input())

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

ans = 0
for mask in range(2 ** n):
    flg = True
    for bit in range(n):
        if (mask >> bit) & 1:
            for x, y in evi_all[bit]:
                if (y == 1 and (mask >> x & 1) == 0) or (y == 0 and (mask >> x & 1) == 1):
                    flg = False

    if flg:
        cnt = 0
        for bit_2 in range(n):
            if (mask >> bit_2) & 1:
                cnt += 1
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = []
z = [ [] for k in range(0, N) ]

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

result = [0]
r = [1] + [ 0 for i in range(0, N-1)]

while r != [ 0 for j in range(0, N)]:
    s = 1
    for i in range(0, N):
        if r[i] == 1:
            for k in range(0, A[i]):
                if r[z[i][k][0] - 1] != z[i][k][1]:
                    s = 0
    if s == 1:
        result.append(sum(r))
    for i in range(0, N):
        if r[i] == 0:
            r[i] = 1
            break
        else:
            r[i] = 0

print(max(result))

Submission status: Accepted

Solution code:
N = int(input())

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

ans = 0
for state in range(1 << N):
    flag = True
    for i in range(N):
        if state >> i & 1:
            for x, y in notes[i]:
                flag &= (y == 1 and state >> x & 1) or (y == 0 and (state >> x & 1) == 0)

    if flag:
        ans = max(ans, sum(state >> i & 1 for i in range(N)))
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations as co
n=int(input())
A=[[] for _ in range(n+1)]
for i in range(1,n+1):
    for _ in range(int(input())):
        A[i].append(list(map(int,input().split())))
for i in range(n+1,0,-1):
    for a in co(range(1,n+1),i):
        b=1
        B=[0]*(n+1)
        for b in a:
            B[b]=1
        for k,v in enumerate(B):
            if v==1:
                for x,y in A[k]:
                    if B[x]!=y:
                        b=0;break
        if b:
            print(i)
            exit()
print(0)

Submission status: Accepted

Solution code:
import itertools

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

def comb(x):
    return list(itertools.combinations(range(n),x))

def check(honests):
    flag = True
    check_list = [0]*n
    for i in honests:
        check_list[i] = 1
    for i in honests:
        for e in lst[i]:
            if (check_list[e[0]] != e[1]):
                flag = False
                break
        if not flag:
            break
    return flag    
  
def main():
    for i in reversed(range(n+1)):
        for honests in comb(i):
            if check(honests):
                return i

n,a,lst = input_data()
print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import string
import sys
from itertools import chain, dropwhile, takewhile

INF = float("inf")


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in readi(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[0]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


from itertools import chain, combinations


def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))


from collections import defaultdict


def main():
    n = readi()
    shougen = defaultdict(list)
    for i in range(n):
        a = readi()
        for _ in range(a):
            x, y = readi(2)
            x -= 1
            shougen[i].append((x, y))

    ans = 0
    for ps in powerset(range(n)):
        valid = True
        for p in ps:
            for x, y in shougen[p]:
                if y == 1 and x not in ps:
                    valid = False
                if y == 0 and x in ps:
                    valid = False
        if valid:
            ans = max(ans, len(ps))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

ans = 0
for bit in range(2**N):
    if judge(bit):
        res = 0
        for i in range(N):
            if bit & (1<<i):
                res += 1
        ans = max(res, ans)
        
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

N = int(input())

claim = []

for _ in range(N):
    memo = []
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        memo.append((x,y))
    claim.append(memo)

maximam = 0
for bit in range(2**N):
    flag = True
    count = 0
    for i in range(N):
        if bit & (1<<i):
            count+=1
            for x, y in claim[i]:
                if (bit & (1<<(x-1)) and y==0) or (not (bit & (1<<(x-1))) and y==1):
                    flag = False
    if flag:
        maximam = max(maximam,count)
print(maximam)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

N = int(input())

claim = []

for _ in range(N):
    memo = []
    A = int(input())
    for _ in range(A):
        x, y = input().split()
        memo.append((x,y))
    claim.append(memo)

maximam = 0
for i in range(2**N):
    flag = True
    bin_i = (N - len(str(bin(i))[2:]))*["0"] + list(bin(i))[2:]
    for j, man in enumerate(bin_i):
        if man == "0":
            continue
        for x, y in claim[j]:
            if bin_i[int(x)-1] != y:
                flag = False
    if flag:
        count = 0
        for b in bin_i:
            if b=="1":
                count+=1
        maximam = max(maximam,count)
print(count)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
l = []
for _ in range(N):
    a = int(input())
    xy = [list(map(int, input().split())) for _ in range(a)]
    l.append(xy)
#print(l) #[[[2, 0]], [[1, 1]]]

test_list = list(itertools.product([1,0],repeat=N))
test_list = sorted(test_list, key=lambda x:x.count(0))
#print(test_list) #[(1,1),(1,0),(0,1),(0,0)]

for test in test_list:
    for i in range(N):
        if test[i]:
            for l_ in l[i]:
                if l_[1] != test[l_[0]-1]:
                    break
            else:
                continue
            break
    else:
        print(test.count(1))
        break
    continue

Submission status: Accepted

Solution code:
# coding: utf-8
import itertools


n_people = int(input())
testimony_list = []
for i in range(n_people):
    n_testimony = int(input())
    testimony_list.append([])
    for j in range(n_testimony):
        testimony_list[i].append([int(x) for x in input().split(' ')])
        
cases_list = sorted(list(itertools.product([0,1], repeat=n_people)), key=lambda x:x.count(1), reverse = True)

for case in cases_list:
    for i in range(n_people):
        if case[i] == 0:
            continue
        
        for testimony in testimony_list[i]:
            if testimony[1] != case[testimony[0]-1]:
                break
        
        else:
            continue
        break
    
    else:
        print(case.count(1))
        break
    continue

Submission status: Accepted

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

for i in range(N):
    a=int(input())
    B=[]
    for __ in range(a):
        x,y=map(int,input().split())
        B.append((x-1,y))
    A.append(B)

ans=0
for bit in range(1<<N):
    flag=1
    honest=[(bit>>i)&1 for i in range(N)]
    for i in range(N):
        if (honest[i] == 0):
            continue
        for x,y in A[i]:
            if honest[x] != y:
                flag=0
    if flag:
        ans=max(ans,sum(honest))
print(ans)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
ii = [0 for _ in range(n)]
member = [i for i in range(n)]
p = []
for i in range(n):
    p.append([])
    buf = int(input())
    for j in range(buf):
        p[i].append([int(x) for x in input().split(" ")])

for i in range(n+1):
    flg = True
    buf_l = list(itertools.combinations(member, n - i))
    for j in buf_l:
        flg = True
        buf_i = ii.copy()
        for k in j:
            buf_i[k] = 1
        for l in j:
            for k in p[l]:
                if buf_i[k[0]-1] != k[1]:
                    flg = False
                    break
            if not flg:
                break
        if flg:
            break
    if flg:
        break
print(n-i)

Submission status: Accepted

Solution code:
import sys


def main():
    N = int(input())
    statement = [[] for i in range(N)]
    for i in range(N):
        message = int(input())
        for j in range(message):
            num, tmp = map(int, input().split())
            if tmp == 1:
                TF = True
            else:
                TF = False
            statement[i].append((num, TF))
    ans = 0
    for i in range(1 << N):
        status = [False] * 15
        tmp_ans = 0
        for j, c in enumerate(format(i, '015b')[::-1]):
            if c == '1':
                status[j] = True
                tmp_ans += 1
        if tmp_ans <= ans:
            continue
        flag = True
        for j, person in enumerate(statement):
            if not status[j]:
                continue
            for state in person:
                if status[state[0]-1] != state[1]:
                    flag = False
                    break
            if not flag:
                break
        if flag:
            ans = max(ans, tmp_ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
lis = [[] for _ in range(n)]

for i in range(n):
    a = int(input())
    for _ in range(a):
        x,y = map(int,input().split())
        lis[i].append((x-1,y))
ans = 0
for i in range(1, 1 << n):
    flag = True
    for j in range(n):
        if (i >> j) & 1 == 0: #j人目が正直者でないか?
            continue
        for x,y in lis[j]:
            if (i>>x) & 1 != y: #仮定と結果が異なる
                flag = False
                break
        if not flag:
            break
    if flag:
        ans = max(ans,bin(i)[2:].count('1')) #iの2進数の1の個数(0x抜き)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
data = []
ans = 0
for i in range(N):
  A = int(input())
  for j in range(A):
    shougen = list(map(int,input().split()))
    hatugen = []
    hatugen.append(i+1)
    hatugen.append(shougen[0])
    hatugen.append(shougen[1])
    data.append(hatugen)
for k in range(2**N):
  ng=0
  hantei = format(k,'b')
  hantei = str(hantei.zfill(N)) 
  for p in range(len(data)):

    ng = 0
    if hantei[data[p][0]-1] == '1':
      
      if hantei[data[p][1]-1] == str(data[p][2]):
        continue
      else:
        ng = 1

        break
  if ng == 0:
    ans = max(hantei.count('1'),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):
    a[i].append(list(map(int, input().split())))
 
max_honest = 0
for i in range(2**N):
  contradiction = False
  honest_p = []
  unkind_p = []
  doubt_honest_p = []
  doubt_unkind_p = []
  length = len(format(2**N-1, "b"))
  bin_num = format(i, "b").zfill(length)
  for j in range(length):
    if (i >> j) & 1:
      if not j+1 in honest_p:
      	honest_p.append(j+1)
      if not j+1 in doubt_honest_p:
      	doubt_honest_p.append(j+1)
      for k in a[j]:
        p = k[0]
        t = k[1]
        if t:
          if not p in honest_p:
          	honest_p.append(p)
        else:
          if not p in unkind_p: 
          	unkind_p.append(p)
    else:
      if not j+1 in unkind_p:
        unkind_p.append(j+1)
      if not j+1 in doubt_unkind_p:
      	doubt_unkind_p.append(j+1)
  if len(list(set(honest_p) & set(unkind_p))) != 0:
    contradiction = True
  if not contradiction and max_honest <= len(doubt_honest_p):
    max_honest = len(doubt_honest_p)
    
print(max_honest)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    XY=[None]*n
    for i in range(n):
        a=int(input())
        S=[None]*a
        for j in range(a):
            S[j]=tuple(map(int,input().split()))
        XY[i]=S

    ans=0
    for U in range(1<<n):
        flag=True
        for i in range(n):
            if((U>>i)&1==0): continue
            for x,y in XY[i]:
                x-=1
                if((U>>x)&1)!=y:
                    flag=False
        if(flag):
            ans=max(ans,bin(U).count('1'))

    print(ans)
resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations

n = int(input())

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

res = 0
for i in range(1,n+1):
    for c in combinations(range(n), i):
        flag = True
        for X in c:
            for x,y in al[X]:
                if y==1:
                    if x-1 not in c:
                        flag = False
                else:
                    if x-1 in c:
                        flag = False
        if flag:
            res = i
            break

print(res)

Submission status: Accepted

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

noContradiction = []
Ans = 0
for bit in range(2**N):
	honest = []
	for i in range(N):
		if bit >> i & 1 == 1:
			honest.append(1)
		else:
			honest.append(0)
	flag = True
	for i in range(N):
		if honest[i]:
			for saying in As[i]:
				if ((saying[1] == 1 and honest[saying[0] - 1] == 0)
					or (saying[1] == 0 and honest[saying[0] - 1] == 1)):
					flag = False
					break
		if not flag:
			break
	if flag:
		Ans = max(Ans, sum(honest))
print(Ans)

Submission status: Accepted

Solution code:
N = int(input())
R = []
for i in range(N):
    s = int(input())
    values = []
    for j in range(s):
        values.append(list(map(int,input().split())))
    R.append(values)
def check(status):
    for i in range(N):
        s = status[i]
        for e1,e2 in R[i]:
            if s == '0':
                continue
            if e2 == 1 and status[e1-1] == '0':
                return False
            if e2 == 0 and status[e1-1] == '1':
                return False
    return True
ans = 0
for x in range(2**N):
    status = format(x,'0%ib'%N)
    if check(status):
        value = status.count('1')
        if value > ans:
            ans = value
print(ans)

Submission status: Accepted

Solution code:
def count_ones(num):
    num = (num & 0x55555555) + (num >> 1 & 0x55555555) 
    num = (num & 0x33333333) + (num >> 2 & 0x33333333)
    num = (num & 0x0F0F0F0F) + (num >> 4 & 0x0F0F0F0F)
    num = (num & 0x00FF00FF) + (num >> 8 & 0x00FF00FF)
    num = (num & 0x0000FFFF) + (num >>16 & 0x0000FFFF)
    return num
ans = 0
cnt = 0
check = 0
n = int(input())
temp_n = 2**n-1
# print(bin(temp_n^255))
# print(count_ones(temp_n^255))
ls_xy = [[0,0] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        if y == 1:
            ls_xy[i][0] += 2**(x-1)
        elif y == 0:
            ls_xy[i][1] += 2**(x-1)

for i in range(2**n):
    check = 0
    for j in range(n):
        if i&(2**j) == 0:
            # print("c",i,j)
            continue
        if (~i & (2**n-1)) & ls_xy[j][0] > 0 or i & ls_xy[j][1] > 0:
            check = 1
            # print("b",i,j)
            break
    if check == 0 and count_ones(i) > ans:
        ans = count_ones(i)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

n = int(input())
state_list = [[-1 for _ in range(n)] for _ in range(n)]

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

from itertools import product
pattern_list = list(product("10",repeat=n))

def check(pattern):
    true_people = [i for i,v in enumerate(pattern) if v=="1"]
    for i in true_people:
        for j,v in enumerate(state_list[i]):
            if (v==0 and j in true_people) or (v==1 and j not in true_people):
                return 0
    return len(true_people)
ret = 0
for i in pattern_list:
    ret = max(ret,check(i))
print(ret)

Submission status: Accepted

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

com=[[0 for i in range(n) ] for j in range(2**n)]

for i in range(2**n):
  for j in range(n):
    if ((i >> j) & 1) == 1:
      com[i][j]=1
  #正直者の証言が全て合っているか。
  for j in range(n):
    if com[i][j]==1:
      for k in range(a[j]):
        if y[j][k]!=com[i][x[j][k]-1]:
          com[i]=[0 for l in range(n) ]
          break
sum=[sum(com[i]) for i in range(2**n) ]
print(max(sum))

Submission status: Accepted

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

anssum = 0
for i in range(2 ** n):
    flag = True
    for j in range(len(HOU)):
        if (i >> HOU[j][0]) & 1:
            if HOU[j][2] == i >> HOU[j][1] & 1:
                continue
            else:
                flag = False
                break
        else:
            if not (i >> HOU[j][0]) & 1:
                continue
            else:
                flag = False
                break


    if flag:
        anssum = max(anssum,str(bin(i)).count('1'))

print(anssum)

Submission status: Accepted

Solution code:
n = int(input())
a = {}
xy = {}
for i in range(n):
    a[i] = int(input())
    xy[i] = {}
    for j in range(a[i]):
        xy[i][j] = list(map(int,input().split()))
ans = []
for i in range(2 ** n):
    flag = []
    k_low = bin(i)[2:]
    if len(k_low) < n:
        k_low = "0" * (n-len(k_low)) + k_low
    for k in k_low:
        flag.append(int(k))
    mujun = 0
    for x in range(len(xy)):
        if flag[x] == 1:
            for y in range(len(xy[x])):
                if flag[xy[x][y][0]-1] != xy[x][y][1]:
                    mujun = 1
    if mujun == 0:
        ans.append(flag)
sum_list = []
for answer in ans:
    sum_list.append(sum(answer))
print(max(sum_list))

Submission status: Accepted

Solution code:
def solve(string):
    n, *axy = map(int, string.split())
    i = 0
    h = [set() for _ in range(n)]
    u = [set() for _ in range(n)]
    for j in range(n):
        a = axy[i]
        for x, y in zip(*[iter(axy[i + 1:i + 2 * a + 1])] * 2):
            if y == 1:
                h[j].add(x - 1)
            else:
                u[j].add(x - 1)
        i += 2 * a + 1

    def search(checking, honest, unkind):
        if len(honest & unkind) > 0:
            return 0
        if len(checking) == 0:
            return len(honest)
        t = checking.copy()
        c = t.pop()
        return max(search(t, honest | {c} | h[c], unkind | u[c]), search(t, honest, unkind | {c}))

    return str(search(set(range(n)), set(), set()))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
N = int(input())
A = []
x = []
y = []

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

    tmp_x = []
    tmp_y = []
    for j in range(num):
        input1, input2 = [int(k) for k in input().split()]
        tmp_x.append(input1)
        tmp_y.append(input2)

    x.append(tmp_x)
    y.append(tmp_y)

ans_list = []
# 2^N通りのパターンを試す
# iを2進数で表示した際に、
# N桁目（0始まり）の数字（0/1）は、人Nが正直者か不親切な人かを示す
for i in range(2 ** N):

# honestは正直者のリスト
    honest = []
    for j in range(N):
        if ((i >> j) & 1):
            honest.append(j)

# 正直者の証言に矛盾がないかをチェック
    flag = 1
    for j in honest:
        for k, l in zip(x[j], y[j]):
            if l == 1:
                if ((i >> (k-1)) & 1):
                    pass
                else:
                    flag = 0
            else:
                if not ((i >> (k-1)) & 1):
                    pass
                else:
                    flag = 0

    if flag == 1:
        ans_list.append(len(honest))

print(max(ans_list))

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#正直者ならtestimonyのxの位置に正直者である1を置く
        elif(y[i][j] == 0):
            testimony[i][x[i][j]-1] = 0#さっきの反対

ans = 0
for i in range(2**n):#2**n通りの「正直者」と「不親切な人」の全パターンを列挙
    bit_list = []
    for j in range(n):
        if ((i >> j) & 1):
            bit_list.append(1)#正直者なら
        else:
            bit_list.append(0)
    flag = 1
    #列挙した中からtestimony[k][l]と一致するのを探し、さらにその中からbit_listの最大値を求める
    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]): #yの人の証言と食い違っていたらflagを0にする
                        flag = 0
                        break
    
    if(flag == 1):
        ans = max(sum(bit_list),ans)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
data_xy = []
for i in range(N):
    A = int(input())
    xy = []
    for i in range(A):
        [x,y] = list(map(int,input().split()))
        xy.append([x-1, y])
    data_xy.append(xy)
ans = 0
for i in range(2**N):
    p_list = [0]*N
    for j in range(N):
        if (i>>j) & 1 == 1:
            p_list[j] = 1
    flag = True
    for j in range(N):
        if p_list[j] == 1:
            for k in range(len(data_xy[j])):
                x = data_xy[j][k][0]
                y = data_xy[j][k][1]
                if p_list[x] != y:
                    flag = False
    if flag == True:
        ans = max(sum(p_list),ans)
print(ans)