Question

Помогите пожалуйста срочно очень!!!!!
Префиксное кодирование является очень распространенным способом сжатия информации для ее хранения и передачи. Каждый символ кодируется некоторым кодовым словом — строкой из нулей и единиц. Кодовые слова могут иметь различную длину, но при этом должно выполняться следующее свойство: ни одно кодовое слово не начинается с другого кодового слова. Например, множество кодовых слов \{00,011,1000,11\}{00,011,1000,11} подходит для префиксного кодирования, а \{00,101,11,1010\}{00,101,11,1010} — нет, так как 101 является началом 1010.

От вас требуется написать программу, которая найдет, какое максимальное количество кодовых слов заданной длины mm можно добавить к некоторому уже построенному множеству слов для префиксного кодирования. Например m=4m=4, и уже построено множество \{10,001,000,0111,11111,11000,111101\}{10,001,000,0111,11111,11000,111101}. Без нарушения условия префиксного кодирования можно добавить следующие слова длины 4: \{0100,0101,0110,1101,1110\}{0100,0101,0110,1101,1110}. Таким образом, ответ равен 5.

Формат входных данных
В первой строке на вход подается два натуральных числа nn и mm — количество уже известных кодовых слов и длина новых кодовых слов. m\leq 60m≤60. Во второй строке через пробел записано nn кодовых слов. Все слова состоят из нулей и единиц и удовлетворяют условию префиксного кодирования. Суммарная длина всех слов не превосходит 10^610
6
.

Формат выходных данных
Требуется вывести одно целое число — ответ к задаче. Ответ может быть равным нулю.

Методика проверки
Программа проверяется на 20 тестах. Прохождение каждого теста оценивается в 1 балл. При этом в трех тестах m\leq 10m≤10 и n\leq 100n≤100, еще в трех тестах длина всех заданных слов не превосходит mm, еще в четырех тестах длина всех заданных слов не меньше чем mm. Тест из условия задачи при проверке не используется.

Sample Input:
7 4
10 001 000 0111 11111 11000 111101

Sample Output:
5

Answer 1

Ответ:Решай сам

Объяснение:

def rec(st,i=0):

global c,n,m

if i ==m:

c+=1

return

st0 = st +"0"

if st0 not in b:

rec(st0,i+1)

st1 = st + "1"

if sr1 not in b:

rec(st1,i+1)

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

b = set(e[:m]for e in input().split())

c=0

rec("",0)

print(c)