TopCoder problem "EvilRobot" used in College Tour West China (Division I Level Two)



Problem Statement

    

An evil robot has been tormenting your land for years. You decided to get rid of him by creating a deadly trap. The trap is now ready, and the only problem left is to make the robot walk inside it. Luckily, you managed to hack into the robot's movement system, and you can reprogram it to move the way you want.

The land is represented by an infinite grid of cells. The robot is currently standing in cell (robotX, robotY), and the trap is set in cell (trapX, trapY). The robot's program is very simple and consists of N commands, where each command is one of:

  • 'U': the robot moves from coordinates (x, y) to coordinates (x, y + 1).
  • 'R': the robot moves from coordinates (x, y) to coordinates (x + 1, y).
The commands are executed in order, starting from the first one, and the program is cyclical (i.e., after the last command is executed, it will start over from the first command).

As soon as the robot walks into the trap, the program will stop executing. Write a program with exactly N commands that will make the robot walk into the trap. Return this program as a String, where the i-th character is the i-th command. If there are multiple possible programs, return the one among them that comes first alphabetically. If no such program exists, return "I'LL GET YOU NEXT TIME" (quotes for clarity) instead.

 

Definition

    
Class:EvilRobot
Method:createProgram
Parameters:int, int, int, int, int
Returns:String
Method signature:String createProgram(int N, int robotX, int robotY, int trapX, int trapY)
(be sure your method is public)
    
 

Constraints

-N will be between 1 and 50, inclusive.
-robotX will be between 0 and 1000000000, inclusive.
-robotY will be between 0 and 1000000000, inclusive.
-trapX will be between 0 and 1000000000, inclusive.
-trapY will be between 0 and 1000000000, inclusive.
 

Examples

0)
    
3
1
1
3
4
Returns: "RUU"
The robot starts at point (1,1). After executing the commands RUURU, he steps into the trap at (3,4). There is one more program that leads to the trap (URU), but RUU comes earlier alphabetically.
1)
    
10
1
1
1
4
Returns: "UUURRRRRRR"
Here the trap is straight above the robot, so the first three of his moves must be U.
2)
    
3
2
1
1
1
Returns: "I'LL GET YOU NEXT TIME"
The robot is already to the right of the trap. This time there is nothing you can do.
3)
    
5
2
2
12
12
Returns: "I'LL GET YOU NEXT TIME"
Even though the robot hasn't passed the trap yet, it's not possible to create a program with 5 commands that leads into it.
4)
    
48
3
0
3000000
5000000
Returns: "RRRRRRRRRUUUUUUUUUUUUUUUUUUUURRRRRRRRRUUUUUUUUUU"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8821

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12240&pm=8821

Writer:

slex

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Greedy, Simple Math