Задача на Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей.
Ограничения: 2 <= K <= 10, N + K <= 18.
Формат входных данных
Числа N и K в десятичной записи, разделенные пробелом или переводом строки.
Формат выходных данных
Искомое число в десятичной записи.
n, k = map(int, input().split())
x, y = 1, 0
for i in range(n):
x, y = (k-1) * (x + y), x
print(x)
Шаг 1: Получение входных данных
- Принимаем от школьника значения N и K в десятичной записи.
Шаг 2: Создание таблицы для хранения промежуточных результатов
- Создаем двумерную таблицу dp размером (N+1)x(K+1), заполненную нулями, где dp[i][j] будет представлять количество i-значных чисел в системе счисления с основанием j, удовлетворяющих условию.
Шаг 3: Инициализация начальных значений
- Заполняем первую строку таблицы dp[1][j] = 1 для всех j от 1 до K, так как однозначные числа не могут содержать двух подряд идущих нулей.
Шаг 4: Заполнение таблицы dp по формуле
- Выполняем следующий цикл от i = 2 до N включительно:
- Для каждого j от 1 до K выполним следующий цикл:
- Суммируем значения dp[i-1][k] для всех k от 1 до K, кроме j, и прибавляем это значение к dp[i][j].
- Таким образом, dp[i][j] будет равно сумме значений dp[i-1][k] для всех k от 1 до K, кроме j.
Шаг 5: Вычисление итогового ответа
- Суммируем последнюю строку таблицы dp, чтобы получить искомое количество N-значных чисел со основанием K и условием без двух подряд идущих нулей.
Шаг 6: Вывод ответа
- Выводим итоговый ответ (используя переменную-счетчик), который будет представлять искомое количество N-значных чисел.
--------------------------------------------------------------------------
Пример решения задачи на ЯП Python:
# Шаг 1: Получение входных данных
N, K = map(int, input().split())
# Шаг 2: Создание таблицы для хранения промежуточных результатов
dp = [[0] * (K+1) for _ in range(N+1)]
# Шаг 3: Инициализация начальных значений
for j in range(1, K+1):
dp[1][j] = 1
# Шаг 4: Заполнение таблицы dp по формуле
for i in range(2, N+1):
for j in range(1, K+1):
for k in range(1, K+1):
if k != j:
dp[i][j] += dp[i-1][k]
# Шаг 5: Вычисление итогового ответа
result = sum(dp[N])
# Шаг 6: Вывод ответа
print(result)
--------------------------------------------------------------------------
Таким образом, мы решаем поставленную задачу, вычисляя количество N-значных чисел в системе счисления с основанием K, удовлетворяющих условию без двух подряд идущих нулей. Решение основано на применении динамического программирования, а итоговый ответ выводится в десятичной записи.