TopCoder problem "LateForConcert" used in SRM 366 (Division I Level Three)



Problem Statement

    

You are a guitar player and you are giving a concert tonight. Unfortunately, you are running a bit late, and you still need to travel across town to get to the concert hall. You will drive as fast as possible (above the speed limit) and you are willing to drive through red lights at the risk of getting fined. However, you do not want to arrive early because you don't like the artist playing before you. Your goal is to get to the concert hall exactly on time.



The city is a rectangular grid of squares described by the String[] cityMap. The j-th character of the i-th element of cityMap is the square at row i, column j. Each square is one of the following:

  • X: A house. You cannot enter this square.
  • .: A safe road. You can drive here safely without ever getting a speeding ticket.
  • Y: Your starting location. After time = 0, this becomes a safe road.
  • C: The concert hall. As soon as you enter this square, you are at your final destination and you cannot leave.
  • T: A traffic light. See below for details.
  • S: A speed trap. You will get fined speedingTicket dollars every time you enter a square containing a speed trap.

You are given an int timeLeft, the number of seconds you have left until your concert starts. At time 0, you are at your starting location. At the speed you are driving, it takes you exactly one second to move to any of the 4 adjacent squares. At each second, you must move to an adjacent square unless you are at a traffic light. You are never allowed to directly go back to the immediately previous square of your path. If you are currently at a traffic light, you have two options: make a move during the upcoming second (like you would from any other square), or stay at the traffic light for exactly one second before making your next move. If you stay at the traffic light for one second, you are guaranteed to not get fined. Otherwise, you have a 70% chance of getting fined redLight dollars.



Determine the route that will take you to the concert hall in exactly timeLeft seconds. If there are multiple such routes, choose the one that minimizes your total expected fine. Return your total expected fine, or -1 if there is no way to get to the concert hall exactly on time.

 

Definition

    
Class:LateForConcert
Method:bestRoute
Parameters:String[], int, double, double
Returns:double
Method signature:double bestRoute(String[] cityMap, int timeLeft, double speedingTicket, double redLight)
(be sure your method is public)
    
 

Notes

-The returned value must be accurate to within a relative or absolute value of 1E-9.
 

Constraints

-cityMap will contain between 1 and 50 elements, inclusive.
-Each element of cityMap will contain between 1 and 50 characters, inclusive.
-Each element of cityMap will contain the same number of characters.
-Each character of cityMap will be one of the following: 'X', '.', 'Y', 'C', 'T' or 'S'.
-Exactly one character in cityMap will be 'Y'.
-Exactly one character in cityMap will be 'C'.
-timeLeft will be between 1 and 100, inclusive.
-speedingTicket will be between 1.0 and 1000.0, inclusive.
-redLight will be between 1.0 and 1000.0, inclusive.
 

Examples

0)
    
{"XXXXXXXX",
 "XY...S.X",
 "XXXXXX.X",
 "C..S.TT."}
14
60
93
Returns: 185.1
If you wait for one of the traffic lights, it will take 14 seconds, and your expected total fine will be speedingTicket + speedingTicket + 0.7 * redLight.
1)
    
{"XX..XX",
 "Y....C"}
9
52
874
Returns: 0.0
You can use the 2x2 square to spend your time so you don't have to see the other artist.
2)
    
{"YTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTC"}
67
123.4
42.192
Returns: 886.032
3)
    
{"C.......",
 "SXXSXXX.",
 "TSSTY..."}
12
1.23456789
123.456789
Returns: 0.0
The shortest route is not always the best!
4)
    
{"Y..",
 "...",
 "..C"}
3
1.0
1.0
Returns: -1.0
The concert hall is too far, so you don't have enough time to reach it.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10781&pm=7827

Writer:

jthread

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Graph Theory