Кодовый замок
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
В разведывательное управление доставили сейф с секретной информацией, кодовый замок на котором открывается комбинацией из nn цифр, каждая цифра может принимать b различных значений от 0 до b−1. Код неизвестен, однако разведчики передали несколько донесений о том, что сумма цифр кода в некоторых заданных позициях равна какому‑то известному числу. Используя информацию из всех полученных донесений, определите, сколько существует возможных кодов, удовлетворяющих этим условиям.
Формат входных данных
Первая строка входных данных содержит число b количество различных значений одной цифры кода, 2≤b≤10.
Вторая строка содержит число n количество цифр в коде, n≥1, bn≤60000.
Третья строка содержит число t количество имеющихся донесений о сумме каких‑то цифр кода, t≥1.
Следующие 2t строк содержат информацию об имеющихся донесениях. Каждое донесение состоит из двух строк. Первая из этих строк («маска цифр») содержит nn символов, записанных слитно и равных «0» или «1», где цифра «1» обозначает, что в донесении говорится об этой цифре кода. Например, маска цифр «01011» означает сумму цифр, стоящих коде на 2-й, 4-й и 5-й позициях. Во второй строке донесения записано число s, равное сумме цифр кода, стоящих на данных позициях.
Гарантируется, что каждая маска цифр содержит хотя бы одну единицу и что все маски цифр различаются. Общее число донесений может быть любым, удовлетворяющим этим условиям.
Формат выходных данных
Программа должна вывести одно целое число количество различных кодов, которые удовлетворяют всем донесениям.
Система оценки
Решения, правильно работающие, когда n≤4 и каждая маска цифр содержит ровно один символ «1», будут оцениваться в 28 баллов.
Решения, правильно работающие, когда n≤4, будут оцениваться в 64 балла.
Замечание
В примере из условия каждая цифра кода может принимать 8 различных значений от 0 до 7; код состоит из 3 цифр. Получено 2 донесения, из первого донесения известно, что сумма первой и второй цифр кода равна 7, из второго донесения известно, что сумма второй и третьей цифр кода равна 12. Существуют 3 кода, удовлетворяющие этим условиям: «075», «166», «257».
Ввод
8
3
2
110
7
011
12
Вывод
3
Ответы
Чтобы решить эту задачу, мы можем использовать динамическое программирование. Основная идея состоит в том, чтобы хранить количество возможных кодов для каждой позиции и каждого возможного значения суммы цифр.
Давайте разберем решение шаг за шагом:
Сначала мы инициализируем таблицу dp размером (n+1) x (b**n+1), где n — количество цифр в коде, а b — количество возможных значений каждой цифры. Эта таблица будет хранить количество возможных кодов для каждой позиции и каждого возможного значения суммы цифр.
Затем мы заполняем таблицу dp рекурсивно. Для каждой позиции i от 1 до n и для каждого возможного значения суммы цифр j от 0 до b**n, мы вычисляем количество возможных кодов, которые могут быть получены, добавив к сумме цифр на позиции i-1 значение k от 0 до b-1.
Для каждого донесения мы обновляем таблицу dp в соответствии с полученной информацией. Если сумма цифр на определенных позициях равна s, мы обнуляем все значения в таблице dp для позиций, которые не соответствуют этому условию.
Наконец, мы возвращаем значение в таблице dp для последней позиции и суммы цифр, равной 0. Это значение представляет количество возможных кодов, удовлетворяющих всем донесениям.
Вот реализация этого решения на Python:
def solve(b, n, t, reports):
dp = [[0] * (b ** n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
for j in range(b ** n + 1):
for k in range(b):
prev_sum = j — k
if prev_sum >= 0:
dp[i][j] += dp[i — 1][prev_sum]
for mask, s in reports:
mask_sum = 0
mask_value = 1
for i in range(n):
if mask[i] == ‘1’:
mask_sum += b ** (n — i — 1)
mask_value *= b
for i in range(b ** n + 1):
if (i // mask_value) % b!= s % b:
for j in range(n + 1):
dp[j][i] = 0
return dp[n][0]
b = int(input())
n = int(input())
t = int(input())
reports = []
for _ in range(t):
mask = input()
s = int(input())
reports.append((mask, s))
print(solve(b, n, t, reports))
Этот код читает входные данные, вызывает функцию solve и выводит результат. Функция solve реализует решение, описанное выше.
# Read input
b = int(input())
n = int(input())
t = int(input())
# Initialize dp table
dp = [[0] * (b * n + 1) for _ in range(n + 1)]
dp[0][0] = 1
# Process each mask
for i in range(t):
mask = input()
s = int(input())
# Update dp table based on the mask and sum
for j in range(n, -1, -1):
for k in range(b * n + 1):
if dp[j][k] > 0:
for l in range(b):
if mask[j] == ‘1’:
dp[j + 1][k + l] += dp[j][k]
else:
dp[j + 1][k + l] += dp[j][k]
# Calculate the number of valid codes
count = 0
for i in range(b * n + 1):
if dp[n][i] > 0 and i == s:
count += dp[n][i]
# Print the result
print(count)