CCO '09 P3 - Beware the Geoducks
View as PDFCanadian Computing Competition: 2009 Stage 2, Day 1, Problem 3
After perfecting the art of converting water to working C++ code, Stan Velikiy is once again facing his arch-nemesis, Mario the Wabbit. At the moment, Stan is chasing Mario on a circuit and you, as the amused observer, are being asked to predict the outcome.
The circuit can be thought as of series of nodes connected by wires of specified length. Stan and Mario each start at one of the nodes and travel along the nodes in a predetermined plan. They visit the nodes according to the plan, travelling along the wires at a speed of one meter per second. Once their travel plans run out, they stay stationary at that node.
If Stan and Mario are ever in the same location, Stan will apprehend Mario. If Stan
exceeds a time limit of he gives up and goes back to converting more water into C++ code.
Unknown to either Stan or Mario, there is a series of geoducks sitting at various nodes of the circuit. Even though they look harmless, they are remnants of top-secret experiments on the Infinite Ambiguity Drive which causes whoever reaches them to disappear instantly. Once either Mario or Stan disappear, Stan can never find Mario. Note that if Stan finds Mario on a node with a geoduck, they both disappear and Stan never finds Mario.
Input Specification
The first line contains six integers: , the number of nodes
;
,
the number of wires;
and
, the number of nodes in the routes
taken by Stan and Mario, respectively;
, the number of geoducks; and
, the time limit.
The next lines contain
integers per line, specifying two nodes that a wire connects
and the length
of the wire. No wire connects a node to itself and there is
at most one wire between two nodes.
The next lines contain one integer per line, which indicate the nodes of Stan's route in
the order of being visited.
The next lines contain one integer per line, the nodes of Mario's route in the order
of being visited.
The last lines contain one integer per line, where each line indicates the location (node)
where there is a geoduck.
Output Specification
On one line, output YES if Stan catches Mario before the time limit expires, NO otherwise.
Sample Input
3 1 2 2 1 3
1 2 6
1
2
2
1
3Description of Sample Input
Stan travels from node 1 to 2 while Mario moves in the other direction. There is a geoduck on node 3.
Output for Sample Input
YESDescription of Output for Sample Input
Stan catches the Mario just as time expires, and fortunately none of them ever find a geoduck.
Comments
I don't understand the sample input.
If the wire between nodes 1 and 2 has a length of 6, won't it take 6 seconds to traverse?
Since the time limit is 3 seconds, won't Stan run out of time and not catch Mario?
At the bottom of the problem statement, the description of output for sample input explicitly says that Stan catches the Mario just as time expires. You are correct in assessing that the wire between nodes 1 and 2 has length 6, and so it would take 6 seconds for one person to traverse the entire length of the wire.
If you read the description of the sample input, you'll note that Stan starts at node 1 and travels to node 2, and Mario starts at node 2 and travels to node 1. In three seconds, both of them will have traveled exactly half the distance of the wire, but because they started at opposite ends of the wire, they meet at the midpoint of the wire after 3 seconds, just as time expires.