TopCoder problem "ShrinkingPills" used in SRM 289 (Division I Level Three)



Problem Statement

    

You have to escape from a laboratory, and you have pills number of "shrinking pills" to help you. Your normal height is 100 units, but when you take one of these pills your height decreases by pspeed units each second. You keep shrinking until your height reaches zero or less, and at that moment, you instantly return to your normal height. For example, if you take a pill that reduces your height by 40 units per second at time 0, your height will be 60 at time 1, then 20 at time 2, and 100 again at time 3. Note that you will never be zero or less units tall. You can only take one pill at a time, and you can only take a pill when you are at your normal size.

There are doors in the laboratory that close downward from the ceiling to the floor. All the doors start closing immediately. Each door is door units tall and drops down by dspeed units each second. For example, consider a door with a height of 200 units, and a closing speed of 150. The door will be 200 units from the floor at time 0, 50 units from the floor at time 1, and fully closed at time 2.

All movements are discrete and simultaneous. For example, suppose you are standing next to a door that is 200 units from the floor. The door's closing speed is 125, and your pill's shrinking speed is 25. You take the pill and move towards the door. In the next second, the door will be 75 (200-125) units from the floor, you will be 75 units tall and you will be standing right under the door. If you do not move again, the door will kill you in the next second. If you do move, you'll be on the other side of the door with a height of 50 units, and the door will be fully closed.

At each second, you can either stay where you are or move horizontally or vertically by one square. You will be given a map of the laboratory as a String[], where '@' represents your starting square, 'E' the exit, '#' a wall, uppercase 'X' a door and ' ' (space) an empty square. The laboratory will be completely surrounded by walls.

You are given pills, the number of available pills, pspeed, the shrinking speed of the pills, dspeed, the closing speed of the doors, door, the height of each door, and lab, the map of the laboratory. Return the minimum number of seconds needed to escape from the laboratory, or -1 if it is not possible.

 

Definition

    
Class:ShrinkingPills
Method:escape
Parameters:int, int, int, int, String[]
Returns:int
Method signature:int escape(int pills, int pspeed, int dspeed, int door, String[] lab)
(be sure your method is public)
    
 

Constraints

-pills will be between 0 and 10, inclusive.
-pspeed will be between 1 and 99, inclusive.
-door will be between 1 and 200, inclusive.
-dspeed will be between 1 and door, inclusive.
-lab will contain between 3 and 50 elements, inclusive.
-Each element of lab will contain between 3 and 50 characters, inclusive.
-Each element of lab will be of the same size.
-Each character in lab will be either ' ', 'X', '#', '@' or 'E'.
-lab will contain exactly one '@'.
-lab will contain exactly one 'E'.
-lab will be surrounded by '#'.
 

Examples

0)
    
3
50
1
100
{"######################",
 "#@    X     X     X E#",
 "######################"}
Returns: 19
Second 0: You are standing on the '@' and all the doors are 100 units from the floor.

...

Second 4: You are next to the first door and it is 96 units from the floor. Your height is 100, and therefore you have to take a pill to be able to pass under the door.

Second 5: You have taken a pill and your height is 50 units. You are standing under the door which is 95 units from the floor.

Second 6: You have returned to your normal height. The first door has been left behind.

...

Second 17: You have taken the last pill. You are 50 units tall and you are standing under the last door that is 83 units from the floor.

...

Second 19: You reach the exit point.

1)
    
1
20
10
60
{"##########",
 "#   #    #",
 "# @ X E  #",
 "#   #    #",
 "##########"}
Returns: 6
You take a pill as soon as possible, and still you have to wait 2 seconds before you can move towards the door.
2)
    
0
1
10
200
{"#########",
 "#@   X  #",
 "####### #",
 "#E   X  #",
 "#########"}
Returns: 14
3)
    
1
1
10
120
{"#############",
 "#   #####   #",
 "# @ XXXXX E #",
 "#   #####   #",
 "#############"}
Returns: -1
4)
    
1
1
10
120
{"#########",
 "#XX@XXXE#",
 "# ##### #",
 "#       #",
 "#########"}
Returns: 12

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9810&pm=5904

Writer:

esteban

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Search