Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1982. Города
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 05/10/2013 | Личное первенство Южного Урала (B) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В игре "Вокруг света" необходимо угадывать название города. При этом известна длина названия и некоторые буквы.
Петя не знает географии и поэтому перебирает все возможные варианты для названия городов. Петя знает, что
не существует названий городов, в которых имеется более трех гласных или согласных букв подряд или
более двух одинаковых букв подряд, и не рассматривает такие варианты. Гласными буквами будем считать
буквы A, E, I, O, U и Y.
Напишите программу, определяющую количество вариантов для названия города с учетом указанных ограничений.
Первая строка ввода содержит последовательность из прописных латинских букв и символов '?'.
Символ '?' означает неизвестную букву в названии города. Длина строки от 1 до 1000 символов.
В первой строке вывести одно целое число — остаток от деления количества вариантов на `1\ 000\ 000\ 009`.
Пример ввода
?O??OW
Пример вывода
16620
