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:
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:
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 Ls and Rs, representing a sequence of moves that will charm your snake from the starting point to the goal square.
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.
© Australian Mathematics Trust 2001-2023
Page generated: 24 March 2023, 8:15pm AEDT