Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1137. Гастроли
Жадные алгоритмыОлимпиадные задачи на русском языке
| 08/11/2008 | Региональные отборочные командные соревнования для школьников (9) |
| 10/07/2013 | Лето 2013-7 (F) |
| 14/04/2015 | Занятие 21 (C) |
| 23/07/2015 | Практика 1 и 2 курса (8 командное) (H) |
Ограничения: время – 250ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Парк аттракционов "Страна чудес Гудвина" отправляется из столицы на гастроли по провинциальным городам.
Все аттракционы погрузили в вагоны, каждый аттракцион в отдельный вагон. Поезд должен проехать по некоторому
заданному маршруту, отцепляя в каждом городе некоторое количество вагонов от хвоста поезда.
Среди этих вагонов обязательно должны быть вагоны с аттракционами, которые требуются жителям данного города.
Кроме заказанных аттракционов можно отцепить другие вагоны с целью увеличения скорости движения поезда на оставшейся
части маршрута. При отсутствии пожеланий по видам аттракционов в некотором городе можно оставить в нем любые аттракционы,
а можно не оставлять ни одного. Паровоз без вагонов проезжает перегон между городами за 1000 минут.
Если к паровозу прицепить `K` вагонов, то время движения на перегоне возрастет до `(1000+K)` минут.
Требуется как можно быстрее довести поезд до последнего города в маршруте, обеспечив все города по пути аттракционами в
соответствии с их пожеланиями.
В первой строке ввода содержится непустая последовательность из строчных латинских букв, длиной не
более 10000 символов – размещение аттракционов по вагонам, перечисленных от хвоста поезда к началу.
Каждая латинская буква соответствует некоторому виду аттракционов, например, буквой 'a' обозначаются все карусели.
Во второй строке содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество городов по маршруту движения.
Далее следует `N` строк, в каждой строке содержатся пожелания города о видах аттракционов и их
количестве в виде последовательности строчных латинских букв. Если городу требуются два аттракциона типа карусели,
то в этой последовательности будут содержаться две буквы 'a'. Длина последовательности
букв не превосходит 100 символов. Порядок символов в пожеланиях города может не соответствовать порядку этих вагонов в поезде.
Вывести одно целое число – минимальное время движения поезда в минутах до последнего города в маршруте.
Если обеспечить провинциальные города аттракционами в соответствии с их пожеланиями невозможно, то вместо времени
движения вывести число `-1`.
Пример ввода
smalltrain 2 all iran
Пример вывода
2014
