### 1998 Canadian Computing Competition, Stage 1

## Problem C: Mars Rover

A planetary "rover" is travelling on a perfectly level surface (no obstacles) on Mars. The rover is in radio communication with the "lander" it arrived in. The lander accumulates and relays commands, which it receives from Earth, to the rover. The rover makes several excursions. Each excursion begins with the rover at the lander facing in a known direction. At the end of each excursion the lander must compute and transmit a sequence of instructions to return the rover to the lander.

The rover responds to a sequence of commands sent from the lander. Each command tells the rover to move ahead some multiple of an exact unit of distance, or to turn left or right exactly 90 degrees.

The "move ahead" command is encoded using two consecutive lines in
the input file. The first line contains the integer 1, and the second line
contains a non-negative integer `n`, the distance to move forward.

The "turn right" command is encoded using a single input line
containing the integer 2.

The "turn left" command is encoded using a single input line
containing the integer 3.

For example, the following sequence of commands instructs the rover to turn
left, then move ahead 10 units, then turn right, and then move ahead 5 units.

3 1 10 2 1 5

Your task is, given such a sequence of commands, to determine how far the rover must travel to return to the lander, and to determine the shortest sequence of commands that will return the rover to the lander. In the example above, the rover must travel 15 units to return, and the shortest sequence of commands is

2 1 10 2 1 5

### Input

The input begins with a line containing a positive integer, `n`,
the number of excursions for the rover. The commands
for excursions occupy subsequent lines of the input file. Each excursion
consists of a number of commands followed by a line containing 0. There are no
errors or blank lines in the input. The rover travels less than 10 000
units of distance on each excursion.

### Output

For each excursion, the output should contain a line:

Distance isk

where `k` is the distance
in units that the rover must travel to return to the lander.
The following lines should contain the shortest sequence of commands to return
the rover to the lander. A blank line should separate
the lines of output for different excursions.

### Sample Input

3 2 3 3 0 3 1 10 2 1 5 0 1 5 2 1 5 3 3 1 1 0

### Sample Output

Distance is 0 Distance is 15 2 1 10 2 1 5 Distance is 9 1 4 3 1 5

All Submissions

Best Solutions

**Point Value:** 10

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Sep 29, 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)

SharkRetrieveron Jun 28, 2014 - 10:40:56 pm UTC 2\n2\n not accepted but 3\n3\n is?i.e.

2

2

1

600

turns into

3

3

1

600

Is there any reason why the first version is not considered just as optimal? Feel free to quote any part of the question that answers this. .-.

xiaowuc1on Jun 29, 2014 - 6:25:50 am UTC Re: 2\n2\n not accepted but 3\n3\n is?sigkillon Aug 18, 2014 - 6:16:12 am UTC Re: 2\n2\n not accepted but 3\n3\n is?Alexon Aug 18, 2014 - 7:05:50 am UTC Re: 2\n2\n not accepted but 3\n3\n is?Note to Brian: Consider displaying an error when alternate output files are missing.

failon Oct 02, 2011 - 2:23:36 pm UTC Some test cases ?jargonon Oct 02, 2011 - 4:52:06 pm UTC Re: Some test cases ?StealthAdepton Dec 05, 2008 - 1:46:58 am UTC What ifhansonw1on Dec 05, 2008 - 1:51:04 am UTC Re: What if