Дарья Дмитриевна готовит зачёт по теории чисел. Она пообещала каждому студенту дать столько задач, сколько слагаемых он создаст в числовом п...
Условие:
Дарья Дмитриевна готовит зачёт по теории чисел. Она пообещала каждому студенту дать столько задач, сколько слагаемых он создаст в числовом примере 𝑎1+𝑎2+ ...+ 𝑎𝑛=2021, где все числа 𝑎𝑖 – натуральные, больше 10 и являются палиндромами (не меняются, если их цифры записать в обратном порядке). Если студент не нашёл ни одного такого примера, он п
Решение:
Добрый день! Задача, которую Дарья Дмитриевна дала своим студентам, связана с палиндромами и разложением числа 2021 на слагаемые, которые являются палиндромами и больше 10.
Для начала, давайте посмотрим, какие палиндромы больше 10 можно использовать в разложении числа 2021. Палиндромы - это числа, которые одинаково читаются слева направо и справа налево.
Наибольший палиндром, меньший 2021 и больший 10, это 1991. Он может быть использован в разложении числа 2021. Однако, чтобы найти количество задач, которые Дарья Дмитриевна даст студенту, нам нужно найти все возможные разложения числа 2021 на палиндромы.
Для этого можно воспользоваться методом динамического программирования. Создадим массив dp, где dp[i] будет хранить количество разложений числа i на палиндромы. Инициализируем dp[0] = 1, так как пустое разложение является...
