Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2041. Пиццерия
Жадные алгоритмыОлимпиадные задачи на русском языке
| 19/04/2014 | Южно-Уральский открытый командный чемпионат по программированию (D) |
| 23/04/2014 | Занятие 22 (D) |
| 18/07/2016 | Лето 2016 - 10 (командная) (C) |
| 03/07/2020 | Летние сборы - 3 (командное) (C) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Создатели Великобинарии заложили в виртуальных жителей любовь к пицце, но их пицца
выглядит как последовательность букв, составляющих название пиццы. Для изготовления пиццы "Маргарита" нужно взять
три буквы А, две буквы Р и по одной букве М, Г, И и Т.
Бинарец Кибибайт работает в пиццерии и должен собирать пиццы из поступающих по конвейеру букв-ингредиентов.
В каждый момент времени может собираться только одна пицца, название которой выбирает Кибибайт перед началом
работы или после сборки очередной пиццы. С конвейера можно брать только тот ингредиент, который
проходит в текущий момент мимо Кибибайта. Кибибайт знает несколько названий-рецептов и последовательность
поступающих букв и хочет собрать как можно больше пицц, чтобы стать работником месяца и получить повышение.
Формат ввода
Первая строка ввода содержит одно целое число: количество названий `N` (`1\ ≤\ N\ ≤\ 1000`).
Далее следует `N` строк, содержащих названия. Названия имеют длину от 1 до 100 букв и состоят только
из русских прописных букв от А до Я (буквы с кодами от 192 до 223, без буквы Ё). Далее следует
строка длиной от 1 до `100\ 000` букв, состоящая из русских прописных букв — поступающие по
конвейеру буквы-ингредиенты.
Формат вывода
В первой строке вывести одно целое число `K` – максимальное количество пицц, которое может собрать Кибибайт.
Во второй строке вывести `K` целых чисел — номера рецептов. Если существует несколько
вариантов с максимальным количеством, то можно вывести любой из них.
Пример ввода
3 МАРГАРИТА СРЕДИЗЕМНОМОРСКАЯ ЛУКОВАЯ МАРГАРИТАЯАВОКУЛРЕДИСЗЕМЛЯТАРАКАНГОРЧИЦА
Пример вывода
3 1 3 1
Когда по конвейеру пройдет последний символ строки, рабочий день Кибибайта заканчивается.
Куда исчезают неиспользованные буквы-ингредиенты в данной задаче неважно, предположим, что из них собирают пиццы другие работники пиццерии, которые стоят на конвейере после Кибибайта. Но нас интересует только количество пицц, собранных Кибибайтом.
