Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1885. Разбиение на палиндромы
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 16/11/2012 | Муниципальный этап 9-11 классы (4) |
| 19/07/2016 | Лето 2016 - 11 (B) |
| 06/07/2020 | Летние сборы - 4 (B) |
| 10/07/2023 | Лето 2023-7 сложные (B) |
| 27/02/2024 | Динамическое программирование 1 (проводит BOGAT) (I) |
| 08/07/2024 | Лето 2024-7 сложные (B) |
| 19/03/2025 | ЦОП1: динамическое программирование (проводит BOGAT) (J) |
| 17/07/2025 | Лето 2025-7 (E) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Палиндромом называется строка, читаемая одинаково слева направо и справа налево.
Например, abba – палиндром, а bat – нет.
Напишите программу, которая подсчитает количество способов разбить заданную строку на непустые подстроки, являющиеся палиндромами.
Например, для слова abbat есть три способа разбиения на палиндромы: a-b-b-a-t,
a-bb-a-t и abba-t.
Первая строка ввода содержит строку из строчных латинских букв длиной от 1 до 100 символов.
Вывести одно целое число — остаток от деления количества способов разбиения на `1 000 000 009`.
Пример ввода
abbat
Пример вывода
3
