To submit the solution for this problem go to the Problem set: 1524. Men in Black
C. Men in Black
Time limit: 3.0 second
Memory limit: 64 MB
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
There are four types of quests that men in black perform.
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.
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−x)·m/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−a)·e/maxe where maxe
is the maximal theoretically possible evasiveness of monsters.
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−x)·i/mint experience,
where x is the agent's experience before the operation.
His intelligence increases by (1−i)·i/mint.
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−x)·x/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−s)·d/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−z)·d/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
For a negotiations quest:
"quest talk" followed by the distance from the office,
the minimal required experience and the minimal discussion
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.
James 0.8 0.7 0.75 0.5 0.85 J
0.4 100 mibLexus
mibLexus 0 pq123bu
mibLexus 12 ab891ah
0.2 0.3 18 100 cockroach
200 20 200 0.95
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.
Problem Author: Dmitry Gozman
Problem Source: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007