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:
from collections import  deque
import sys
import bisect
# import math
import itertools
from queue import deque
# from math import gcd

INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

# def lcm(x, y): return (x * y) // gcd(x, y)

N = inp()
A = [0 for _ in range(N)]
xx = [[] for _ in range(N)]
yy = [[] for _ in range(N)]

for i in range(N):
    A[i] = inp()
    for _ in range(A[i]):
        x, y = inp_list()
        xx[i].append(x)
        yy[i].append(y)

# ↑ inputs
# ↓ main process

# {0, 1, ..., N-1} の集合の bit 全探索
ans = 0
for bit in range(1 << N):
    """
        例： bit == 10 のとき、2進数では 001010 
            右から人 1, 2, ..., 6 と対応させる。
    """
    is_inconsistent = False
    # 整数 bit を２進数表示し、右から 1/0 を True/False に置換
    is_honest = [(bit >> i) & 1 for i in range(N)]
    for i in range(N):
        if not is_honest[i]: continue
        for (x, y) in zip(xx[i], yy[i]):
            if is_honest[x - 1] != y:
                is_inconsistent = True # 矛盾
    if not is_inconsistent:
        ans = max(ans, sum(is_honest))
print(ans)

Submission status: Accepted

Solution code:
from collections import  deque
import sys
import bisect
# import math
import itertools
from queue import deque
# from math import gcd

INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

# def lcm(x, y): return (x * y) // gcd(x, y)

N = inp()
A = [0 for _ in range(N)]
xx = [[] for _ in range(N)]
yy = [[] for _ in range(N)]

for i in range(N):
    A[i] = inp()
    for _ in range(A[i]):
        x, y = inp_list()
        xx[i].append(x)
        yy[i].append(y)

# ↑ inputs
# ↓ main process

honest_count = 0
# {0, 1, ..., N-1} の集合の bit 全探索
ans = 0
for bit in range(1 << N):
    """
        例： bit == 10 のとき、2進数では 001010 
            右から人 1, 2, ..., 6 と対応させる。
    """
    ok = True
    is_honest = [(bit >> i) & 1 for i in range(N)] # bit を 1 右にシフトさせたものの2^0の位が1なら True
    for i in range(N):
        if not is_honest[i]: continue
        for (x, y) in zip(xx[i], yy[i]):
            if is_honest[x - 1] != y:
                ok = False
    if ok:
        ans = max(ans, sum(is_honest))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

l = []
ans = 0
for i in range(2**n):
	l = []
	torf = [0 for _ in range(n)]
	# 正直者を1にする
	for j in range(n):
			if i & (1<<j):
				torf[j] = 1
				l.append(j)
	flag = False
	for j in range(n):
		# 正直者の証言が正しいかチェック
		if torf[j] == 1:
			for k in range(a[j]):
				if torf[xy[j][k][0]-1] != xy[j][k][1]:
					flag = True
					break
		# 嘘つきの証言が嘘かチェック
		"""
		else:
			for k in range(a[j]):
				if torf[xy[j][k][0]-1] == xy[j][k][1]:
					flag = True
					break
		"""
		if flag:
			break
	if not flag:
		ans = max(ans,len(l))

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
  flag = 0
  count = 0
  for j in range(n):
    if ((i>>j)&1)==1 and flag==0:
      for k,l in word[j]:
        if ((i>>(k-1))&1) != l:
          flag = 1 ## tell a lie
          break
  if flag==0:
    count = bin(i).count('1')
    ans = max(ans,count)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = []
xy = []

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

ans = 0
for i in range(2**n):
    # 正直者リスト
    _true = [0]*n
    bl = True
    for j in range(n):
        if (i >> j) & 1:
            _true[j] = 1
    for j in range(n):
        # 正直者の話だけ聞く
        if _true[j] == 1:
            # 証言を１つずつ確認して矛盾があったら終わり
            for x, y in xy[j]:
                if _true[x-1] != y:
                    bl = False
                    break
    if bl:
        ans = max(ans, sum(_true))

print(ans)

Submission status: Accepted

Solution code:

N = int(input())
A = []
xy = []
for i in range(N):
    Ai = int(input())
    A.append(Ai)
    xyi = [list(map(int,input().split())) for i in range(Ai)]
    xy.append(xyi)




ans = 0
for i in range(2**N):
    s = str(bin(i))[2:].zfill(N)
    flag = True
    d = [k for k in range(len(s)) if s[k]=='1']
    honest = [1 if s[k]=='1' else 0 for k in range(len(s))]
    for j in d:
        for k in range(A[j]):
            if honest[xy[j][k][0]-1]^xy[j][k][1]==1:
                flag = False
                break
            else:
                continue
        if not flag:
            break
    if flag:
        ans = max(ans,len(d))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

max_res = 0
for i in range(2 ** n):           
    ok_flg = True
    bin_i = format(i, "015b")[::-1] 
                                    
    for j in range(n):
        for x, y in xy_arr[j]: 
            if bin_i[j] == "1" and y != int(bin_i[x - 1]):
                ok_flg = False
                break
        else:
            continue
        break
        
    if ok_flg:
        res = sum(int(x) for x in bin_i)
        max_res = max(max_res, res)
        
print(max_res)

Submission status: Accepted

Solution code:
import sys,itertools as it
f=sys.stdin.readline
n=int(f())
ll=[]
for i in range(n):
  a=int(f())
  for _ in range(a):
    x,y=map(int,f().split())
    ll+=[(i,x-1,y)]
c=0
for p in it.product([0,1],repeat=n):
  if all(p[i]<1 or p[x]==y for i,x,y in ll):
    c=max(c,sum(p))
print(c)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
ll=[]
for i in range(n):
  a=int(input())
  for _ in range(a):
    x,y=map(int,input().split())
    ll+=[(i,x-1,y)]
c=0
for p in range(2**n):
  if all(p>>i&1<1 or p>>x&1==y for i,x,y in ll):
    c=max(c,sum(p>>i&1 for i in range(n)))
print(c)

Submission status: Accepted

Solution code:
import sys,itertools as it
input=sys.stdin.readline
n=int(input())
ll=[]
for i in range(n):
  a=int(input())
  for _ in range(a):
    x,y=map(int,input().split())
    ll+=[(i,x-1,y)]
c=0
for p in it.product([0,1],repeat=n):
  b=1
  for i,x,y in ll:
    if p[i] and p[x]!=y:
      b=0
      break
  if b: c=max(c,sum(p))
print(c)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
ll=[]
for i in range(n):
  a=int(input())
  for _ in range(a):
    x,y=map(int,input().split())
    ll+=[(i,x-1,y)]
c=0
for p in range(2**n):
  b=1
  for i,x,y in ll:
    if p>>i&1 and p>>x&1!=y:
      b=0
      break
  if b: c=max(c,sum(p>>i&1 for i in range(n)))
print(c)

Submission status: Accepted

Solution code:
N = int(input())
XY = [[] for _ in range(N)]
for i in range(N):
    A = int(input())
    for _ in range(A):
        x, y = map(int, input().split())
        XY[i].append((x-1,y))
ans = 0
for bit in range(1<<N):
    cnt = bin(bit).count('1')
    ok = True
    for i in range(N):
        if bit&(1<<i):
            for x,y in XY[i]:
                if y == 1:
                    if not bit&(1<<x):
                        ok = False
                        break
                else:
                    if bit&(1<<x):
                        ok = False
                        break
            if not ok:
                break
    if ok:
        ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [0]*N
X = []
Y = []
for i in range(N):
    A[i] = int(input())
    X.append([])
    Y.append([])
    for j in range(A[i]):
        x, y = map(int, input().split())
        X[i].append(x-1)
        Y[i].append(y)
ans = 0
for bit in range(1<<N):
    honest = 0
    ok = True
    for i in range(N):
        if bit&(1<<i):
            honest += 1
            for j in range(A[i]):
                if Y[i][j] == 0:
                    if bit&(1<<X[i][j]):
                        ok = False
                        break
                else:
                    if not bit&(1<<X[i][j]):
                        ok = False
                        break
            if not ok:
                break
    if ok:
        ans = max(ans, honest)
print(ans)

Submission status: Accepted

Solution code:
# ABC147C - HonestOrUnkind2

from collections import defaultdict
import itertools

n = int(input())
m = [[]for i in range(n)]

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

#print(m)
ans=0
for i in itertools.product([0,1],repeat=n):
    k=1
    for j in itertools.compress([ii for ii in range(n)],i):
        for x,y in m[j]:
            if i[x] !=-1 and i[x]!=y:
                k=0
                break
        if not k:
            break
    #print(i)
    if k:
        ans=max(ans,sum(i))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [0]*N
X = []
Y = []
for i in range(N):
    A[i] = int(input())
    X.append([])
    Y.append([])
    for j in range(A[i]):
        x, y = map(int, input().split())
        X[i].append(x-1)
        Y[i].append(y)
ans = 0
for bit in range(1<<N):
    honest = 0
    ok = True
    for i in range(N):
        if bit&(1<<i):
            honest += 1
            for j in range(A[i]):
                if Y[i][j] == 0:
                    if bit&(1<<X[i][j]):
                        ok = False
                else:
                    if not bit&(1<<X[i][j]):
                        ok = False
    if ok:
        ans = max(ans, honest)
print(ans)

Submission status: Accepted

Solution code:
def is_nth_bit_set(x, n):
    if x & (1 << n):
        return 1
    else:
        return 0


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

ans = 0
for i in range(2 ** N):
    judge = [None] * N
    flag = True
    for j in range(N):
        honest = is_nth_bit_set(i, j)
        judge[j] = honest

    for j in range(N):
        honest = judge[j]
        if not honest:
            continue
        for x, y in comment[j]:
            if honest:
                if judge[x] == y:
                    continue
                else:
                    flag = False
                    break
    if not flag:
        continue

    tmp = sum(judge)
    if tmp > ans:
        ans = tmp
print(ans)

Submission status: Accepted

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

def main():
    n = int(input())
    #ビット全探索を行う
    import itertools
    li = list(itertools.product([0, 1], repeat=n)) # ０が不親切もの、１が親切もの

    #dd[i][x] = y:人iが人xをy（０なら不親切,１なら親切)だと思っていることを収納
    NIL = -1
    dd = [[NIL]*n for _ in range(n)]
    for i in range(n):
        a = int(input())
        for j in range(a):
            x, y = map(int, input().split())
            x = x-1
            dd[i][x] = y


    from copy import deepcopy
    max_sum = 0 #親切者の数の最大値
    for i in li: # i には親切者のタプルが入っている
        ppp = 0
        for ggg in i:
            ppp += ggg
        if ppp <= max_sum:
            continue
        sum_ = 0
        flag = True
        for k in range(len(i)): #全員の証言が矛盾しないかを考える
            if i[k] == 0: # 不親切ものの場合
                continue
            else: #以下k人目の証言を考える
                sum_ += 1
                for l in range(n):
                    if dd[k][l] != NIL and dd[k][l] != i[l]: #証言と一致していない場合
                        flag = False
                        break
        if flag:
            max_sum = max(max_sum, sum_)

    print(max_sum)
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

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


def check(i):
    honests = []
    for j in range(n):
        if (i >> j) & 1:
            honests.append(j)

    for j in honests:
        for k in range(len(testimony[j])):
            if testimony[j][k] == 1 and k not in honests:
                return False
            if testimony[j][k] == 0 and k in honests:
                return False

    return True


ans = 0
for i in range(1, 2 << (n-1)):
    if check(i):
        count = 0
        for j in range(n):
            if (i >> j) & 1:
                count += 1
        ans = max(ans, count)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
word = []
for _ in range(n):
    a = int(input())
    l = [list(map(int,list(input().split()))) for _ in range(a)]
    word.append(l)

ans = 0
for i in range(2**n):
    flag = 0
    for j in range(n):
        if (i>>j) & 1 == 1 and flag == 0:
            for k,v in word[j]:
                if i>>(k-1) & 1 != v:
                    flag = 1
                    break

    if flag == 0:
        ans = max(ans,bin(i).count('1'))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
opinion = [{} for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        opinion[i][x-1] = y
ans = 0
for i in range(2**n):
    honest = [0]*n
    j = 0
    while i > 0:
        honest[j] = i&1
        j += 1
        i = i >> 1
    flag = 1
    for j in range(n):
        if honest[j]:
            for x,y in opinion[j].items():
                if honest[x] != y:
                    flag = 0
    if flag:
        ans = max(ans, honest.count(1))
print(ans)

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:  # 矛盾がある場合はflag == 1になる
        honest = max(honest, bin(i)[2:].count('1'))  # 1の数をカウントし最大となるものを選択
print(honest)

Submission status: Accepted

Solution code:
import sys
import numpy as np 

n = int(sys.stdin.readline().rstrip())
graph = [None] * n
for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    if not a: continue
    graph[i] = np.array([sys.stdin.readline().split() for _ in range(a)], dtype=np.int16).T

def main():
    comb = (np.arange(1 << n)[:, None] >> np.arange(n) & 1).astype(np.bool)
    ok = np.full(1 << n, True, dtype=np.bool)
    for i in range(n):
        if graph[i] is None: continue
        x, y = graph[i]
        ok &= ~comb[:, i] | np.all(comb[:, x-1] == y.astype(np.bool), axis=1)

    print(np.amax(comb[ok].sum(axis=1)))

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
rela = [[0] * N for i in range(N)]
for i in range(N):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        x -= 1
        if y == 1:
            rela[i][x] = 1
        else:
            rela[i][x] = -1  
def kensyou(person):
    for i in range(N):
        for j in range(N):
            if person[i] == 1:
                if rela[i][j] == 1:
                    if person[j] == -1:
                        return 0
                elif rela[i][j] == -1:
                    if person[j] == 1:
                        return 0
    return 1
ans = 0
for i in range(2 ** N):
    person = []
    for j in range(N):
        if ((i >> j) & 1):
            person.append(1)
        else:
            person.append(-1)
    #print(kensyou(person))
    if kensyou(person):
        ans = max(ans, person.count(1))
print(ans)

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    """n = int(input())
    v = []
    for i in range(n):
        v.append([])
    for i in range(n):
        A = int(input())
        for j in range(A):
            human,lie = readInts() # human : 人  lie: 1 が正直者 0 が不親切
            v[human-1].append([human - 1,lie]) # human : 0-based index
    print(v)
    def judge(bit):
        # i 人目の証言を検証する
        print(bin(bit))
        for i in range(n):
            # 証言は意味がないな
            #if not (bit & (1<<i)): # フラグのたってるやつだけみてる
                #continue
            for x,y in v[i]:
                print(x,y,bit)
                # y = 1 なのに 不親切 だったらだめ
                if y == 1 and not (bit & (1 << x)):
                    return False
                # y = 0 なのに 正直ならだめ
                if y == 0 and (bit & (1 << x)):
                    return False
        return True
    res = 0
    for bit in range(1 << n):
        if judge(bit):
            count = 0
            for i in range(n):
                if bit & (1 << i):
                    count += 1
            res = max(res,count)
    print(res)
    """
    n = int(input())
    xy = [[] for _ in range(n)]
    for i in range(n):
        A = int(input())
        for j in range(A):
            x,y = readInts()
            xy[i].append([x,y])
    ans = 0
    for b in range(1 << n):
        for m in range(n):
            if (b >> m) & 1:
                for x,y in xy[m]:
                    if y != (b >> (x-1) & 1):
                        break
                else:
                    continue
                break
        else:
            ans = max(ans,bin(b).count("1"))
    print(ans)
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
N = int(input())

g_list = [[-1 for i in range(N)] for j in range(N)]

for i in range(N):
    m = int(input())
    for j in range(m):
        a_x = list(map(int, input().split()))
        a = a_x[0]
        a -= 1
        x = a_x[1]
        g_list[i][a] = x

ans = 0

for i in range(1 << N):
    d = [0 for l in range(N)]
    for j in range(N):
        if i >> j & 1:
            d[j] = 1
    ok = True
    for j in range(N):
        if d[j]:
            for k in range(N):
                if g_list[j][k] == -1:
                    continue
                if g_list[j][k] != d[k]:
                    ok = False
    if ok:
        total = list(bin(i)[2:].rjust(N, '0'))
        count = 0
        for t in total:
            if t == '1':
                count += 1
        ans = max(ans, count)

print(ans)

Submission status: Accepted

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

def is_valid(s):
	for i in range(n):
		if s[i] == 0:
			continue
		for x, y in a[i]:
			if s[x] != y:
				return False
	return True

ans = 0
for i in range(1 << n):
	s = [0] * n
	for j in range(n):
		if (i >> j) & 1:
			s[j] = 1
	if is_valid(s):
		ans = max(ans, sum(s))

print(ans)

Submission status: Accepted

Solution code:
import collections

N = int(input())
edges = [[None] * N for _ in range(N)]
for i in range(N):
    num_prop = int(input())
    for j in range(num_prop):
        x, y = map(int, input().split())
        edges[i][x-1] = y


def check(hs, us):
    for h in hs:
        for h2 in hs:
            if edges[h][h2] == 0:
                return False
        for u in us:
            if edges[h][u] == 1:
                return False
    return True


def search():
    maxv = 0
    maxhs = None
    maxus = None
    for i in range(1 << N):
        hs = []
        us = []
        for j in range(N):
            if (i >> j) & 1 == 1:
                hs.append(j)
            else:
                us.append(j)
        if check(hs, us):
            if maxv < len(hs):
                maxv = len(hs)
                maxhs = hs
                maxus = us
    return maxv  #, [x+1 for x in maxhs], [x+1 for x in maxus]

print(search())

Submission status: Accepted

Solution code:
n = int(input())
xy = [[] for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        xy[i].append((x-1,y))
ans = 0
for i in range(2**n):
    tf = [0]*n #正直者1
    flag = True
    for j in range(n):
        if (i>>j)&1:
            tf[j] = 1
    for j in range(n):
        if tf[j]==1:
            for x,y in xy[j]:
                if tf[x] !=y:#正直者の言うことが矛盾してたら
                    flag = False
                    break
    if flag:ans = max(ans,sum(tf))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

"""
    矛盾したらFalse
    矛盾しなければTrue
    正直者と仮定した者の証言
        正直&正直者と仮定されている
        不親切&不親切と仮定されている
"""
def check(i, xiyj, HoU):
    # XOR
    if HoU ^ ((i >> xiyj) & 1):
        return False

    return True

max_honest = 0
for i in range(2 ** len(XY)):
    count = 0
    is_contradiction = True
    for j in range(len(XY)):
        # 正直者と仮定したときだけ採用
        if not ((i >> j) & 1): continue
        count+=1
        for k in range(len(XY[j])):
            xiyj = XY[j][k][0] - 1
            HoU = XY[j][k][1]
            
            if not check(i, xiyj, HoU):
                is_contradiction = False
                break # TLE対策
                
        if not is_contradiction:
            break # TLE対策

    # 矛盾がなく、正直者の数が更新できれば更新
    if is_contradiction and (count > max_honest):
        max_honest =count
            
print(max_honest)

Submission status: Accepted

Solution code:
n = int(input())

XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        xy.append(list(map(int, input().split())))
    
    XY.append(xy)
    
def check(i, xiyj, HoU):
    # 矛盾したらFalse 正直者と仮定した証言より 正直&正直者と仮定されている / 不親切&不親切と仮定されている True
    if ((i >> xiyj) & 1) ^ HoU:
        return False

    return True
    
max_honest = 0
for i in range(2 ** len(XY)):
    count = 0
    is_contradiction = True
    for j in range(len(XY)):
        # 正直者と仮定したときだけ採用
        if not ((i >> j) & 1): continue
        for k in range(len(XY[j])):
            xiyj = XY[j][k][0] - 1
            HoU = XY[j][k][1]
            
            if not check(i, xiyj, HoU):
                is_contradiction = False
                break
                
        if not is_contradiction:
            break

    if is_contradiction:
        for j in range(len(XY)):
            if ((i >> j) & 1): count+=1 
                
        if count > max_honest:
            max_honest =count
            
print(max_honest)

Submission status: Accepted

Solution code:
n = int(input())
 
XY = []
for i in range(n):
    a = int(input())
    xy = []
    for j in range(a):
        xy.append(list(map(int, input().split())))
    
    XY.append(xy)
    
def check(i, xiyj, HoU):
    # 矛盾したらFalse 正直者と仮定した証言より 正直&正直者と仮定されている / 不親切&不親切と仮定されている True
    if ((i >> xiyj) & 1) ^ HoU:
        return False
 
    return True
    
max_honest = 0
for i in range(2 ** len(XY)):
    count = 0
    honest = [0] * len(XY)
    is_contradiction = True
    for j in range(len(XY)):
        # 正直者と仮定したときだけ採用
        if not ((i >> j) & 1): continue
        for k in range(len(XY[j])):
            xiyj = XY[j][k][0] - 1
            HoU = XY[j][k][1]
            
            if not check(i, xiyj, HoU):
                is_contradiction = False
 
    if is_contradiction:
        for j in range(len(XY)):
            if ((i >> j) & 1): count+=1 
                
        if count > max_honest:
            max_honest =count
            
print(max_honest)

Submission status: Accepted

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

ans = 0

for i in range(2**n):
    flag = True
    for j in range(n):  # 人ｊについて
        if (i >> j) & 1 == 1:  # 人jが正直ならば
            for k in range(a_list[j]):  # 人jの証言kについて
                if xy_list[j][k][1] == 1:
                    m = xy_list[j][k][0]
                    if (i >> m-1) & 1 != 1:  # 矛盾発生（正直者のjの証言で正直者と確定したｍが不親切だった）
                        flag = False
                        break

                elif xy_list[j][k][1] == 0:
                    m = xy_list[j][k][0]
                    if (i >> m-1) & 1 == 1:
                        flag = False
                        break
    if flag:
        i_bin = format(i, 'b')
        if ans < i_bin.count('1'):
            ans = i_bin.count('1')

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N=int(input())
    A = []
    for i in range(N):
        a = int(input())
        A.append([])
        xy = None
        for j in range(a):
            xy = list(map(int,input().split()))
            A[i].append(xy)
    #print(A)

    c=0
    for bit in range(1,2**N):
        bs = np.array(list(map(int,list("0"*N+bin(bit)[2:])[-N:])))
        #print(bs)
        ok=True
        for i in range(N):
            if bs[i]:
                for j in range(len(A[i])):
                    x, y = A[i][j]
                    if y==1 and bs[x-1]==0:
                        ok=False
                        break
                    if y==0 and bs[x-1]!=0:
                        ok=False
                        break
                else:
                    continue
                break

        if ok:
            #print("OK")
            #print(bs)
            c = max(c, bs.sum())

    print(c)        


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for i in range(2**n):
  flag = 0
  count = 0
  for j in range(n):
    if ((i>>j)&1)==1 and flag==0:
      for k,l in word[j]:
        if ((i>>(k-1))&1) != l:
          flag = 1 ## tell a lie
          break
  if flag==0:
    count = bin(i).count('1')
    ans = max(ans,count)
print(ans)

Submission status: Accepted

Solution code:
num = int(input())
coms = []

ans_num = 0

for com in range(num):
    b = []
    n = int(input())
    for _ in range(n):
        xi,yi = [int(j) for j in input().split(" ")]
        b.append([int(xi) - 1, int(yi)])
    coms.append(b)

for i in range(2 ** num):
    selects = []
    ans_array = [0 for _ in range(num)]
    indexes = []
    flag = True

    #組み合わせの作成
    for j in range(num):
        if((i >> j) & 1):
            selects.append(coms[j])
            indexes.append(j)
            ans_array[j] = 1
    
    for index in indexes:
        for com in coms[index]:
            if ans_array[com[0]] != com[1]:
                flag = False
                break

    if flag and (len(indexes) >= ans_num):
        ans_num = len(indexes)

print(ans_num)

Submission status: Accepted

Solution code:
N=int(input())

answers=[]
counts=[]


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

#print(answers)
for i in range(pow(2,N)):
    hypo=str(bin(i))[2:].rjust(N,"0")
    judge=True
    count=0
    #print(hypo)
    for n in range(N):
        if judge==False:
            break
        elif hypo[n]=="1":
            count+=1
            for ans in answers[n]:
                if hypo[ans[0]-1]==str(ans[1]):
                    pass
                else:
                    judge=False
                    break
    if judge==False:
        pass
    else:
        counts.append(count)
#print(counts)
print(max(counts))

Submission status: Accepted

Solution code:
N=int(input())
xy=[[-1]*N for i in range(N)]
count=0
for i in range(N):
    A=int(input())
    for j in range(A):
        x,y=map(int,input().split())
        xy[i][x-1]=y
for i in range(1<<N):
    honest=[0]*N
    for j in range(N):
        if (i>>j)&1:
            honest[j]=1
    flag=True
    for j in range(N):
        if honest[j]:
            for k in range(N):
                if xy[j][k]==-1:
                    continue
                if xy[j][k]!=honest[k]:
                    flag=False
    if flag:
        count=max(count,honest.count(1))
print(count)

Submission status: Accepted

Solution code:
N=int(input())
a=[]
for i in range(N):
	A=int(input())
	B=[]
	for i in range(A):
		b=list(map(int,input().split()))
		B.append(b)
	a.append(B)
ans=0
for i in range(2**N):
	bi=list(str(bin(i)))
	bi=bi[2:]
	bi=[0]*(N-len(bi))+bi
	bi=list(map(int,bi))
	p=1
	for j in range(N):
		if bi[j]==1:
			for k in range(len(a[j])):
				m=a[j][k][0]
				n=a[j][k][1]
				if bi[m-1]!=n:
					p=0
					break
	if p==1:
		ans=max(ans,sum(bi))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

A = []

for _ in range(n):
    t = int(input())
    A.append([list(map(int, input().split())) for _ in range(t)])

ans = 0
max = 0
flag = 0

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