Люди в черном
Как известно, "Люди в черном" защищают нашу землю от нашествия инопланетных тараканов и других вредителей. Они следят за всеми перемещениями инопланетных врагов и друзей и контролируют их действия. Но недавно о деятельности "Людей в черном" узнало правительство и решило следить за ними.
В организации "Люди в черном" работают несколько агентов. У каждого агента есть несколько характеристик: точность, сообразительность, скорость пешком, опыт и умение водить автомобиль. Все характеристики от нуля до единицы. Кроме того, каждому агенту присвоена определенная буква от "A" до "Z", а имя его - секретная информация. Когда в организацию приходит новый агент, ему подбирают свободную букву (которая не назначена ни одному агенту), ближайшую к первой букве имени агента. Если таких несколько, то выбирается первая в лексикографическом порядке буква. Например, если в организации уже есть агенты "J" и "K", а пришел агент с именем "Killer", то он получит букву "L".
"Люди в черном" владеют несколькими автомобилями различных классов, которыми пользуются агенты. При этом скорость движения агента на любом автомобиле равна его умению водить автомобиль. Но для использования некторых автомобилей необходимо иметь умение не менее некоторого значения. Для каждого класса автомобилей известен максимальный пробег, после которого автомобиль приходит в негодность.
Во вселенной существуют несколько различных видов инопланетных монстров, с которыми приходится сражаться "Людям в черном". Чтобы агент мог убить монстра, он должен иметь опыт и сообразительность не ниже минимальных для данного вида монстров. При этом, каждый монстр обладает уклончивостью, и агенты с невысокой точностью могут очень долго пытаться попасть в уклончивого монстра. Монстр определенного типа дает некоторое количество опыта агенту, убившему его.
По мере работы агенты "Людей в черном" получают различные задания, которые бывают четырех типов.
Задания на доставку подразумевают доехать до точки назначения и вернуться назад. Для таких заданий известно расстояние от офиса "Людей в черном".
При выполнении здания на уничтожение монстра надо добраться до монстра, убить его, и вернуться назад. Известно расстояние до монстра, его класс. Время, которое агент с точностью accuracy потратит на убиение монстра уклончивости evasiveness равно evasiveness/accuracy. При этом агент получит (1-experience)*monsterExperience/maxMonsterExperience, где experience - опыт агента, monsterexperience - опыт за убийство данного вида монстров, maxMonsterExperience - максимальный опыт за убийство монстров, и его точность увеличится на (1-accuracy)*evasiveness/maxEvasiveness, где accuracy - его точность до того, как агент убил монстра. Чтобы агент смог убить монстра, он должен иметь сообразительность и опыт не ниже минимальных для данного типа монстров.
Еще один вид заданий - задание на расследование происшествия. Про такое задание известно расстояние от офиса, минимальная сообразительность агента, который может провести расследование. При этом время, которое агент потратит, равно minTime/intellect, где intellect - сообразительность агента, minTime - минимальное время на данное расследование. При этом агент получит (1-experience)*intellect/minTime опыта, где experience - его опыт до расследования, и на (1-intellect)*intellect/minTime увеличит свою сообразительность.
Последний вид заданий - это переговоры с представителями других планет. Здесь, чем опытнее агент, тем лучше. Про такие задания известно расстояние от офиса и минимальный опыт агента, который сможет вести переговоры. Время, которое агент затратит на переговоры, равно minTime/experience, где experience - опыт агента, minTime - минимальное время на эти переговоры. Агент получит (1-experience)*experience/minTime опыта.
На каждое задание "Люди в черном" отправляют одного или двух агентов. Если агентов двое, то их характеристики изменяются также, как если бы они выполнили задание по-одинчоке. Агент может поехать на задание на машине или пойти пешком. Если по дороге машина сломается, то агент вынужден оставшуюся часть задания ходить пешком. На задание отправляется тот агент (либо та пара агентов), который выполнит задание быстрее всего. Если таких несколько, то используются несколько правил. Во-первых, один агент лучше, чем два. Во-вторых, из двух агентов посылают того, у кого буква раньше в алфавите (если агентов по двое, то сравниваются упорядоченные пары букв). В-третьих, если пешком задание выполнится не медленнее, то автомобиль агент не берет. В-четвертых, из нескольких автомобилей выбирается автомобиль с минимальным номером.
Все задания выполняются в минимальный момент времени, как только можно их выполнить. Если несколько заданий могут быть выполнены в один момент, приоритет отдается заданию, поступившему раньше.
Когда агент движется пешком, его скорость растет на величину (1-speed)*distance/maxDistance, где speed - его скорость на начало движения, distance - расстояние, которое он прошел и maxDistance - максимальное расстояние, которое может пройти агент. Аналогично, умение водить автомобиль растет на величину (1-auto)*distance/maxDistance. При расчетах используются характеристики агента на начало выполнения текущего квеста.
Когда агенты работают в паре, то для них высчитываются суммарные характеристики. При этом пешая скорость равна минимальной из двух скоростей, умение управлять автомобилем - максимальное из двух, точность пары есть полусумма точностей агентов. Суммарный опыт равен 1-(1-e_1)*(1-e_2), где e_1 и e_2 - опыт первого и второго агента. Аналогично, суммарная сообразительность равна 1-(1-i_1)*(1-i_2).
Кроме заданий, в организацию может прийти новый агент, либо "Люди в черном" могут купить новый автомобиль.
Когда опыт агента превышает заданный предел, то агент устает работать в организации "Люди в черном" и уходит на пенсию. Но в любом случае, агент доведет текущее задание до конца.
Можете считать, что время округляется до минут, все разговоры в офисе не занимают времени.
Ваша задача - написать программу, которая по заданным описаниям заданий выдаст действия всех агентов.
Входные данные
Все числа и строки во входном файле могут быть разделены пробелами и переводами строк.
Входной файл содержит:
Количество агентов (не более 26), затем для каждого агента его имя, точность, скорость ходьбы, сообразительность, опыт, умение водить машину и букву, которая ему приписана. Все бкувы различны.
Количество типов автомобилей (не более 50), затем для каждого типа минимальное умение агента, чтобы он смог управлять автомобилем, максимальный пробег и название типа.
Количество автомобилей (не более 50), затем для каждого автомобиля название типа, текущий пробег (не более максимального пробега) и номер автомобиля.
Количество видов монстров (не более 50), затем для каждого типа минимальный опыт, необходимый для убийства этого монстра, минимальную сообразительность, уклончивость, опыт за убийство и название вида.
Максимальное расстояние, которое может пройти агент, максимальную уклончивость монстров, максимальный опыт за убийство монстров и максимальный опыт, по достижении которого агент уходит на пенсию.
Количество событий в организации (не более 2000). Затем для каждого события:
время его возникновения.
При появлении нового агента: "newagent", затем имя агента, его точность, скорость ходьбы, сообразительность, опыт и умение водить автомобиль.
При появлении нового автомобиля: "newcar", название типа автомобиля, его текущий пробег и номер.
Для задания на доствку: "quest", "run" и расстояние от офиса "Людей в черном".
Для убийства монстра: "quest", "kill", расстояние от офиса и название вида монстра.
Для расследования: "quest", "findout", расстояние от офиса, минимальная сообразительность и минимальное время расследования.
Для переговоров: "quest", "talk", расстояние от офиса, минимальный опыт и минимальное время переговоров.
Все характеристики - вещественные числа от нуля до единицы. Все остальные числа во входном файле целые, по модулю не более 10^6. Все имена агентов, названия типов автомобилей и монстров и номера автомобилей состоят из латинских букв и цифр, их длина не более десяти. Все имена, названия и номера различны. События отсортированны по времени, время поступления всех событий различно.
Выходные данные
В выходной файл выведите все события в следующем формате: "dddd:hh:mm <Описание события>", где"dddd:hh:mm" - день, час и минута возникновения события от начального момента времени, "<Описание события>" - одно из описаний, перечисленных ниже.
"New agent <имя> got a letter <буква>." - новый агент по имени <имя> получил букву <буква>.
"MIB bought a car of class <название>." - появился новый автомобиль класса <название>.
"Agent <буква1>[ and agent <буква2>] started quest <номер>[ using car <номер автомобиля>]." - агент <буква1> (и, возможно, агент <буква2>) начал исполнение задания <номер>, возможно, с использованием автомобиля <номер автомобиля>.
"Agent <буква1>[ and agent <буква2>] killed monster <название>." - агент <буква1> (и, возможно, агент <буква2>) убил монстра вида <название>.
"Car <номер> was broken." - автомобиль <номер> выработал свой ресурс (достиг максимального пробега).
"Agent <буква1>[ and agent <буква2>] finished quest <номер>." - агент <буква1> (и, возможно, агент<буква2>) окончил исполнение задания <номер>.
"Agent <буква> has tired." - агент <буква> ушел на пенсию по достижении соответствующего опыта.
Задания нумеруются с единицы, в порядке их перечисления во входном файле. Если несколько событий происходят в одно время, то их необходимо выводить в том порядке, как они перечислены выше (например, сначала пришел новый агент, а затем сломался автомобиль).