CCC '98 S3 - Mars Rover

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 Specification

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 Specification

For each excursion, the output should contain a line:

Distance is k

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

Comments


  • 2
    greenkeys  commented on March 23, 2020, 6:33 p.m. edit 2

    Hey guys,

    I need some help; I have no idea why my program gets WA in the first case but AC on every other case. Any feedback would be appreciated!

    Thanks

    Things I've tried:

    • replace input with sys.stdin.readline
    • look on past CCC test data (only input is provided)
    • remove unnecessary newlines

  • 2
    sankeeth_ganeswaran  commented on June 25, 2019, 4:06 p.m. edited

    what the heck is case 7


    • -1
      Jinx  commented on July 1, 2020, 5:32 p.m. edited

      The most annoying test case in history

      EDIT: There's a more annoying one lol