A daily train consists of N cars. Let's consider one particular car. It has 54 places numbered consecutively from 1 to 54, some of which are already booked and some are still free. The places are numbered in the following fashion:
The car is separated into 9 compartments of 6 places each, as shown in the picture. So, the 1st compartment consists of places 1, 2, 3, 4, 53 and 54, the 2nd compartment consists of places 5, 6, 7, 8, 51 and 52, and so on.

A group of X friends wants to buy tickets for free places, all of which are in one compartment (it's much funnier to travel together). You are given the information about free and booked places in each of the N cars. Find the number of ways to sell the friends exactly X tickets in one compartment (note that the order in which the tickets are sold doesn't matter).

------ Input ------ 

The first line of the input contains two integers X and N (1 ≤ X ≤ 6, 1 ≤ N ≤ 10) separated by a single space. Each of the following N lines contains the information about one car which is a string of length 54 consisting of '0' and '1'. The i-th character (numbered from 1) is '0' if place i in the corresponding car is free, and is '1' if place i is already booked.

------ Output ------ 

Output just one integer -- the requested number of ways.

----- Sample Input 1 ------ 
1 3
100101110000001011000001111110010011110010010111000101
001010000000101111100000000000000111101010101111111010
011110011110000001010100101110001011111010001001111010
----- Sample Output 1 ------ 
85
----- explanation 1 ------ 
In the first test case, any of the free places can be sold.

----- Sample Input 2 ------ 
6 3
100101110000001011000001111110010011110010010111000101
001010000000101111100000000000000111101010101111111010
011110011110000001010100101110001011111010001001111010
----- Sample Output 2 ------ 
1
----- explanation 2 ------ 
In the second test case, the only free compartment in the train is compartment 3 in the first car (places 9, 10, 11, 12, 49 and 50 are all free).

----- Sample Input 3 ------ 
3 2
000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000
----- Sample Output 3 ------ 
360
----- explanation 3 ------ 
In the third test case, the train is still absolutely free; as there are 20 ways to sell 3 tickets in an empty compartment, the answer is 2 * 9 * 20 = 360.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Combinatorics

Implementation

Mathematics

Data structures


Solutions:
import math
(x, n) = map(int, input().split())
counter = 0
equals = 0
for _ in range(n):
	a = input()
	(i, j) = (0, 54)
	for __ in range(9):
		lst = a[i:i + 4] + a[j - 2:j]
		counter += math.comb(lst.count('0'), x)
		i += 4
		j -= 2
print(counter)


import math
(X, N) = map(int, input().split())
count = 0
for _ in range(N):
	seat = input()
	(i, j) = (0, 54)
	for __ in range(9):
		compartment = seat[i:i + 4] + seat[j - 2:j]
		count += math.comb(compartment.count('0'), X)
		i += 4
		j -= 2
print(count)


import math
l = [int(i) for i in input().split()]
(x, n) = l
count = 0
for i in range(n):
	s = input()
	l = [0] * 9
	sum = 0
	for i in range(1, 37):
		if s[i - 1] == '0':
			sum += 1
		if i % 4 == 0:
			l[i // 4 - 1] += sum
			sum = 0
	for i in range(37, 55):
		if s[i - 1] == '0':
			sum += 1
		if (54 - i) % 2 == 0:
			l[(54 - i) // 2] += sum
			sum = 0
	for i in l:
		if i >= x:
			count += math.factorial(i) / (math.factorial(i - x) * math.factorial(x))
print(int(count))


import math
(x, n) = map(int, input().split())
gorb = 0
for _ in range(n):
	a = list(input())
	(i, j) = (0, 54)
	for __ in range(9):
		t = a[i:i + 4] + a[j - 2:j]
		gorb += math.comb(t.count('0'), x)
		i += 4
		j -= 2
print(gorb)


import math
(x, n) = map(int, input().split())
count = 0
for i in range(n):
	s = input()
	(i, j) = (0, 54)
	for d in range(9):
		li = s[i:i + 4] + s[j - 2:j]
		count += math.comb(li.count('0'), x)
		i += 4
		j -= 2
print(count)


from math import comb
(f, c) = map(int, input().split())
l = []
for i in range(c):
	l.append(list(input().split()))
r = []
for i in l:
	for j in i:
		l2 = list(map(int, list(j)))
		box = []
		while len(l2) > 0:
			cabin = []
			for i in range(4):
				cabin.append(l2[0])
				l2.pop(0)
			cabin.append(l2[-1])
			l2.pop(-1)
			cabin.append(l2[-1])
			l2.pop(-1)
			box.append(cabin)
		r.append(box)
trainfree = []
for i in r:
	boxfree = []
	for j in i:
		cabinfree = 0
		for k in j:
			if k != 1:
				cabinfree += 1
		boxfree.append(cabinfree)
	trainfree.append(boxfree)
totaltype = 0
for i in trainfree:
	for j in i:
		if j >= f:
			totaltype += comb(j, f)
print(totaltype)


from math import factorial as fact

def combo(n, r):
	if n < r:
		return 0
	return fact(n) // (fact(r) * fact(n - r))
(x, n) = map(int, input().split(' '))
total = 0
for i in range(n):
	seat = input()
	front_seat = 0
	back_seat = 53
	for j in range(9):
		no_of_empty_seats = 0
		for a in range(4):
			if seat[front_seat] == '0':
				no_of_empty_seats += 1
			front_seat += 1
		for b in range(2):
			if seat[back_seat] == '0':
				no_of_empty_seats += 1
			back_seat -= 1
		total += combo(no_of_empty_seats, x)
print(total)


import math
(xp, n) = list(map(int, input().split()))
a = [input() for i in range(n)]
c1 = 0
for i in range(n):
	j = 0
	k = 54
	while j <= 33:
		s = a[i][j:j + 4] + a[i][k - 2:k]
		c1 += math.comb(s.count('0'), xp)
		j = j + 4
		k = k - 2
print(c1)


def comb(n, k):
	if k > n:
		return 0
	result = 1
	for i in range(k):
		result = result * (n - i) // (i + 1)
	return result
t = 1
for _ in range(t):
	(x, n) = map(int, input().split())
	cnt = 0
	for i in range(n):
		a = input()
		for j in range(9):
			l = a[j * 4:(j + 1) * 4] + a[54 - (j + 1) * 2:54 - j * 2]
			cnt += comb(l.count('0'), x)
print(cnt)


def fact(n):
	f = 1
	for i in range(1, n + 1):
		f = f * i
	return f

def result(p, q):
	return fact(p) / (fact(p - q) * fact(q))
(x, n) = map(int, input().split())
lf = []
ll = []
c = 0
for i in range(n):
	s = input()
	for i in range(9):
		lf.append(s[i * 4:(i + 1) * 4])
		ll.append(s[9 * 6 - (i + 2 + i):9 * 6 - (i + i)])
for i in range(len(lf)):
	a = lf[i].count('0')
	b = ll[i].count('0')
	if a + b >= x:
		res = result(a + b, x)
	else:
		res = 0
	c = c + res
print(int(c))


import math
(x, n) = [int(i) for i in input().split()]
arr = []
count = 0
for n in range(n):
	s = input()
	i = 0
	j = 54
	for k in range(9):
		d = str(s[i:i + 4]) + str(s[j - 2:j])
		if d.count('0') >= x:
			res = math.comb(d.count('0'), x)
			count += res
		i = i + 4
		j = j - 2
print(count)


def fact(m):
	r = 1
	for j in range(2, m + 1):
		r = r * j
	return r
(a, b) = map(int, input().split())
rus = 0
for _ in range(b):
	s = input()
	for i in range(9):
		q = i * 4
		d = 54 - i * 2
		p1 = s[q:q + 4].count('0')
		p2 = s[d - 2:d].count('0')
		p = p1 + p2
		if p >= a:
			rus = rus + fact(p) / (fact(p - a) * fact(a))
print(int(rus))


import math
(x, n) = map(int, input().split())
c = 0
for k in range(n):
	s = input()
	i = 1
	j = 54
	for _ in range(9):
		kupe = s[i - 1:i + 3] + s[j - 2:j]
		c += math.comb(kupe.count('0'), x)
		i += 4
		j -= 2
print(c)


def fact(p):
	if p == 0 or p == 1:
		return 1
	else:
		return p * fact(p - 1)

def comb(n, r):
	if n < r:
		return 0
	else:
		return fact(n) // (fact(r) * fact(n - r))
(a, b) = map(int, input().strip().split())
ans = 0
for e in range(b):
	l = input()
	i = 0
	j = 1
	for k in range(9):
		ass = 0
		for _ in range(4):
			if l[i] == '0':
				ass += 1
			i += 1
		for _ in range(2):
			if l[-j] == '0':
				ass += 1
			j += 1
		ans += comb(ass, a)
print(ans)


import math
(x, y) = list(map(int, input().split()))
cnt = 0
comb = 0
arr = [0] * 9
for i in range(y):
	s = input()
	st = 0
	en = 53
	for j in range(9):
		for k in range(st, st + 4):
			if s[k] == '0':
				cnt += 1
		for k in range(en, en - 2, -1):
			if s[k] == '0':
				cnt += 1
		arr[j] = cnt
		cnt = 0
		st += 4
		en -= 2
	for i in range(0, 9):
		if arr[i] >= x:
			comb += math.factorial(arr[i]) // (math.factorial(x) * math.factorial(arr[i] - x))
print(comb)


import math
(x, n) = map(int, input().split())
c = 0
for i in range(n):
	s = str(input())
	lst = []
	p = 0
	q = 54
	for j in range(9):
		lst = s[p:p + 4] + s[q - 2:q]
		c += math.comb(lst.count('0'), x)
		p += 4
		q -= 2
print(c)


import math
(x, n) = map(int, input().split())
sum = 0
for _ in range(n):
	a = input()
	i = 0
	j = 54
	for __ in range(9):
		s = a[i:i + 4] + a[j - 2:j]
		i += 4
		j -= 2
		sum += math.comb(s.count('0'), x)
print(sum)


import math
(kannaa, buji) = map(int, input().split())
count = 0
for _ in range(buji):
	go = input()
	(j1, j2) = (0, 54)
	for __ in range(9):
		v = go[j1:j1 + 4] + go[j2 - 2:j2]
		count += math.comb(v.count('0'), kannaa)
		j1 += 4
		j2 -= 2
print(count)


import math
(X, N) = map(int, input().split())
c = 0
for i in range(N):
	s = input()
	(i, j) = (0, 54)
	for k in range(9):
		com = s[i:i + 4] + s[j - 2:j]
		c += math.comb(com.count('0'), X)
		i += 4
		j -= 2
print(c)


import math
(x, n) = map(int, input().split())
count = 0
for i in range(n):
	string = input()
	for i in range(9):
		string1 = string[i * 4:i * 4 + 4]
		if i == 0:
			string2 = string[-1] + string[-2]
		else:
			string2 = string[i * -2 - 2:i * -2]
		dabba = string1 + string2
		n0 = dabba.count('0')
		if n0 >= x:
			count += math.factorial(n0) / (math.factorial(n0 - x) * math.factorial(x))
print(int(count))


import math
(x, n) = list(map(int, input().strip().split()))
answer = 0
for i in range(n):
	seat = list(map(int, list(input())))
	available_seat = [0, 0, 0, 0, 0, 0, 0, 0, 0]
	start = 0
	end = 53
	for z in range(9):
		count = 0
		for j in range(start, start + 4):
			if seat[j] == 0:
				count += 1
		for k in range(end, end - 2, -1):
			if seat[k] == 0:
				count += 1
		available_seat[z] = count
		start += 4
		end -= 2
	for i in range(0, 9):
		if available_seat[i] >= x:
			answer += math.factorial(available_seat[i]) // (math.factorial(x) * math.factorial(available_seat[i] - x))
print(answer)


facto = [1]
for i in range(6):
	facto.append(facto[-1] * (i + 1))

def split_com(s):
	free = [0] * 9
	for i in range(36):
		free[i // 4] += 1 - int(s[i])
	for i in range(36, 54):
		free[8 - (i - 36) // 2] += 1 - int(s[i])
	return free
(x, n) = map(int, input().split())
booked = []
for i in range(n):
	booked.append(split_com(input()))
ans = 0
for i in booked:
	for j in i:
		if j >= x:
			ans += facto[j] // (facto[x] * facto[j - x])
print(ans)


import math
(n, x) = map(int, input().split())
c = 0
e = 0
for j in range(x):
	s = input()
	(j, k) = (0, 54)
	for m in range(9):
		b = s[j:j + 4] + s[k - 2:k]
		c += math.comb(b.count('0'), n)
		j += 4
		k -= 2
print(c)


def f(n, memo={}):
	if n <= 2:
		return n
	if n in memo:
		return memo[n]
	memo[n] = n * f(n - 1, memo)
	return memo[n]

def combinations(n, r):
	return f(n) / (f(r) * f(n - r))
(x, n) = map(int, input().split())
ans = 0
for i in range(n):
	car = input()
	w1 = (0, 4)
	w2 = (52, 54)
	vacant = 0
	if x == 1:
		ans += car.count('0')
	else:
		for i in range(9):
			vacant = car[w1[0]:w1[1]].count('0') + car[w2[0]:w2[1]].count('0')
			if vacant == x:
				ans += 1
			elif vacant >= x:
				ans += combinations(vacant, x)
			w1 = (w1[0] + 4, w1[1] + 4)
			w2 = (w2[0] - 2, w2[1] - 2)
print(int(ans))


import math
(x, n) = map(int, input().split())
tot = 0
for i in range(n):
	s = input()
	j = 0
	k = 54
	while j < 36:
		s1 = s[j:j + 4] + s[k - 2:k]
		j += 4
		k -= 2
		if x <= s1.count('0'):
			tot += math.factorial(s1.count('0')) // (math.factorial(x) * math.factorial(s1.count('0') - x))
print(tot)


import math
gt = str(input())
gt = gt.split(' ')
omtes = int(gt[0])
umi = int(gt[-1])
op = []
for yyn in range(0, umi):
	op.append(str(input()))
seats = 0
for hhv in op:
	a = 0
	b = 4
	d = 52
	e = 54
	der = 0
	while der < 9:
		jut = hhv[a:b] + hhv[d:e]
		loer = 0
		for pp in jut:
			if pp == '0':
				loer += 1
		if loer >= omtes:
			if omtes != 1:
				s = math.comb(loer, omtes)
				seats += s
			else:
				seats += loer
		der += 1
		a += 4
		b += 4
		d -= 2
		e -= 2
print(seats)


import math
(x, n) = list(map(int, input().split(' ')))
ans = 0
for i in range(n):
	if x > 6:
		print(0)
		break
	ins = []
	ins.extend(input())
	for i in range(9):
		num = 4 * i
		temp = [ins[num], ins[num + 1], ins[num + 2], ins[num + 3], ins[52 - i * 2], ins[53 - i * 2]]
		zeros = temp.count('0')
		if zeros >= x:
			ans += math.factorial(zeros) / (math.factorial(x) * math.factorial(zeros - x))
print(int(ans))


import math
(y, n) = map(int, input().split())
w = 0
for _ in range(n):
	s = input()
	k = 1
	x = 0
	for i in range(0, 36, 4):
		x = s[i:i + 4].count('0')
		if s[-k] == '0':
			x += 1
		if s[-(k + 1)] == '0':
			x += 1
		k += 2
		if y <= x:
			w += math.comb(x, y)
print(w)


import math

def ncr(n, r):
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
(x, n) = map(int, input().split())
result = 0
for i in range(n):
	s = input()
	j = 0
	for i in range(0, 36, 4):
		c = (s[i:i + 4] + s[52 - j:54 - j]).count('0')
		j += 2
		if c >= x:
			result += ncr(c, x)
print(result)


import math
(x, n) = map(int, input().split())
sum = 0
for i in range(n):
	p = input()
	(l, m) = (0, 54)
	for j in range(9):
		a = p[l:l + 4] + p[m - 2:m]
		sum += math.comb(a.count('0'), x)
		l += 4
		m -= 2
print(sum)


def comb(n, k):
	if k > n:
		return 0
	result = 1
	for i in range(k):
		result = result * (n - i) // (i + 1)
	return result
(x, n) = map(int, input().split())
counter = 0
for _ in range(n):
	a = input()
	for i in range(9):
		lst = a[i * 4:(i + 1) * 4] + a[54 - (i + 1) * 2:54 - i * 2]
		counter += comb(lst.count('0'), x)
print(counter)


import math as e
(x, n) = map(int, input().split())
li = []
c = 0
d = 0
for i in range(n):
	s = input()
	li.append(list(s))
for j in range(n):
	a = li[j]
	i = 0
	t = 54
	for _ in range(9):
		m = a[i:i + 4].count('0') + a[t - 2:t].count('0')
		if m >= x:
			d += e.factorial(m) // (e.factorial(x) * e.factorial(m - x))
		i += 4
		t -= 2
print(d)


import math
(x, n) = map(int, input().split())
ans = 0
for _ in range(n):
	res = input()
	i = 0
	j = 53
	while i < 36 and j >= 36:
		car = 0
		k = 0
		while k < 4:
			if res[i] == '0':
				car += 1
			i += 1
			k += 1
		l = 0
		while l < 2:
			if res[j] == '0':
				car += 1
			j -= 1
			l += 1
		if car >= x:
			ans += math.comb(car, x)
print(ans)


from math import comb
(X, N) = map(int, input().split())
op = 0
for _ in range(N):
	S = input()
	while S:
		s1 = S[0:4] + S[-2:]
		vacant = s1.count('0')
		if vacant >= X:
			op += comb(vacant, X)
		S = S[4:-2]
print(op)


def nCr(n, r):
	if r > n:
		return 0
	if r == 0 or r == n:
		return 1
	return nCr(n - 1, r - 1) + nCr(n - 1, r)
(x, y) = map(int, input().split())
c = 0
for t in range(y):
	s = input()
	z = []
	a = 0
	b = 54
	for i in range(9):
		z.append(int(s[a:a + 4].count('0') + s[b - 2:b].count('0')))
		a += 4
		b -= 2
	for j in z:
		if j == x:
			c += 1
		elif j > x:
			c += nCr(j, x)
print(int(c))


from math import factorial as fac
ans = 0
(X, N) = map(int, input().split())
for i in range(N):
	K = input()
	s = 54
	for m in range(0, 9 * 4, 4):
		free = 0
		free_2 = 0
		last_ans = ans
		for n in range(4):
			if str(K)[m + n] == '0':
				free += 1
				free_2 += 1
			if free == X:
				ans += 1
				free = 0
		for l in range(2):
			s -= 1
			if str(K)[s] == '0':
				free += 1
				free_2 += 1
			if free == X:
				ans += 1
				free = 0
		if free_2 > X:
			seconds = fac(free_2) / (fac(X) * fac(free_2 - X))
			if seconds > ans - last_ans:
				ans = last_ans + int(seconds)
print(ans)


import math
(x, n) = map(int, input().split())
c = 0
for k in range(n):
	a = input()
	(i, j) = (0, 54)
	for k in range(9):
		l = a[i:i + 4] + a[j - 2:j]
		c += math.comb(l.count('0'), x)
		i += 4
		j -= 2
print(c)


import math
(x, n) = map(int, input().split())
total = 0
for i in range(n):
	places = input()
	place_count = 0
	last_place_count = len(places)
	for i in range(9):
		total += math.comb((places[place_count:place_count + 4] + places[last_place_count - 2:last_place_count]).count('0'), x)
		place_count += 4
		last_place_count -= 2
print(total)


def fact(N):
	factorial = 1
	if N == 0:
		return 1
	for i in range(2, N + 1):
		factorial *= i
	return factorial

def combination(N, r):
	return fact(N) / (fact(r) * fact(N - r))
(X, N) = input().split()
(X, N) = (int(X), int(N))
ways = 0
for carNumber in range(N):
	info = input()
	for comp in range(9):
		empty = 0
		for seat in range(4 * comp, 4 * comp + 4):
			if info[seat] == '0':
				empty += 1
		for seat in range(52 - 2 * comp, 54 - 2 * comp):
			if info[seat] == '0':
				empty += 1
		if empty >= X:
			ways += combination(empty, X)
print(int(ways))