#2820

Словарь

Темы: [Обработка текста] [Алгоритмы поиска]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2010, Лига А, Задача G ]

Однажды, разбирая старые книги на чердаке, школьник Вася нашёл англо-латинский словарь. Английский он к тому времени знал в совершенстве, и его мечтой было изучить латынь. Поэтому попавшийся словарь был как раз кстати.

К сожалению, для полноценного изучения языка недостаточно только одного словаря: кроме англо-латинского необходим латинско-английский. За неимением лучшего он решил сделать второй словарь из первого.

Как известно, словарь состоит из переводимых слов, к каждому из которых приводится несколько слов-переводов. Для каждого латинского слова, встречающегося где-либо в словаре, Вася предлагает найти все его переводы (то есть все английские слова, для которых наше латинское встречалось в его списке переводов), и считать их и только их переводами этого латинского слова.

Помогите Васе выполнить работу по созданию латинско-английского словаря из англо-латинского.

Входные данные

В первой строке содержится единственное целое число N — количество английских слов в словаре. Далее следует N описаний. Каждое описание содержится в отдельной строке, в которой записано сначала английское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого английского слова на латинский. Переводы отсортированы в лексикографическом порядке. Порядок следования английских слов в словаре также лексикографический.

Все слова состоят только из маленьких латинских букв, длина каждого слова не превосходит 15 символов. Общее количество слов на входе не превышает 100 000.

Выходные данные

Выведите соответствующий данному латинско-английский словарь, в точности соблюдая формат входных данных. В частности, первым должен идти перевод лексикографически минимального латинского слова, далее — второго в этом порядке и т.д. Внутри перевода английские слова должны быть также отсортированы лексикографически.

Примечание

«Лексикографический порядок» означает, что слова идут по алфавиту. Иначе говоря, если у двух слов A и B несколько первых символов совпадают, то раньше идет то, у которого первая буква после общей части идет в алфавите раньше (например, слова solution и solve идут именно в таком порядке, так как первые 3 буквы в этих словах совпадают, а 4-я буква u в слове solution идет по алфавиту раньше буквы v слова solve). Если слово A является началом слова B, то раньше идет слово A (например, сначала идет слово school, а затем слово schoolboy).

Примеры

Входные данные

3
apple - malum, pomum, popula
fruit - baca, bacca, popum
punishment - malum, multa

Выходные данные

7
baca - fruit
bacca - fruit
malum - apple, punishment
multa - punishment
pomum - apple
popula - apple
popum - fruit

#2821

Пешки

Темы: [Потоки]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2010, Лига А, Задача H ]

В первом классе Глеб увлекался шахматами. К тому моменту он знал только лишь как ходит пешка: она может бить по диагонали влево-вверх и вправо-вверх, и ходить на клетку вверх только если та клетка не занята другой фигурой. О том, что пешка может превращаться в ферзя Глеб не подозревает. Поэтому он придумал свой вариант шахмат.

Игра идёт на доске с N строками и M столбцами (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) по следующим правилам. В нижней строке, имеющей номер 1, стоят P белых пешек, белых фигур на доске больше нет. На остальной части доски стоят разные чёрные фигуры (их названия Глеб не знает). Ходят только белые, их цель — побить все чёрные фигуры.

Как и в настоящих шахматах, если пешка Глеба бьёт чёрную фигуру, то она становится на её место, а побитая фигура убирается с доски. Считается, что Глеб выиграл, если он сумел побить белыми пешками все чёрные фигуры, в противном случае он проиграл. Помогите ему по заданной конфигурации всех фигур определить, сможет ли он выиграть, и, в случае успеха, выведите правильную последовательность ходов белых пешек.

Входные данные

Сначала вводятся четыре целых числа N, M, P, K (1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ P ≤ M, 1 ≤ K ≤ 1000, K ≤ (M - 1)N). Далее записано P различных чисел — номера столбцов p_j (1 ≤ p_j ≤ M), в которых стоят белые пешки. Далее идут K различных пар целых чисел — координаты (строки и столбцы) чёрных фигур r_i, c_i (2 ≤ r_i ≤ N, 1 ≤ c_i ≤ M).

Выходные данные

Если пешки не смогут съесть все фигуры, выведите единственное слово NO.

В противном случае в первую строку выведите YES, вторая строка должна содержать суммарное число перемещений C, последующие C строк — описание ходов пешек, по одному ходу на каждую строку. Каждый ход задаётся двумя координатами r, c пешки (номерами строки и столбца), которая будет ходить, и символом m, принимающем три значения: L, R, F — побить вперед и влево, побить вперед и вправо, сделать шаг вперед соответственно. Данные о ходе следует выводить разделёнными одним пробелом, сначала координаты, потом тип хода.

Если последовательностей ходов несколько, выведите любой из них. Обратите внимание, что минимизировать количество перемещений не требуется.

Примеры

Входные данные

2 2 2 1
1 2
2 2

Выходные данные

YES
1
1 1 R

Входные данные

Выходные данные

NO

#2822

Трамвай

Темы: [Динамическое программирование]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2010, Лига А, Задача I ]

Вася идет из школы домой вдоль проспекта, по которому ходят трамваи. Мама считает, что ему после школы полезно дышать свежим воздухом, поэтому настаивает, чтобы не менее K метров он прошел пешком. Вася при этом хочет попасть домой как можно быстрее (обязательно выполнив требование мамы).

Вдоль проспекта расположено N трамвайных остановок, которые находятся в точках a₁, a₂, ..., a_N (все координаты задаются в метрах). Школа находится около 1-й остановки, а дом — около остановки номер N. Мальчик идет пешком со скоростью v метров в минуту. Трамвай едет со скоростью w метров в минуту (временем стоянки трамвая на остановках пренебрежем). В нулевой момент времени и далее с интервалом T минут от первой остановки в сторону Васиного дома отправляются трамваи. Вася выходит из школы также в момент времени 0. Сесть в трамвай и выйти из него можно только на остановке. При этом, если Вася приходит на остановку раньше трамвая, на который хочет сесть, то ему придется подождать, пока тот не подъедет. Вася идет пешком и едет на трамвае только в направлении от школы к дому.

Напишите программу, которая определит, когда Вася сможет оказаться дома.

Входные данные

Сначала вводится число N — количество остановок (1 ≤ N ≤ 2000). Далее заданы координаты остановок a₁, a₂, ..., a_N (0 ≤ a₁ < a₂ < ... < a_N ≤ 10⁹). Далее вводится интервал движения трамваев T (1 ≤ T ≤ 2000). Затем расстояние, не меньше которого Вася должен пройти пешком K (0 ≤ K ≤ 2000). Затем заданы скорости Васи v и трамвая w (1 ≤ v ≤ w ≤ 10 000). Все вводимые числа целые. K не превышает длины пути от школы до дома.

Выходные данные

В первую строку выведите не менее чем с пятью знаками после десятичной точки одно число — минимальное время, когда Вася сможет оказаться дома, пройдя пешком не менее K метров. Далее нужно вывести информацию о пути Васи. Занумеруем промежутки между соседними остановками числами от 1 до N - 1 (то есть промежуток между первой и второй остановками имеет номер 1, между второй и третьей — 2 и так далее). Следующая строка должна содержать количество промежутков, пройденных Васей пешком. Далее выведите номера этих промежутков в возрастающем порядке.

Примеры

Входные данные

Выходные данные

16.000000
1
1

Входные данные

Выходные данные

#2823

Путешествия в реальности

Темы: [Динамическое программирование на графах] [Алгоритмы на графах]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2010, Лига А, Задача J ]

Каждый раз, когда в мире происходит значимое событие, наша реальность разветвляется на несколько — в зависимости от исхода этого события. После этого существует уже не только наша основная реальность, но и ответвившиеся от неё в моменты появления разных исходов.

Однажды один архимаг решил сделать мир лучше. Такая грандиозная задача не под силу одному архимагу, поэтому он решил найти самого себя ещё в K реальностях и выполнить эту задачу вместе. Проведённое теоретическое исследование показало, что, кроме реальности, в которой находится именно он, существует ещё N - 1 реальностей. Для удобства они были занумерованы числами от 1 до N, при этом его собственная реальность имеет номер 1, а посетить ему необходимо реальности с номерами 2, 3, ..., K + 1.

Как уже говорилось, каждая реальность когда-то ответвилась от некоторой другой, за исключением одной Начальной реальности, которая существовала всегда (её номер может оказаться каким угодно; считается, что она появилась в момент времени 0). Исследование показало, что реальность с номером i ответвилась от реальности с номером P_i в момент времени T_i. Из каждой реальности с номером i архимаг может переместиться

в любую ответвившуюся от неё, то есть в любую j, такую что P_j = i;
в P_i, если i — не Начальная реальность.

Другими словами, возможны лишь переходы вида i <-> P_i. На каждый такой переход в любую сторону архимаг затрачивает T_i - T_{P_i} > 0 условных единиц энергии.

Требуется найти минимальное количество энергии, которое потребуется архимагу, чтобы, начав в реальности с номером 1, посетить все реальности с номерами от 2 до K + 1 (в любом порядке) и затем вновь вернуться в 1. Любую реальность при этом разрешается посещать сколько угодно раз.

Входные данные

Сначала вводятся два целых числа N и K (0 ≤ K < N ≤ 100 000): количество доступных реальностей и количество реальностей, которые необходимо посетить. Далее идёт N пар целых чисел, i-я пара — это P_i и T_i (1 ≤ P_i ≤ N, 0 ≤ T_i ≤ 10⁶; для Начальной реальности P_i = T_i = 0).

Гарантируется, что ответвившаяся реальность появилась строго позже породившей (T_i > T_{P_i}), и что маг может при желании добраться до любой из N реальностей.

Выходные данные

Выведите единственное число E — минимальную возможную энергию, которая потребуется архимагу для путешествия.

Примеры

Входные данные

Выходные данные