В разведывательное управление доставили сейф с секретной информацией, кодовый замок на…
- User
В разведывательное управление доставили сейф с секретной информацией, кодовый замок на котором открывается комбинацией из n цифр, каждая цифра может принимать b различных значений от 0 до b−1. Код неизвестен, однако разведчики передали несколько донесений о том, что сумма цифр кода в некоторых заданных позициях равна какому-то известному числу. Используя информацию из всех полученных донесений, определите, сколько существует возможных кодов, удовлетворяющих этим условиям. Входные данные: Первая строка входных данных содержит число b — количество различных значений одной цифры код. Вторая строка содержит число n — количество цифр в коде, n≥1. Третья строка содержит число t – количество имеющихся донесений о сумме каких-то цифр кода, t≥1. Следующие 2t строк содержат информацию об имеющихся донесениях. Каждое донесение состоит из двух строк. Первая из этих строк («маска цифр») содержит n символов, записанных слитно и равных «0» или «1», где цифра «1» обозначает, что в донесении говорится об этой цифре кода. Например, маска цифр «01011» означает сумму цифр, стоящих в коде на 2-й, 4-й и 5-й позициях. Во второй строке донесения записано число s, равное сумме цифр кода, стоящих на данных позициях.Гарантируется, что каждая маска цифр содержит хотя бы одну единицу и что все маски цифр различаются. Общее число донесений может быть любым, удовлетворяющим этим условиям. Выходные данные: Программа должна вывести одно целое число — количество различных кодов, которые удовлетворяют всем донесениям. Примечание: В примере из условия каждая цифра кода может принимать 8 различных значений от 0 до 7, код состоит из 3 цифр. Получены 2 донесения, из первого донесения известно, что сумма первой и второй цифры кода равна 7, из второго донесения известно, что сумма второй и третьей цифры кода равна 12. Существуют 3 кода, удовлетворяющие этим условиям: «075», «166», «257». Примеры: Входные данные: 1 8 3 2 110 7 011 12 Выходные данные: 3
- Assistant
Для заданного примера входных данных:
8 3 2 110 7 011 12мы имеем следующие параметры:
- b = 8: каждая цифра кода может принимать значения от 0 до 7.
- n = 3: длина кода составляет 3 цифры.
- t = 2: имеется 2 донесения.
Далее, каждое донесение состоит из маски и суммы:
- Маска
110и сумма 7: это означает, что сумма первых двух цифр кода (x_1 + x_2) должна равняться 7. - Маска
011и сумма 12: это означает, что сумма последних двух цифр кода (x_2 + x_3) должна равняться 12.
Теперь найдем все возможные комбинации цифр
(x_1, x_2, x_3), удовлетворяющие этим условиям:- Из первого условия:
x_1 + x_2 = 7⇒x_2 = 7 - x_1. - Подставляем
x_2во второе условие:7 - x_1 + x_3 = 12⇒x_3 = 12 - (7 - x_1) = 5 + x_1.
Поскольку каждая цифра должна быть в диапазоне от 0 до 7, рассмотрим возможные значения для
x_1:-
x_1 = 0:
x_2 = 7 - 0 = 7x_3 = 5 + 0 = 5- Код: 075
-
x_1 = 1:
x_2 = 7 - 1 = 6x_3 = 5 + 1 = 6- Код: 166
-
x_1 = 2:
x_2 = 7 - 2 = 5x_3 = 5 + 2 = 7- Код: 257
Проверяем остальные значения
x_1:- x_1 = 3:
x_2 = 4x_3 = 8(не допустимо, так как максимальное значение 7)
Таким образом, допустимыми кодами являются:
- 075
- 166
- 257
Следовательно, количество возможных кодов, удовлетворяющих всем условиям, равно 3.
Ответ:
3