1524. Men in Black
Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ

Всем известно, что только наличие людей в черном (MIB) сдерживает чужих от вторжения на Землю.
Но недавно правительство узнало о MIB и решило начать отслеживать все их перемещения.

Выяснилось, что MIB – сверхсекретная организация и состоит из нескольких агентов. Каждый агент имеет несколько особенностей: точность, интеллект, скорость пешего передвижения, опыт, навык вождения. Все особенности характеризуются числом в пределах от 0 до 1. Каждый секретный агент закодирован буквой от "A" до "Z", потому что его имя – страшная тайна. Когда новый агент приезжает в организацию, ему присваивается буква еще назначенная ни одному агенту, самая близкая к первой букве в имени агента. Если есть несколько букв, выбирается первая из них по алфавиту.

Например, если в организации уже есть агенты "J", "K" и "L" , и прибыл новичок с именем "Killer", то он получит буквенное обозначение "I". MIB имеет несколько автомобилей, используемых агентами. Скорость агента за рулем равно его навыку вождения. Но некоторые специфичные автомобили требуют достаточного уровня опыта вождения у агента. То есть водить их может только агент, который имеет навык движения, не меньше некоторой предопределенной для данного типа автомобилей границы. Каждый автомобиль имеет свой ресурс - расстояние, которое он может проехать прежде, чем выйдет из строя.

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

1. Патрулирование - от офиса до указанной точки и назад. Для патрулирования расстояние от офиса до указанной точки задано.
2. Убийство чудовища – добраться до чудовища, убить его и вернуться. Для такого действия Вам указывают расстояние к чудовищу и его тип. Время, которое требуется агенту с точностью «a» чтобы убить чудовище с уклончивостью «e» равняется «e/a». После этого агент дополнительно получает «(1-x)+m/maxx» опыта, где «x» - предыдущий опыт агента, «m» некоторое значение опыта для данного типа чудовищ, и «maxx» - теоретически максимальная величина опыта. Точность агента возрастает на величину «(1-a)+e/maxe», где «maxe» - максимальная теоретически возможная уклончивость чудовища.
3. Расследование - добраться до точки, где будет проводиться расследование, выполнить его и вернуться назад. При этом задается расстояние в точку расследования, и минимальный интеллект, требуемый от агента для выполнения расследование. Время, необходимое для выполнения расследования агентом с интеллектом «i» есть «mint/i», где «mint» - минимальное временя необходимое для выполнения этого расследования. После того, как расследование завершено, агент выполнивший его, получает дополнительно «(1?x)·i/mint» опыта, где «x» - опыт агента перед действием, также его интеллект возрастает на «(1?i)·i/mint».
4. Переговоры – дойти до точки переговоров, обсудить там горячие вопросы и вернуться назад. Задается расстояние от офиса до точки переговоров, и минимальный опыта агента, который может принять участие на переговорах. Время необходимое для агента с опытом «x», чтобы завершить дискуссию - равное «mint/x» где «mint» - минимальное время. После того, как переговоры завершились, агент получает дополнительно опыт «(1?x)·x/mint ».

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

Все действия заканчиваются, как только они будут выполнены. Если есть несколько действий, то первым выполняется то, которое было получено первым.
После завершения действия, у выполнявшего его агента скорости пешей ходьбы возрастает на «(1?s)·d/maxd», где «s» - его пешая скорость до выполнения действия, «d» расстояние, которое он прошел в процессе выполнения, «maxd» - максимально возможное расстояние ходьбы. Если агент водил автомобиль, его навык вождения возрастает на «(1?z)·d/maxd», где «z» - предыдущий навык вождения этого агента.

Когда пара агентов выполняет действия, то характеристики пары определяются, по следующим правилам: скорость пешей ходьбы пары определяется по минимальной для каждого агента. Навык вождения – по максимуму, точность пары – «(a1+a2)/2», опыт пары – «1?(1?e1)·(1?e2)», интеллект пары – «1?(1?i1)·(1?i2)».
Следующие события могут произойти: новое задание может быть получено, новый агент может прибыть, новый автомобиль может быть куплен.
Если опыт агента становится большим или равным некоторой встроенной величины, названной «пенсионный опыт» - агент уходит в отставку.
Все интервалы времени в этой задаче измеряются в минутах, все интервалы округляются в ближайшую минуту, согласно общепринятым правилам округления.
Исходные данные
Все числа и слово во входных данных разделяются пробелами и/или переводом строки. Ввод содержит:

? Количество агентов (самое большее 26), сопровождающееся описанием агентов. Каждый агент описан следующими параметрами: имя, точность, скорость ходьбы, интеллект, опыт, навык вождения, назначенная буква. Все назначенные буквы - уникальны. Изначально опыт каждого агента меньше пенсионного порога.
? Количество типов автомобилей (максимум 50), после это для каждого типа автомобилей: минимальный навык необходимый для вождения данного типа, ресурс автомобиля (пробег до выхода из строя), имя типа.
? Количество автомобилей (самое большее 50), после это для каждого автомобиля указано: тип, пробег (не превышает максимальное значение для автомобилей этого типа), идентификатор.
? Количество типов чудовищ (самое большее 50), после это для каждого типа чудовищ указано: минимальный опыт, минимальный интеллект, с которым можно убить чудовище этого типа, уклончивость чудовищ этого типа, величина опыта получаемая после убийства чудовищ этого типа, и имя типа.
? Максимальное расстояние пешего прохода, максимальная уклончивость чудовищ, максимальный опыт для убийства чудовищ, пенсионный опыт.
? Количество событий в организации (самое большее 2000). Для каждого случая указано время его возникновения и параметры:
? Для нового агента, приходящего в организацию указано ключевое слово: "newagent". Дальше перечислено имя агента, его точность, пешая скорость, интеллект, опыт, навык вождения. Количество агентов никогда не превышает 26.
? Для нового купленного автомобиля: "newcar", тип автомобиля, текущий пробег, id.
? Для патрулирования: "quest run", расстояние из офиса к указанной точке.
? Для уничтожения чудовища: "quest kill", расстояние из офиса к чудовищу и тип чудовища.
? Для расследования: "quest findout", расстояние из офиса, минимально необходимый интеллект и минимальное время для расследования.
? Для переговоров: "quest talk" расстояние из офиса, минимально необходимый опыт и минимальное времени дискуссии.
Все характеристики – числа с плавающей точкой, в рамках от 0 до 1 (не включая). Все другие числа являются положительными целыми и не превышают 1000000. Все имена агентов, типы автомобилей, типы чудовищ и идентификаторы автомобилей содержат только буквы английского алфавита, их длина не превышает 10. Все имена и идентификаторы - уникальные. Все события сортированы по времени, нет событий с одинаковым временем.

Результат
Выведите все интересные моменты в следующем формате: "dddd:hh:mm <description>", где "dddd:hh:mm" день, час и минута когда интересное событие происходит. Следующие моменты – интересны:

? "New agent <name> got a letter <letter>."
? "MIB bought a car of class <car type>."
? "Agent <letter1>[ and agent <letter2>] started quest <number>[ using car <car id>]."
? "Agent <letter1>[ and agent <letter2>] killed monster <monster kind>.
? "Car <id> was broken." ()
? "Agent <letter1>[ and agent <letter2>] finished quest <number>."
? "Agent <letter> has tired."

/*
(Перевод:
? Новый агент <имя> получил букву <буква>
? Человек в черном купил автомобиль класса <тип автомобиля>
? Агент <буква1>[ и агент <буква2>], начали действие <номер действия>[ используя автомобиль <идентификатор автомобиля>].
? (Агент <буква1>[ и агент <буква2>], убили чудовище <тип чудовища>.
? Автомобиль <идентификатор> был разбит.
? Агент <буква1>[ и агент <буква2>], завершили действие <номер>."
? Агент <буква1> ушел в отставку.
*/

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

Thanks a lot!