Question

Задача на Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей.
Ограничения: 2 <= K <= 10, N + K <= 18.
Формат входных данных
Числа N и K в десятичной записи, разделенные пробелом или переводом строки.
Формат выходных данных
Искомое число в десятичной записи.

Answer 1

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

x, y = 1, 0

for i in range(n):

   x, y = (k-1) * (x + y), x

print(x)

Answer 2

Для решения данной задачи на количество N-значных чисел в системе счисления с основанием K, в которых не может быть двух подряд идущих нулей, можем использовать метод динамического программирования.

Шаг 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, удовлетворяющих условию без двух подряд идущих нулей. Решение основано на применении динамического программирования, а итоговый ответ выводится в десятичной записи.