Statistics

Problem Statement for "CheapestFlights"

Problem Statement

Character j in element i (both 0-based) of prices gives the cost of a flight from location i to location j. Fortunately, the airline is having a special. Each time you arrive at a location k, all future flights to location k (from anywhere) become half price (no rounding). These savings build on each other. For example, if you arrive at location 2 twice, the next flight to location 2 is one quarter of the original price. Given startLocation and endLocation, the locations where you must start and end respectively, and num, the exact number of flights you must take, return the smallest possible total cost. You cannot take a flight from a location back to itself.

Definition

Class:
CheapestFlights
Method:
getLowest
Parameters:
String[], int, int, int
Returns:
double
Method signature:
double getLowest(String[] prices, int startLocation, int endLocation, int num)
(be sure your method is public)

Notes

  • You may revisit a location numerous times.
  • The returned value must be accurate to 1e-9 relative or absolute.

Constraints

  • prices will contain between 3 and 8 elements inclusive.
  • Each element of prices will contain N characters, where N is the number of elements in prices.
  • Each character in prices will be a digit ('0'-'9').
  • startLocation will be between 0 and N-1 inclusive, where N is the number of elements in prices.
  • endLocation will be between 0 and N-1 inclusive, where N is the number of elements in prices.
  • num will be between 2 and 8 inclusive.

Examples

  1. {"019", "909", "990" }

    0

    1

    2

    Returns: 18.0

    You must take 2 flights, so you go from location 0 to location 2, and then location 2 to location 1.

  2. {"099", "909", "990" }

    0

    1

    3

    Returns: 22.5

    Your path is: Location 0 -> Location 1 -> Location 0 -> Location 1 The respective costs are 9, 9, and 4.5.

  3. {"099", "909", "990" }

    0

    1

    7

    Returns: 32.625

  4. {"111", "111", "111" }

    1

    1

    8

    Returns: 3.75

  5. {"111", "111", "111" }

    1

    1

    7

    Returns: 4.5

  6. {"0135841", "0009080", "8508439", "4870309", "5152070", "1536202", "9364160"}

    0

    2

    3

    Returns: 4.0

  7. {"04241524", "40727827", "13058587", "90906627", "79910604", "07592085", "12462001", "21155670"}

    0

    3

    3

    Returns: 5.0

  8. {"0934316", "9052946", "0008846", "9610562", "5756015", "1965503", "7264940"}

    5

    1

    7

    Returns: 6.25

  9. {"006945", "003539", "140941", "229029", "053802", "778520"}

    4

    4

    7

    Returns: 3.0

  10. {"07013", "30649", "21016", "80306", "09820"}

    4

    0

    6

    Returns: 2.75

  11. {"04873260", "30570882", "60040818", "32905406", "42950074", "56277076", "07704303", "29238780"}

    2

    0

    6

    Returns: 1.0

  12. {"07435722", "40875379", "34042981", "81202903", "47480621", "77243038", "00250807", "22159640"}

    5

    1

    2

    Returns: 3.0

  13. {"0727124", "0094764", "2106593", "1080597", "3238004", "0082705", "8261590"}

    2

    1

    8

    Returns: 2.5

  14. {"0281552", "4095991", "4702394", "9000215", "9732083", "0853104", "5782070"}

    4

    3

    6

    Returns: 4.0

  15. {"01498", "30544", "11007", "23006", "04810"}

    1

    1

    5

    Returns: 5.0

  16. {"083533", "106854", "700370", "807053", "945109", "338710"}

    1

    4

    3

    Returns: 5.0

  17. {"06912", "10851", "62098", "97608", "39800"}

    2

    3

    5

    Returns: 7.0

  18. {"080872", "200060", "490833", "383050", "607306", "256540"}

    4

    3

    7

    Returns: 3.75

  19. {"055119", "205542", "320256", "412032", "456802", "333930"}

    0

    1

    3

    Returns: 5.0

  20. {"082115", "706445", "560911", "748096", "860307", "428940"}

    2

    4

    3

    Returns: 1.5

  21. {"03615749", "70905174", "47055001", "05706230", "70570071", "09330034", "82663909", "13786430"}

    0

    6

    8

    Returns: 4.875

  22. {"0491856", "1063964", "5304325", "7310188", "5094004", "8239104", "3278820"}

    2

    1

    3

    Returns: 3.0

  23. {"00702", "50435", "37057", "92307", "40460"}

    1

    4

    4

    Returns: 9.5

  24. {"013222", "403244", "110535", "353005", "333403", "000240"}

    4

    1

    8

    Returns: 4.75

  25. {"00301440", "30013241", "03030355", "53404412", "31410035", "43251035", "21205002", "25400540"}

    2

    5

    3

    Returns: 1.0

  26. {"0330051", "4025011", "4103250", "1500424", "2203032", "2030203", "1430410"}

    0

    1

    5

    Returns: 1.0

  27. {"00210", "50330", "22014", "23402", "31420"}

    2

    0

    7

    Returns: 4.25

  28. {"05502", "50312", "50044", "45005", "24050"}

    4

    0

    2

    Returns: 5.0

  29. {"05451", "00224", "15032", "02502", "00210"}

    2

    4

    6

    Returns: 2.75

  30. {"0440", "1003", "0503", "3020"}

    3

    3

    4

    Returns: 0.0

  31. {"0553005", "2000544", "4300244", "0240512", "2404025", "0444304", "1452500"}

    6

    1

    2

    Returns: 4.0

  32. {"051041", "403525", "320212", "034011", "022000", "250310"}

    3

    4

    7

    Returns: 1.0

  33. {"04525", "50104", "24013", "10103", "02530"}

    2

    3

    4

    Returns: 2.5

  34. {"0423", "4034", "4401", "2240"}

    1

    3

    8

    Returns: 8.375

  35. {"01344", "30133", "33033", "23404", "33320"}

    4

    3

    7

    Returns: 8.75

  36. {"04341421", "20241243", "23041422", "42201343", "13120341", "11443034", "31121403", "43323110"}

    3

    3

    8

    Returns: 5.625

  37. {"01412", "20414", "44013", "43403", "33430"}

    3

    2

    7

    Returns: 9.25

  38. {"04241133", "10214231", "21031113", "43201142", "23440133", "32413013", "32231403", "33341410"}

    6

    7

    7

    Returns: 6.25

  39. {"0441134", "1011441", "2404321", "3140434", "3242013", "2132402", "4223310"}

    4

    3

    3

    Returns: 3.0

  40. {"04314414", "40432121", "33033332", "42103411", "42430423", "43342034", "44432202", "24412320"}

    6

    6

    5

    Returns: 5.0

  41. {"03323", "40113", "22022", "31404", "14110"}

    1

    0

    2

    Returns: 3.0

  42. {"0443", "4021", "3101", "1140"}

    0

    1

    7

    Returns: 6.625

  43. {"03424", "10314", "42033", "12302", "32130"}

    4

    2

    2

    Returns: 5.0

  44. {"089786", "809969", "770989", "797098", "678806", "966960"}

    1

    4

    4

    Returns: 21.0

  45. {"08777779", "60877977", "66067669", "78608797", "66980986", "76998097", "88797807", "66888670"}

    7

    0

    2

    Returns: 12.0

  46. {"0876669", "8066876", "8606987", "9770699", "6899078", "6699806", "6678960"}

    6

    2

    7

    Returns: 22.75

  47. {"0769778", "7078898", "6907798", "7960996", "6878096", "9789709", "7888880"}

    4

    6

    5

    Returns: 22.5

  48. {"07988776", "60879989", "99067789", "67908696", "69860779", "67968088", "77699707", "98799790"}

    4

    1

    2

    Returns: 13.0

  49. {"078689", "808888", "960978", "896069", "698806", "886860"}

    4

    4

    2

    Returns: 12.0

  50. {"098998", "806996", "970776", "687069", "789706", "687990"}

    2

    1

    2

    Returns: 14.0

  51. {"078997", "709669", "860777", "779097", "699809", "769760"}

    3

    1

    8

    Returns: 26.125

  52. {"0969687", "7099896", "6807897", "6780876", "6678089", "7868806", "7978960"}

    1

    2

    7

    Returns: 24.75

  53. {"0788669", "6087777", "7906798", "7780799", "6688089", "6899706", "8796960"}

    3

    0

    2

    Returns: 13.0

  54. {"85586885","04364909","60950496","51732432","16904504","41669934","04524950","48688641"}

    4

    6

    8

    Returns: 3.5

  55. {"35332652","38195157","84706197","07100116","69489310","71921763","97298351","08640882"}

    7

    1

    8

    Returns: 4.5

  56. {"34989418","50735753","13340736","64276226","28887628","82080708","67517245","32878728"}

    1

    2

    8

    Returns: 7.0

  57. {"87269383","73415778","84173935","18366883","27716295","34794980","54129703","94257917"}

    3

    5

    8

    Returns: 9.25

  58. {"94703634","43393862","36892060","27913695","07006438","79701717","57653289","41484808"}

    0

    1

    7

    Returns: 4.5

  59. {"87827300","09419754","40627763","43789378","51880778","65036358","35172996","48429480"}

    0

    4

    7

    Returns: 6.0

  60. {"56288767","21306265","36413079","94306553","03854336","54564282","99195382","97886426"}

    6

    3

    8

    Returns: 5.5

  61. {"84951605","15571232","96971092","76568005","18468403","38936893","06264827","69470604"}

    7

    7

    8

    Returns: 3.75

  62. {"44754371","93472212","45432673","33899847","72364766","31272641","04373276","79363492"}

    0

    2

    7

    Returns: 9.0

  63. {"56166748","42000201","32913859","45033609","78586930","41910012","00696218","38952805"}

    0

    3

    8

    Returns: 2.0

  64. {"26355695","67481078","70507506","61773006","21665078","25164576","17349776","03686376"}

    0

    7

    8

    Returns: 9.5

  65. {"36439105","47489057","93573137","06235873","88103935","20877836","56911859","10932140"}

    3

    3

    8

    Returns: 1.5

  66. {"48535241","14205592","58023307","32219700","46548530","21595576","72416650","83672696"}

    1

    3

    7

    Returns: 0.875

  67. {"94663433","29552805","17196680","98637309","84569631","57712226","08334611","06010322"}

    4

    6

    8

    Returns: 2.75

  68. {"71104176","00808561","35733115","29169182","71351250","15505009","99501150","53594375"}

    0

    0

    8

    Returns: 1.875

  69. { "9099999", "0909999", "9090999", "9909099", "9990909", "9999090", "9999900" }

    0

    6

    6

    Returns: 0.0

  70. { "9199999", "1919999", "9191999", "9919199", "9991919", "9999191", "9999911" }

    0

    6

    6

    Returns: 6.0

  71. { "3033333", "0303333", "3030333", "3303133", "3331313", "3333131", "3333311" }

    0

    6

    6

    Returns: 3.0

  72. { "3033333", "0303333", "3031333", "3313133", "3331313", "3333131", "3333311" }

    0

    6

    6

    Returns: 3.0

  73. { "4044444", "0404444", "4041444", "4414144", "4441414", "4444141", "4444411" }

    0

    6

    6

    Returns: 4.0

  74. { "4044444", "0404444", "4041444", "4414144", "4441404", "4444041", "4444411" }

    0

    6

    6

    Returns: 3.0

  75. { "3133399", "1313333", "3131333", "3313133", "3331313", "9333130", "9333301" }

    0

    6

    6

    Returns: 4.0

  76. { "3133333", "1313333", "3131333", "3313133", "3331303", "3333030", "3333301" }

    0

    6

    6

    Returns: 3.0

  77. { "3133339", "1313333", "3131333", "3313133", "3331313", "3333130", "3333301" }

    6

    0

    6

    Returns: 3.0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: