Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды: Вычесть 2 Вычесть 3 Извлечь корень Первые две команды уменьшают число на доске на 2 и 3 соответственно, третья команда — извлекает

1. Дано

• Исходное число ($N_0$): 25
• Целевое число ($N_{цель}$): 3
• Допустимые команды (преобразования):

1. Вычесть 2: $x \rightarrow x - 2$

2. Вычесть 3: $x \rightarrow x - 3$

3. Извлечь корень: $x \rightarrow \sqrt{x}$ (применяется, только если $x$ — полный квадрат)

2. Найти

Количество различных последовательностей команд (программ), преобразующих 25 в 3.

3. Решение

Будем использовать метод динамического программирования. Обозначим $K(n)$ как количество программ, преобразующих число $n$ в целевое число 3.

Наша цель — найти $K(25)$.

Базовый случай:...