Connection Status:
Competition Arena > LateForConcert

LateForConcert

SRM 366 · 2007-09-18 · by jthread

SRM 366 · 2007-09-18 · by jthread · Graph Theory
Class Name: LateForConcert
Return Type: double
Method Name: bestRoute
Arg Types: (vector<string>, int, double, double)
Problem Statement

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.

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)
{"SSXTTXS",
 "TSS..T.",
 "TSX..CS",
 "X..X.SX",
 "SXYST.S"}
8
902.9244188898721
657.7809919381947
Returns: 1363.3711132466083
3)
{"YTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTC"}
67
123.4
42.192
Returns: 886.032
4)
{"C.......",
 "SXXSXXX.",
 "TSSTY..."}
12
1.23456789
123.456789
Returns: 0.0

The shortest route is not always the best!

39)
{"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.

Submissions are judged against all 72 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LateForConcert with a public method double bestRoute(vector<string> cityMap, int timeLeft, double speedingTicket, double redLight) · 72 test cases · 2 s / 256 MB per case

Submitting as anonymous