Problem:


Score : 300 points

Problem Statement

We have N switches with "on" and "off" state, and M bulbs. The switches are numbered 1 to N, and the bulbs are numbered 1 to M.

Bulb i is connected to k_i switches: Switch s_{i1}, s_{i2}, ..., and s_{ik_i}. It is lighted when the number of switches that are "on" among these switches is congruent to p_i modulo 2.

How many combinations of "on" and "off" states of the switches light all the bulbs?

Constraints

1 \leq N, M \leq 10

1 \leq k_i \leq N

1 \leq s_{ij} \leq N

s_{ia} \neq s_{ib} (a \neq b)

p_i is 0 or 1.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
k_1 s_{11} s_{12} ... s_{1k_1}
:
k_M s_{M1} s_{M2} ... s_{Mk_M}
p_1 p_2 ... p_M

Output

Print the number of combinations of "on" and "off" states of the switches that light all the bulbs.

Sample Input 1

2 2
2 1 2
1 2
0 1

Sample Output 1

1

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

There are four possible combinations of states of (Switch 1, Switch 2): (on, on), (on, off), (off, on) and (off, off). Among them, only (on, on) lights all the bulbs, so we should print 1.

Sample Input 2

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

Sample Output 2

0

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an even number of switches that are "on" among the following: Switch 1.

Bulb 3 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

Switch 1 has to be "off" to light Bulb 2 and Switch 2 has to be "on" to light Bulb 3, but then Bulb 1 will not be lighted. Thus, there are no combinations of states of the switches that light all the bulbs, so we should print 0.

Sample Input 3

5 2
3 1 2 5
2 2 3
1 0

Sample Output 3

8



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


Sample output:
1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# coding: UTF-8
 
n,m = map(int,input().split())
 
s = []
for i in range(m):
    s += [tuple(map(int,input().split())),]
 
p = list(map(int,input().split()))
 
ret = 0
all = [(str(bin(i)))[2:].zfill(m) for i in range(2 ** n)]
all = [[int(i) for i in case] for case in all]
for case in all:
    flag = 0
    for num,i in enumerate(s):
 
        sw = [0 for z in range(n)]
        for k in i[1:]:
            sw[k-1] = 1
 
        if (sum(i*j for i,j in zip(sw,case)) % 2) != p[num]:
            flag = 1
           
    if flag == 0:
        ret += 1
 
print(ret)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# coding: UTF-8

n,m = map(int,input().split())

s = []
for i in range(m):
    s += [tuple(map(int,input().split())),]

p = list(map(int,input().split()))

ret = 0
all = [(str(bin(i)))[2:].zfill(m) for i in range(2 ** n)]
all = [[int(i) for i in case] for case in all]
for case in all:
    flag = 0
    for num,i in enumerate(s):
        if flag == 1:
            continue


        sw = [0 for z in range(n)]
        for k in i[1:]:
            sw[k-1] = 1

        if (sum(i*j for i,j in zip(sw,case)) % 2) != p[num]:
            flag = 1
           
    if flag == 0:
        ret += 1

print(ret)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# coding: UTF-8

n,m = map(int,input().split())

s = []
for i in range(m):
    s += [tuple(map(int,input().split())),]

p = list(map(int,input().split()))

ret = 0
all = [(str(bin(i)))[2:].zfill(m) for i in range(2 ** n)]
all = [[int(i) for i in case] for case in all]
for case in all:
    flag = 0
    for num,i in enumerate(s):
        if flag == 1:
            continue

        sw = [0 for z in range(n)]
        for k in i[1:]:
            sw[k-1] = 1
        if (sum(i*j for i,j in zip(sw,case)) % 2) != p[num]:
            flag = 1
           
    if flag == 0:
        ret += 1

print(ret)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
t = []

for i in range(m):
    t.append(list(map(int,input().split())))
q = list(map(int,input().split()))

x = 0
import math


for switch_cond in range(2**n):
    s = []

    for i in range(n):
        if switch_cond%2 == 0:
            s.append(0)
            switch_cond = switch_cond//2
        else:
            s.append(1)
            switch_cond = (switch_cond-1)//2
    #print("s",s)
    for j in range(m):
        #print("t[",j,"]",t[j])
        for r in range(n):
            if r+1 not in t[j][1:]:
                s[r]=0
        if q[j]%2!=s.count(1)%2:
            break
    else:
        x += 1
print(x)

Submission status: Wrong Answer

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

l = max(ks[0])
for m in range(1,M):
    l = max(l,max(ks[m]))

ans = 0

for i in range(1 << l):
    cnt_on = [0]*M
    for j in range(l):
        if ((i >> j) & 1) == 1:
            for m in range(M):
                cnt_on[m] += ks[m][1:].count(j+1)

    c = 0
    for m in range(M):
        if cnt_on[m]%2 == p[m]:
            c += 1
    
    if c == M:
        ans += 1


print(ans)

Submission status: Wrong Answer

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

l = max(ks[0])
for m in range(1,M):
    l = max(l,max(ks[m]))

ans = 0

for i in range(1 << l):
    cnt_on = [0]*M
    for j in range(l):
        if ((i >> j) & 1) == 1:
            for m in range(M):
                cnt_on[m]+=ks[m][1:].count(j+1)

    f = True
    for m in range(M):
        if cnt_on[m]%2 != p[m]:
            f = False
            break
    
    if f:
        ans += 1


print(ans)

Submission status: Wrong Answer

Solution code:
I=lambda:list(map(int,input().split()))
n,m=I()
s=eval('I(),'*m)
p=I()
a=0
r=range
for i in r(1<<n):
 c=[0]*m
 for j in r(n):
  for k in r(m):c[k]+=i>>j&j+1in s[k][1:]
 a+=all(j==i%2for i,j in zip(c,p))
print(a)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
mat = np.zeros((M,N))
for i in range(M):
    slist = list(map(int, input().split()))
    for j in slist[1:]:
        mat[i,j-1] = 1
plist = list(map(int, input().split()))
mat = np.append(mat, np.array([plist]).T, axis=1)
def power_set(N):
    p_sets = [[]]
    item = [i for i in range(N)]
    for i in item:
        temp = []
        for j in p_sets:
            temp += [ j+[i] ]
        p_sets += temp
    return p_sets
ret = 0
for swi in power_set(N)[1:]:
    tm_mat = mat[:,swi+[N]]
    if sum([(np.sum(i) % 2) == 0 for i in tm_mat]) == M:
        ret += 1
print(ret)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
k = []
lis = []
P = []
for _ in range(M):
    x = list(map(int, input().split()))
    k.append(x[0])
    lis.append(x[1:])
for p in map(int, input().split()):
    P.append(p)
count = 0
for i in range(2**N):
    flag = True
    string = str(bin(i)[2:])[::-1]
    for index in range(M):
        total = 0
        for s in lis[index]:
            if s < len(string):
                if string[s - 1] == '1':
                    total += 1
        if total % 2 != P[index]:
            flag = False
            break
    if flag:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
lamplist = [0]*M
for i in range(M):
    A = list(map(int, input().split()))
    lamplist[i] = A
oddeven_ans = list(map(int, input().split()))

switch = np.zeros(N)
ans = 0
numofswitch = np.zeros(M)

for s in range(M):
    numofswitch[s] = lamplist[s][0]
    del lamplist[s][0]

for j in range(2 ** N):
    ansflag = 0
    oddeven = 0
    for k in range(N):
        switch[k] = j % 2
        j //= 2
    for p in range(M):
        for r in lamplist[p]:
            if switch[r-1] > 0:
                oddeven += 1

        if oddeven % 2 != oddeven_ans[p]:
            ansflag = 1
    if ansflag == 0:
        ans += 1

print("{}".format(ans))

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
KS = [list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))

ans = 0
for i in range(1 << N):
  tmp = 1
  cnt = 0
  for j, b in enumerate(KS):
    for bb in b[1:]:
      if (i >> (bb-1)) & 1:
        cnt += 1
    if cnt%2 != P[j]:
      tmp = 0
      break
  if tmp:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
KS = [list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))

ans = 0
for i in range(1 << N):
  tmp = 1
  cnt = 0
  for j, b in enumerate(KS):
    for bb in b:
      if (i >> (bb-1)) & 1:
        cnt += 1
    if cnt%2 != P[j]:
      tmp = 0
      break
  if tmp:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
KS = [list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))

ans = 0
for i in range(1 << N):
  tmp = 1
  cnt = 0
  for j, b in enumerate(KS):
    for bb in b:
      if (i >> bb) & 1:
        cnt += 1
    if cnt%2 != P[j]:
      tmp = 0
      break
  if tmp:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
lamplist = [0]*M
for i in range(M):
    A = list(map(int, input().split()))
    lamplist[i] = A
oddeven_ans = list(map(int, input().split()))

switch = np.zeros(N)
ans = 0
numofswitch = np.zeros(M)

for s in range(M):
    numofswitch[s] = lamplist[s][0]
    del lamplist[s][0]

for j in range(2 ** N):
    ansflag = 0
    oddeven = 0
    for k in range(N):
        switch[k] = j % 2
        j //= 2
    for p in range(M):
        for r in range(int(numofswitch[p])):
            if switch[lamplist[p][r] - 1] > 0:
                oddeven += 1

        if oddeven % 2 == oddeven_ans[p]:
            continue
        else:
            ansflag = 1
    if ansflag == 0:
        ans += 1

print("{}".format(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
lamplist = [0]*M
for i in range(M):
    A = list(map(int, input().split()))
    lamplist[i] = A
oddeven_ans = list(map(int, input().split()))

switch = np.zeros(N)
ans = 0
numofswitch = np.zeros(M)

for s in range(M):
    numofswitch[s] = lamplist[s][0]
    del lamplist[s][0]

for j in range(2 ** N):
    ansflag = 0
    oddeven = 0
    for k in range(N):
        switch[k] = j % 2
        j //= 2
    for p in range(M):
        for r in range(int(numofswitch[p])):
            if switch[lamplist[p][r] - 1] > 0:
                oddeven += 1

        if oddeven % 2 != oddeven_ans[p]:
            ansflag = 1
    if ansflag == 0:
        ans += 1

print("{}".format(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
lamplist = [0]*M
for i in range(M):
    A = list(map(int, input().split()))
    lamplist[i] = A
oddeven_ans = list(map(int, input().split()))

switch = np.zeros(N)
ans = 0
numofswitch = np.zeros(M)

for s in range(M):
    numofswitch[s] = lamplist[s][0]
    del lamplist[s][0]


for j in range(2 ** N):
    ansflag = 0
    oddeven = 0
    for k in range(N):
        switch[k] = j % 2
        j //= 2
    for p in range(M):
        for r in range(int(numofswitch[p])):
            if switch[lamplist[p][r] - 1] == 1:
                oddeven += 1

        if oddeven % 2 != oddeven_ans[p]:
            ansflag = 1
    if ansflag == 0:
        ans += 1

print("{}".format(ans))

Submission status: Wrong Answer

Solution code:
import itertools

N,M = map(int, input().split())
all_lst = []
for i in range(M):
  lst = list(map(int, input().split()))
  all_lst.append(lst[1:])

lst_p = list(map(int, input().split()))

l = [0, 1]
on_off = list(itertools.product(l, repeat=N))

for idx,i in enumerate(on_off):
  ans_lst = []
  for j in range(M):
    sum = 0
    for k in all_lst[j]:
      sum += i[k-1]
    ans_lst.append(sum % 2)
  if(ans_lst == lst_p):
    print(1)
    break
  if ((idx+1) == len(on_off)):
    print(0)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
lamplist = []
for i in range(M):
    A = list(map(int, input().split()))
    lamplist.append(A)
oddeven_ans = list(map(int, input().split()))

switch = np.zeros(N)
ans = 0
numofswitch = np.zeros(M)

for s in range(M):
    numofswitch[s] = lamplist[s][0]
    del lamplist[s][0]


for j in range(2 ** N):
    ansflag = 0
    oddeven = 0
    for k in range(N):
        switch[k] = j % 2
        j //= 2
    for p in range(M):
        for r in range(int(numofswitch[p])):
            if switch[lamplist[p][r] - 1] == 1:
                oddeven += 1

        if oddeven % 2 != oddeven_ans[p]:
            ansflag = 1
    if ansflag == 0:
        ans += 1

print("{}".format(ans))

Submission status: Wrong Answer

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

N, M = map(int, input().split())
lights = [map(int, input().split()[1:]) for i in range(M)]
p = list(map(int, input().split()))

combi = 0
for i in range(1<<N):
    flag = True
    for j, switch in enumerate(lights):
        if sum([1 for s in switch if (i>>(s-1)) & 1 == 1])%2 != p[j]:
            flag = False
            break
    if flag:
        combi += 1

print(combi)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X=[]
for i in range(M):
    X.append(list(map(int, input().split())))
P=list(map(int, input().split()))
ans=0
odd=0
even=0
key='{:0'+str(N)+"b}"
for k in range(2**N):
    
    switch=list(key.format(k))
    for i in range(M):
        
        
        if P[i]==1:
            odd=0
            for j in range(X[i][0]):
                odd+=int(switch[ X[i][j+1]-1] )
            if odd%2==0:
                break
            
        else:
            even=0
            for j in range(X[i][0]):
                even+=int(switch[ X[i][j+1]-1] )
            if even%2==1:
                break
    
    if odd%2==1 and even%2==0:
        ans+=1
        #print(X[i],switch,odd,even)
            
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split())
  
dict_rel = dict()
for i in range(M):
  dict_rel[i+1] = [int(j) for j in input().split()][1:]
list_cond = [int(i) for i in input().split()]

#print(dict_rel)
#print(list_cond)

list_pattern = [[] for j in range(2**N)]

for i in range(len(list_pattern)):
  b = bin(i)[2:].zfill(N)
  list_pattern[i] = [int(k) for k in b]

#print(list_pattern)

num_full = 0
for pattern in list_pattern:
  flg = True
  for light in dict_rel.keys():
    num_on = 0
    for i in range(len(dict_rel[light])):
      if pattern[i-1] == 1:
        num_on += 1
    if list_cond[light-1] != num_on%2:
      flg = False
      #break
  if flg == True:
    num_full += 1

print(num_full)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
s = []
for i in range(M):
    t = []
    ks = list(map(int, input().split()))[1:]
    for j in range(N):
        if j+1 in ks:
            t += [1]
        else:
            t += [0]
    s.append(t)
p = list(map(int, input().split()))
A = np.array(s)
for i in range(M):
    s[i] += [p[i]]
Ab = np.array(s)
rank_A = np.linalg.matrix_rank(A)
rank_Ab = np.linalg.matrix_rank(Ab)
if rank_A == rank_Ab:
    print(2 ** (N - rank_A))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
lamplist = []
for i in range(M):
    A = list(map(int, input().split()))
    lamplist.append(A)
oddeven_ans = list(map(int, input().split()))

switch = np.zeros(N)
ans = 0
numofswitch = np.zeros(M)

for s in range(M):
    numofswitch[s] = lamplist[s][0]
    del lamplist[s][0]


for j in range(2 ** N):
    ansflag = 0
    oddeven = 0
    for k in range(N):
        switch[k] = j % 2
        j //= 2
    for p in range(M):
        for r in range(int(numofswitch[p])):
            if switch[lamplist[p][r] - 1] == 1:
                oddeven += 1

        if (int(oddeven % 2)) != int(oddeven_ans[p]):
            ansflag = 1
    if ansflag == 0:
        ans += 1

print("{}".format(ans))

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split())
  
dict_rel = dict()
for i in range(M):
  dict_rel[i+1] = [int(j) for j in input().split()][1:]
list_cond = [int(i) for i in input().split()]

#print(dict_rel)
#print(list_cond)

list_pattern = [[] for j in range(2**N)]

for i in range(len(list_pattern)):
  b = bin(i)[2:].zfill(N)
  list_pattern[i] = [int(k) for k in b]

#print(list_pattern)

num_full = 0
for pattern in list_pattern:
  flg = True
  for light in dict_rel.keys():
    num_on = 0
    for i in range(len(dict_rel[light])):
      if pattern[i] == 1:
        num_on += 1
    if list_cond[light-1] != num_on%2:
      flg = False
      #break
  if flg == True:
    num_full += 1

print(num_full)

Submission status: Wrong Answer

Solution code:

def input_from_console():
    n, m = map(int, input().split())
    k_list = []

    for i in range(m):
        k, *s_list = map(int, input().split())
        k_list.append((k, s_list))
    p_list = list(map(int, input().split()))
    return n, m, k_list, p_list


def solve(n, m, k_list, p_list):
    def bit_count(bit):
        count = 0
        while bit > 0:
            if bit & 1:
                count += 1
            bit >>= 1
        return count

    selected_light_list = []
    for i in range(m):
        bit_sum = 0
        target = k_list[i][1]
        for j in target:
            bit_sum += 2 ** int(j - 1)
        selected_light_list.append(bit_sum)

    total_count = 0
    for sp in range(1, 2 ** n):
        # print('sp {0:b}'.format(sp))
        condition_list = []
        for i in range(m):
            if  bit_count(selected_light_list[i] & sp) % 2 == p_list[i]:
                condition_list.append(True)
            else:
                condition_list.append(False)
        if all(condition_list):
            total_count += 1
    return total_count


def main():
    n, m, k_list, p_list = input_from_console()
    print(solve(n, m, k_list, p_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X=[]
for i in range(M):
    X.append(list(map(int, input().split())))
P=list(map(int, input().split()))


ans=0
key='{:0'+str(N)+"b}"
for k in range(2**N):
    
    switch=list(key.format(k))
    for i in range(M):
        odd=0
        even=0
        if P[i]==1:
            
            for j in range(X[i][0]):
                odd+=int(switch[ X[i][j+1]-1] )
            if odd%2==0:
                break
            #print(X[i],switch,odd)
        else:
            
            for j in range(X[i][0]):
                even+=int(switch[ X[i][j+1]-1] )
            if even%2==1:
                break
    if odd%2==1 and even%2==0:
        ans+=1
        
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))



denkyu = []
for _ in range(M):
    s_list = list(map(int, input().split()))[1:]
    denkyu.append(s_list)
p_ist = list(map(int, input().split()))

ans = 0

for i in range(1, 2**N, 1):
    binary = format(i, '0{}b'.format(N))
    
    all_shine = True
    for s_list, p in zip(denkyu, p_ist):
        sum_ = 0
        for s in s_list:
            sum_ += int(binary[s-1])
        if sum_ % 2 == p:
            pass
        else:
            all_shine = False
            continue
            
    if all_shine:
        ans += 1
    

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
n, m = map(int, input().split())
kss = []

for mm in range(m):
  ks = list(map(int, input().split()))
  k = ks[0]
  s = ks[1:]
  kss.append(s)
ps = list(map(int, input().split()))


def dfs(kss, ps, ar, n):
  #print(f'dfs called with ar={ar}')
  if len(ar) < n:
    return dfs(kss, ps, ar+[0], n) + dfs(kss, ps, ar+[1], n)
  ok = True
  for m, ks in enumerate(kss):
    sm = 0
    for s in ks:
      sm += ar[s-1]
    if sm % 2 != ps[m-1]:
      ok = False
      break
  #print(f'ar={ar} is {ok}')
  return 1 if ok else 0

count = dfs(kss, ps, [], n)
print(count)

Submission status: Wrong Answer

Solution code:
import itertools

def main():
    n,m=list(map(int,input().split(' ')))
    swich_all=list(itertools.product([0,1],repeat=n))
    swich=[]
    cnt=0
    for i in range(m):
        swich.append(list(map(int,input().split(' '))))
    check_p=list(map(int,input().split(' ')))
    for i in swich_all:
        tmp=0
        check =True
        for j in range(m):
            for k in swich[j][1:]:
                tmp += i[k-1]
            if tmp%2 != check_p[j]:
                check = False
                break
        if check == True:
            cnt +=1

    print(cnt)

main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
b=[0]*m
for i in range(m):
  a=list(map(int,input().split()))
  b[i]=a
p=list(map(int,input().split()))
z=0
for i in range(0,2**n):  
  sl=[int(x) for x in list(str(bin(i+2**n)[2:]))]
  flag=0
  for j in range(m):
    s=0
    for l in range(1,b[j][0]):
      s=s+sl[b[j][l]]
    if s%2!=p[j]:
      flag=1
  if flag==0:
    z=z+1
print(z)

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split())
  
dict_rel = dict()
for i in range(M):
  dict_rel[i+1] = [int(j) for j in input().split()][1:]
list_cond = [int(i) for i in input().split()]

#print(dict_rel)
#print(list_cond)

list_pattern = [[] for j in range(2**N)]

for i in range(len(list_pattern)):
  b = bin(i)[2:].zfill(N)
  list_pattern[i] = [int(k) for k in b]

#print(list_pattern)

num_full = 0
for pattern in list_pattern:
  flg = True
  for light in dict_rel.keys():
    num_on = 0
    for i in range(len(dict_rel[light])):
      if pattern[i] == 1:
        num_on += 1
    if list_cond[light-1] != num_on%2:
      flg = False
      break
  if flg == True:
    num_full += 1

print(num_full)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X=[]
for i in range(M):
    X.append(list(map(int, input().split())))
P=list(map(int, input().split()))



ans=0
key='{:0'+str(N)+"b}"
for i in range(2**N):
    
    switch=list(key.format(i))
    ODD=1
    EVEN=1
    for i in range(M):
        if P[i]==1:
            odd=0
            for j in range(X[i][0]):
                odd+=int(switch[ X[i][j+1]-1] )
            if odd%2==0:
                break
            else:
                ODD*=odd
            
        else:
            even=0
            for j in range(X[i][0]):
                even+=int(switch[ X[i][j+1]-1] )
            if even%2==1:
                break
            else:
                EVEN*=even
                
    if ODD%2==1 and EVEN%2==0:
        ans+=1

print(ans)    
print(ans)

Submission status: Wrong Answer

Solution code:


def input_from_console():
    n, m = map(int, input().split())
    k_list = []

    for i in range(m):
        k, *s_list = map(int, input().split())
        k_list.append((k, s_list))
    p_list = list(map(int, input().split()))
    return n, m, k_list, p_list


def solve(n, m, k_list, p_list):
    def bit_count(bit):
        count = 0
        while bit > 0:
            if bit & 1:
                count += 1
            bit >>= 1
        return count

    selected_light_list = []
    for i in range(m):
        bit_sum = 0
        target = k_list[i][1]
        for j in target:
            bit_sum += 2 ** int(j - 1)
        selected_light_list.append(bit_sum)

    total_count = 0
    for sp in range(1, 2 ** n):
        # print('sp {0:b}'.format(sp))
        condition_list = []
        for i in range(m):
            if selected_light_list[i] & sp > 0 and bit_count(selected_light_list[i] & sp) % 2 == p_list[i] % 2:
                condition_list.append(True)
            else:
                condition_list.append(False)
        if all(condition_list):
            total_count += 1
    return total_count


def main():
    n, m, k_list, p_list = input_from_console()
    print(solve(n, m, k_list, p_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
b=[0]*m
for i in range(m):
  a=list(map(int,input().split()))
  b[i]=a
p=list(map(int,input().split()))
z=0
for i in range(0,2**n):  
  sl=[int(x) for x in list(str(bin(i+2**n)[2:]))]
  flag=0
  for j in range(m):
    s=0
    if b[j][0]==1:
      s=s+sl[b[j][1]]
    for l in range(1,b[j][0]):
      s=s+sl[b[j][l]]
    if s%2!=p[j]:
      flag=1
  if flag==0:
    z=z+1
print(z)

Submission status: Wrong Answer

Solution code:
import itertools

switch, light = map(int, input().split())
ksm = []
for i in range(1, light+1):
    ks = input().split()
    ksm.append(ks)

pm = input().split()

ans = 0
for i in itertools.product([0, 1], repeat=switch):
    isOk = True
    for li in range(light):
        if not isOk:
            break
        p = int(pm[li])
        ks = ksm[li]
        light_sum = 0
        for ksi in range(int(ks[0])):
            light_sum += i[int(ks[ksi + 1]) - 1]
        print("light_sum{0}:{1}".format(li, light_sum))
        if light_sum % 2 != p:
            isOk = False
    if isOk:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

N, M = map(int, input().split())
k = []
for i in range(M):
    tmp = [int(j) for j in input().split()]
    k.append(tmp)

p = [int(i) for i in input().split()]

onoff = [0, 1]
kouho = list(itertools.product(onoff, repeat=N))

ans = 0
for li in kouho:
    flag = True
    for i in range(M):
        end = k[i][0]+1
        sum = 0
        for j in range(1, end):
            sum += li[j-1]
        if sum % 2 != p[i]:
            flag = False
            break
    if flag == True:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
lamplist = []
for i in range(M):
    A = list(map(int, input().split()))
    lamplist.append(A)
oddeven_ans = list(map(int, input().split()))

switch = np.zeros(N)
ans = 0

for j in range(2 ** N):
    flag = 0
    oddeven = 0
    for k in range(N):
        switch[k] = j % 2
        j //= 2
    for p in range(M):
        for r in range(1, lamplist[p][0]+1):

            if switch[lamplist[p][r] - 1] == 1:
                oddeven += 1
        if (int(oddeven % 2)) != int(oddeven_ans[p]):
            flag = 1
    if flag == 0:
        ans += 1

print("{}".format(ans))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
bi_N = [i+1 for i in range(2**N-1)]
ans = 0
l = []
for i in range(M):
  l.append(list(map(int, input().split())))
p = list(map(int, input().split()))
for i in bi_N[::-1]:
  a = format(i,'b')
  a = str(format(a, '0>10'))
  bi_a = [a[i] for i in range(10)]
  for z, (j, k) in enumerate(zip(l,p)):
    x = 0
    o = j[0]
    for y in range(o+1)[1:]:
      x += int(bi_a[-j[y]])
    if x%2 != k:
      break
    if z == M-1:
      ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(a) for a in input().split()]
v = [int(a) for a in input().split()]


cap = min(n, k)
max_val = 0
for left in range(k):
    for right in range(cap - left):
        rest = k - (left + right)
        l_popped = v[:left]
        r_popped = v[-right:] if right > 0 else []
        popped = l_popped + r_popped

        popped.sort()

        first_positive = len(popped)
        for i, value in enumerate(popped):
            if value > 0:
                first_positive = i
                break

        sum_val = sum(popped[min(rest, first_positive):])
        if sum_val > max_val:
            max_val = sum_val

print(max_val)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
bi_N = [i+1 for i in range(2**N-1)]
ans = 0
l = []
for i in range(M):
  l.append(list(map(int, input().split())))
p = list(map(int, input().split()))
for i in bi_N[::-1]:
  a = format(i,'b')
  a = str(format(a, '0>10'))
  bi_a = [a[i] for i in range(10)]
  for z, (j, k) in enumerate(zip(l,p)):
    x = 0
    o = j[0]
    for y in range(o+1)[1:]:
      print(bi_a[-j[y]])
      x += int(bi_a[-j[y]])
    if x%2 != k:
      break
    if z == M-1:
      ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
bi_N = [i+1 for i in range(2**N-1)]
ans = 0
l = []
for i in range(M):
  l.append(list(map(int, input().split())))
p = list(map(int, input().split()))
for i in bi_N[::-1]:
  a = format(i,'b')
  a = str(format(a, '0>10'))
  bi_a = [a[i] for i in range(10)]
  for z, (j, k) in enumerate(zip(l,p)):
    x = 0
    o = j[0]
    for y in range(o)[1:]:
      x += int(bi_a[-j[y]])
    if x%2 != k:
      break
    if z == M-1:
      ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#供養提出
n,m=map(int,input().split())
tmp=[]
k=[]
s=[]
p=[]
S=[]
Ev=0
Od=0
cnt=0
for i in range(m):
    tmp=input().split()
    tmp=[int(k) for k in tmp]
    k.append(tmp[0])
    for j in range(len(tmp)-1):
        s.append(tmp[j+1])
    S.append(s)
    s=[]

p=input().split()
p=[int(i) for i in p]


for i in range(m):
    for j in range(k[i]):
        if S[i][j]%2==0:
            Ev+=1
        else:
            Od+=1
    if p[i]==0:
        cnt+=2**Ev+2**(Od-1)+Ev*Od
    else:
        cnt+=2**Od+Ev*Od
        if Od==0: cnt-=2
    Ev=0
    Od=0
        
print(cnt)
print(k)
print(S)
print(p)

Submission status: Wrong Answer

Solution code:
import math

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

prob = 1
for i in range(m):
    ks = A[i]
    k,s = ks[0],ks[1:]
    p = P[i]
    c = 0
    if p == 0:
        for j in range(0,k+1,2):
            c += math.factorial(k) / (math.factorial(j)*math.factorial(k-j))
    else:
        for j in range(1,k+1,2):
            c += math.factorial(k) / (math.factorial(j)*math.factorial(k-j))
    prob *= c*2**(n-k) / (2**n)
    
print(int(2**n*prob))

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
connections=[]
for _ in range(M):
    connections.append(list(map(int,input().split())))
conditions = list(map(int,input().split()))

ans_cnt = 0
for i in range(2**N):
    condition_cnt = 0
    for j in range(M):

        cnt=0
        for k in connections[j][1:]:
            if (i >> k) & 1:
                cnt += 1
        if cnt%2 == conditions[j]:
            condition_cnt += 1
    if condition_cnt == M:
        ans_cnt += 1

print(ans_cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=[]
for i in range(m):
	data=list(map(int,input().split()))
	s.append(data[1:])
p=list(map(int,input().split()))

tmp=[]
ans=0
for i in range(n**2):
	cir=format(i,'b').zfill(n)
	for j in range(len(s)):
		for k in range(len(s[j])):
			tmp.append(cir[s[j][k]-1])
		if tmp.count('1')//2!=p[j]:
			break
		tmp.clear()
		if j==len(s)-1:
			ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
K = [[int(i) for i in input().split()] for j in range(m)]
P = [int(i) for i in range(n)]

ans = 0

for bits in range(2 ** n + 1):
    ok = True
    for i, k in enumerate(K):
        ok = ok and sum((bits >> (s - 1)) & 1 for s in k) % 2 == P[i]
    if ok:
        ans += 1

print(ans)