ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Dmitry Gozman Contest 1. Petrozavodsk training camp. Winter 2007

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Men in Black

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
Everybody knows that men in black protect our Earth from alien cockroaches and other vermin. They track all movements of our alien foes and friends and control their actions. But recently the government has learned about men in black and decided to track all their movements.
There are several agents. Each agent has several characteristics: accuracy, intelligence, walking speed, experience, driving skill. All characteristics are real numbers ranging from 0 to 1. Also each agent has a code letter "A" to "Z", since his name is top secret. When the new agent comes to the organization he is assigned a letter closest to the first letter of the agent name, that is not assigned to any agent. If there are several such letters, the one which goes first lexicographically is chosen. For example, if there are already agents "J", "K" and "L" in the organization, and the agent with the name "Killer" comes, he gets the letter "I".
Men in black have several cars that agents use in their work. The speed of the agent when driving is equal to his driving skill. But some cars require the agent that drives it to have a driving skill greater or equal to some predefined value. Each car has some distance that it can pass before it can no longer be used.
There are several kinds of alien monsters in the universe that men in black fight with. The agent can kill a monster if his experience and his intelligence are greater or equal to some predefined values for this kind of monster. Each kind of monster has evasiveness, and depending on the agent's accuracy it can take different time to kill a monster. A killed monster gives the agent who has killed him some experience.
There are four types of quests that men in black perform.
  1. Delivery quest — get from the office to the destination point and back. For such quests the distance from the office to the destination point is given.
  2. Kill the monster quest — get to the monster, kill him, get back. For such a quest you are given a distance to the monster and its kind. The time that an agent with accuracy a needs to kill a monster with evasiveness e is equal to e/a. The agent gets (1−xm/maxx experience, here x is the experience of the agent, m is some experience value that is associated with this kind of monster, and maxx is the theoretically maximal experience value. Agent's accuracy increases by (1−ae/maxe where maxe is the maximal theoretically possible evasiveness of monsters.
  3. Investigation — get to the point where the investigation is needed, perform it, get back. For such a quest you are given a distance to the investigation point, and the minimal intelligence required to perform the investigation. The time needed to perform an investigation by an agent with intelligence i is mint/i where mint is the minimum time required to perform this investigation. After completing the investigation the agent gets (1−xi/mint experience, where x is the agent's experience before the operation. His intelligence increases by (1−ii/mint.
  4. Negotiations — get to the point of negotiations, discuss hot issues, get back. You are given the distance from the office to the negotiations point, and the minimal experience of an agent that can take part in negotiations. The time needed for an agent with experience x to complete the discussion is equal mint/x where mint is the minimum time needed. After the negotiations the agent gets (1−xx/mint additional experience.
Each quest can be performed by one or two agents. If two agents perform the same quest, after it their characteristics change as if each of them completed this quest alone. An agent can walk to the location where the quest must be performed, or drive there. If the car breaks while the agent is driving, he must continue to walk to the location he was driving to. If the quest is performed by two agents, they can use the same car to get to its location.
The following algorithm is used to choose an agent or a pair of agents to perform the quest. An agent (a pair of agents) is chosen that would perform the quest in the shortest time. If there are several possibilities, the following tie breaking rules are used. If it is possible to choose one agent or a pair of agents, one agent is chosen. If there are two candidate agents, the one who has the smaller letter assigned is chosen (for pairs of agents the ordered pairs of letters are compared). Agents always choose a car in such a way to perform their quest in the shortest time. If the quest is completed without using a car within the same time, the car is not used. If there are several cars available with the same quest performing time, the car with the lexicographically smaller id is chosen.
All quests are performed as soon as they can be performed. If there are several quests available, the one that was received earlier is performed first.
After the agent completed the quest where he had to walk, his walking speed increases by (1−sd/maxd where s is his walking speed before the quest, d is the distance he walked while performing the quest, maxd is the maximal possible walking distance. If the agent was driving a car for some distance, his driving skill increases by (1−zd/maxd where z is the driving skill of the agent before the quest, d is the distance he drove while performing the quest.
When the pair of agents perform the quest, the characteristics of the pair are calculated using the following algorithm. Pair's walking speed is minimum of agents' walking speeds, pair's driving skill is maximum of agents' driving skills, pair's accuracy is (a1+a2)/2, pair's experience is 1−(1−e1)·(1−e2), pair's intelligence is 1−(1−i1)·(1−i2).
The following events can happen: new quest can be received, new agent can come, new car can be bought.
If the agent's experience becomes greater or equal to some predefined value called retirement experience, the agent gets tired and leaves the organization immediately after finishing his last quest. His letter becomes free and a new agent can get it from that moment. It is guaranteed that at each moment there are no more than 26 agents in the agency, no more than 50 non-broken cars, and no more than 50 received but not yet started quests.
All time intervals in this problem are measured in minutes, all time interval lengths are rounded to the closest minute, standard rounding rules are used. For example, the intervals when an agent drives a car, when he walks after the car is broken, when he kills a monster must be rounded separately.

Исходные данные

All numbers and words in the input are separated by spaces and/or line feeds.
The input contains:
  • The number of agents (at most 26) followed by the description of agents. Each agent is described by his name, accuracy, walking speed, intelligence, experience, driving skill, and the letter he is assigned. All assigned letters are different. Experience of each agent is less than the retirement experience.
  • The number of car types (at most 50), after that for each car type: the minimal required driving skill to drive the car of this type, the distance the car of this type can run before breaking, the name of the type.
  • The number of cars (at most 50), after that for each car: its type, current distance passed (not exceeding the maximal distance for cars of this type), its id.
  • The number of monster kinds (at most 50), after that for each monster kind: the minimal experience needed to kill a monster of this kind, minimal intelligence needed to kill a monster of this kind, evasiveness of monsters of this kind, experience value associated with monsters of this kind, and the name of this kind.
  • Maximal walking distance, maximal monsters evasiveness, maximal experience for monster killing, retirement experience.
  • The number of events in the organization (at most 2000). After that for each event the time it occurs and:
    • For a new agent coming to the organization: "newagent", followed by agent's name, his accuracy, walking speed, intelligence, experience, driving skill. The number of agents never exceeds 26.
    • For a new car bought: "newcar" followed by the type of the car, its current distance passed, its id.
    • For a delivery quest: "quest run" followed by the distance from the office to the destination point.
    • For a kill the monster quest: "quest kill" followed by the distance from the office to the monster and the monster type.
    • For an investigation quest: "quest findout" followed by the distance from the office, the minimal required intelligence and the minimal investigation time.
    • For a negotiations quest: "quest talk" followed by the distance from the office, the minimal required experience and the minimal discussion time.
All characteristics are floating point numbers ranging from 0 to 1 (not inclusive) with no more than 2 digits after decimal point. Minimal required characteristics for quests might be equal to zero. All other numbers are positive integers and do not exceed 106. All agent names, car type names, monster kind names, and car ids contain only letters of the English alphabet and digits, the lengths of the names do not exceed 10. All names and ids are different. All events are sorted by the time of occurrence, all times are different.

Результат

Output all interesting moments to the output in the following format: "dddd:hh:mm   <description>", where "dddd:hh:mm" are day, hour and minute when the interesting event occurs.
The following moments are interesting (pay attention to the order):
  • "MIB bought a car of class <car type>."
  • "Car <id> was broken."
  • "Agent <letter1>[ and agent <letter2>] killed monster <monster kind>."
  • "Agent <letter1>[ and agent <letter2>] finished quest <number>."
  • "Agent <letter> has tired."
  • "New agent <name> got a letter <letter>."
  • "Agent <letter1>[ and agent <letter2>] started quest <number>[ using car <car id>]."
All quests are numbered starting from 1 in order they are received. If several interesting events occur simultaneously, they must be listed in the same order they are described above. If several interesting events of the same type occur simultaneously, they must be listed in lexicographic order. If two agents perform the quest they must be listed in the messages in the order of their code letters.
It is guaranteed that all quests can be performed by men in black before 10000 day since beginning.

Пример

исходные данныерезультат
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
0000:00:10    New agent Klint got a letter K.
0000:00:20    Agent J started quest 1 using car pq123bu.
0000:00:30    MIB bought a car of class mibLexus.
0000:00:43    Agent K started quest 2 using car ab891ah.
0000:02:12    Agent J finished quest 1.
0000:02:25    Car ab891ah was broken.
0000:03:00    Agent K killed monster cockroach.
0000:05:05    Agent K finished quest 2.
Автор задачи: Dmitry Gozman
Источник задачи: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1524. Men in Black