Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1140. Шифровка
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 06/01/2005 | Областная олимпиада школьников по информатике (командные соревнования) (1) |
| 26/09/2013 | Занятие 4 для продолжающих (A) |
| 07/03/2024 | ДП (повторение) (проводит BOGAT) (I) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Алиса и Боб решили шифровать свою переписку и начали обсуждать шифр.
Алиса: Предлагаю следующий простой шифр. Буква 'A' будет записываться как 1, 'B' – 2, и так далее до 'Z' – 26.
Боб: Это глупый шифр. Если я пошлю тебе слово 'BEAN' (боб), оно будет закодировано как 25114. Но это сообщение можно расшифровать несколькими способами.
Алиса: Ты прав, но другие слова бессмысленны. Кроме 'BEAN' получаются слова 'BEAAD', 'YAAD', 'YAN', 'YKD' и 'BEKD'. Я думаю, что можно догадаться о корректной расшифровке.
Боб: Ладно, это был слишком простой пример. А если я пошлю сообщение из 500 цифр или больше, как ты найдешь среди миллиардов возможных расшифровок единственно правильную?
Алиса: Так много? Не может быть…
Напишите программу, которая подсчитывает число возможных расшифровок некоторого сообщения, закодированного шифром Алисы.
Во входном файле содержится несколько строк с шифровками. Все шифровки корректны и не начинаются с цифры 0. Строка, содержащая только 0, служит признаком конца ввода и не обрабатывается.
В выходной файл для каждой шифровки из входного файла вывести в соответствующей строке число возможных расшифровок. Шифровки могут быть очень длинными, но гарантируется, что число расшифровок меньше `2^32`.
Пример ввода
25114 1111111111 4444444444 0
Пример вывода
6 89 1
