eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Люди у чорному

Люди у чорному

Ліміт часу 3 секунди
Ліміт використання пам'яті 64 MiB

Як відомо, "Люди у чорному" захищають нашу землю від нашестя інопланетних тарганів та інших шкідників. Вони слідкують за усіма переміщеннями інопланетних ворогів та друзів і контролюють їх дії. Але нещодавно про діяльність "Людей у чорному" взнав уряд і вирішив слідкувати за ними.

В організації "Люди у чорном" працюють декілька агентів. У кожного агента є декілька характеристик: точність, кмітливість, швидкість пішки, досвід та вміння керувати автомобілем. Усі характеристики від нуля до одиниці. Крім того, кожному агенту присвоєно певну літеру від "A" до "Z", а ім'я його - секретна інформація. Коли до організації прибуває новий агент, йому підбирають вільну літеру (яка не приначена щодному агенту), найближчу до першої літери імені агента. Якщо таких декілька, то обирається перша у лексикографічному порядку літера. Наприклад, якщо в організації вже є агенти "J" та "K", а прийшов агент з іменем "Killer", то він отримає літеру "L".

"Люди у чорному" володіють декількоми автомобілями різних класів, якими користуються агенти. При цьому швидкість руху агента на довільному автомобілі дорівнює його вмінню керувати автомобілем. Але для використання деяких автомобілів необхідно мати вміння не менше деякого значення. Для кожного класу автомобілів відомий максимальний пробіг, після якого автомобіль приходить у непридатність.

У всесвіті існують декілька різних видів інопланетних монстрів, з якими приходиться воювати "Людям у чорному". Щоб агент міг вбити монстра, він повинен мати досвід і кмітливість не нижче мінімальних для даного виду монстрів. При цьому, кожен монстр має ухильніст, і агенти з невисокою точністю можуть дуже довго пробувати попасти в ухильного монстра. Монстр певного типу дає деяку кількість досвіду агенту, який його вбив.

По мірі роботи агенти "Людей у чорному" отримують різні завдання, які бувають чотирьох типів.

  1. Завдання на доставку підрозумівають доїхати до точки призначення і повернутись назад. Для таких завдань відома відстань від офіса "Людей у чорному".

  2. При виконанні завдання на знищення монстра потріб добратись до монстра, вбити його, і повернутись назад. Відома відстань до монстра, його клас. Час, який агент з точністю accuracy витратить на те, щоб вбити монстра з уильністю evasiveness, дорівнює evasiveness/accuracy. При цьому агент отримає (1-experience)*monsterExperience/maxMonsterExperience, де experience - досвід агента, monsterexperience - досвід за вбивство даного виду монстрів, maxMonsterExperience - максимальний досвід за вбивство монстрів, і його точність збільшується на (1-accuracy)*evasiveness/maxEvasiveness, де accuracy - його точність до того, як агент вбил монстра. Щоб агент зміг вбити монстра, він повинен мати кмітливість і досвід не нижче мінімальних для даного типа монстрів.

  3. Ще один вид завдань - завдання на розслідування пригоди. Для такого завдання відома відстань від офіса, мінімальна кмітливість агента, який може провести розслідування. При цьому час, який агент потратить, дорівнює minTime/intellect, де intellect - кмітливість агента, minTime - мінімальний час на дане розслідування. При цьому агент отримає (1-experience)*intellect/minTime досвіду, де experience - його досвід до розслідування, і на (1-intellect)*intellect/minTime збільшить свою кмітливість.

  4. Останній вид завдань - це перемовини з представниками інших планет. Тут, чим досвідченіший агент, тим краще. Для таких завдань відомі відстань від офіса і мінимальний досвід агента, який зможе вести перемовини. Час, який агент потратить на перемовини, дорівнює 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." - агент <буква> ушел на пенсию по достижении соответствующего опыта.

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

Приклад

Вхідні дані #1
1
James 0.8 0.7 0.75 0.5 0.85 J

1
0.4 100 mibLexus

2
mibLexus 0 pq123bu
mibLexus 12 ab891ah

1
0.2 0.3 18 100 cockroach

200 20 200 0.95

4
10 newagent Klint 0.9 0.8 0.5 0.7 0.86
20 quest run 48
30 newcar mibLexus 47 aa890bu
43 quest kill 100 cockroach
Вихідні дані #1
0000:00:10    New agent Klint got a letter K.
0000:00:20    Agent K started quest 1 using car ab891ah.
0000:00:30    MIB bought a car of class mibLexus.
0000:00:43    Agent J started quest 2 using car pq123bu.
0000:02:02    Car ab891ah was broken.
0000:02:12    Agent K finished quest 1.
0000:02:41    Car pq123bu was broken.
0000:03:04    Agent J killed monster cockroach.
0000:05:26    Agent J finished quest 2.
Автор Dmitry Gozman
Джерело Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007