Want to try solving this problem? You can submit your code online if you log in or register.

You are a snake charmer performing for a travelling circus troupe. For your next act, you will show off your skills by charming your snake to move to a place selected by an audience member. To perform this act, you have created a grid for your snake to move around in. Initially your snake starts off in a square in the middle of this grid facing north, and you will ask the audience for a goal square for your snake to reach. However, your snake is very peculiar: it only likes to move by zigzagging around. More specifically you can only make your snake move in two ways:

- An
`L`move: make it turn left and then move forward by one square. - An
`R`move: make it turn right and then move forward by one square.

For instance, consider the following grid in a coordinate system.

Your snake will always start off at the square (0,0). In the above grid, the flag square at (-1,2) represents the goal square selected by the audience, and the dots show the path taken. The snake is initially facing north, so the sequence of moves taken by it are:

- An
`R`move: it turns right to face east and moves forward one square to the square (1,0). - An
`L`move: it turns left to face north and moves forward one square to the square (1,1). - An
`L`move: it turns left to face west and moves forward one square to the square (0,1). - An
`R`move: it turns right to face north and moves forward one square to the square (0,2). - An
`L`move: it turns left to face west and moves forward one square to square (-1,2), which is the goal square where it stops.

Now, you realise that the longer it takes for your snake to get to the goal square, the less interested your audience will become. Can you find the shortest path for you to charm your snake to the goal square? If there are multiple shortest paths, you only need to find one of them.

The input file consists of one line with two integers x and y representing the (x,y) coordinates of the goal square.

Your output file should consist of a single line of `L`s and `R`s, representing a sequence of moves that will charm your snake from the starting point to the goal square.

-1 2

RLLRL

This is the example case explained in the description of this problem.

For all subtasks, it is guaranteed that -5000 ≤ x, y ≤ 5000. Additionally, (x,y) will never be (0,0).

To score all the points for a subtask, the path you output must be the shortest one possible. If you output a path that is not the shortest, but still arrives at the goal square, you will get 50% of the marks of the subtask. If you output a path that does not reach the goal square at all, you will get zero marks.

- For Subtask 1 (20 marks), -5 ≤ x, y ≤ 5.
- For Subtask 2 (10 marks), x = y.
- For Subtask 3 (10 marks), x = 0.
- For Subtask 4 (15 marks), x ≥ y ≥ 0.
- For Subtask 5 (10 marks), -100 ≤ x, y ≤ 100.
- For Subtask 6 (35 marks), no further constraints apply.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 1 December 2021, 10:53am AEDT