2004 Canadian Computing Competition, Stage 1

Problem S4: Space Turtle

Space Turtle is a fearless space adventurer. His spaceship, the Tortoise, is a little outdated, but still gets him where he needs to go.

The Tortoise can do only two things - move forward an integer number of light-years, and turn in one of four directions (relative to the current orientation): right, left, up and down. In fact, strangely enough, we can even think of the Tortoise as a ship which travels along a 3-dimensional co-ordinate grid, measured in light-years.

In today's adventure, Space Turtle is searching for the fabled Golden Shell, which lies on a deserted planet somewhere in uncharted space. Space Turtle plans to fly around randomly looking for the planet, hoping that his turtle instincts will lead him to the treasure.

You have the lonely job of being the keeper of the fabled Golden Shell. Being lonely, your only hobby is to observe and record how close various treasure seekers come to finding the deserted planet and its hidden treasure.

Given your observations of Space Turtle's movements, determine the closest distance Space Turtle comes to reaching the Golden Shell.

Input

The first line consists of three integers sx, sy, and sz, which give the coordinates of Space Turtle's starting point. Space Turtle is originally oriented in the positive x direction, with the top of his spaceship pointing in the positive z direction, and with the positive y direction to his left. Each of these integers are between -100 and 100.

The second line consists of three integers tx, ty, and tz, which give the coordinates of the deserted planet. Each of these integers are between -10000 and 10000.

The rest of the lines describe Space Turtle's flight plan in his search for the Golden Shell. Each line consists of an integer, d, 0 ≤ d ≤ 100, and a letter c, separated by a space. The integer indicates the distance in light-years that the Tortoise moves forward, and the letter indicates the direction the ship turns after having moved forward. `L', `R', `U', and `D' stand for left, right, up and down, respectively. There will be no more than 100 such lines.

On the last line of input, instead of one of the four direction letters, the letter `E' is given instead, indicating the end of today's adventure.

Output

Output the closest distance that Space Turtle gets to the hidden planet, rounded to 2 decimal places.

If Space Turtle's coordinates coincide with the planet's coordinates during his flight indicate that with a distance of 0.00. He safely lands on the planet and finds the Golden Shell.

Sample Input

0 0 0
1 1 1
2 L
2 L
2 U
2 U
2 L
2 L
2 U
2 E

Sample Output

1.41

All Submissions
Best Solutions


Point Value: 12
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 28, 2008

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Does the turtle stay facing -> and goes up in this position or does it turn upward so the front is facing up and goes upward?

The U instruction means that the Space Turtle adjusts himself so that whatever direction currently seems to him to be UP is now his FRONT, and LEFT and RIGHT stay the same as they were before.

Can someone please explain how the input works. I know the problem statement tells me how to do it but I'm still quite confused.

You start facing a positive x direction. The you move in that direction and afterwards you change direction?

So for the sample, you start off with 0 0 0
Then you move to 2 0 0?
Then you move to 2 2 0?