Statistics

Problem Statement for "GreedyGovernment"

Problem Statement

You live in a town which is divided into sectors, numbered 0 through N-1. In addition, some sectors are connected by roads. You must pay a toll to move between sectors. The government of your town is rather greedy, and it has decided to increase the toll along one of these roads. In particular, they are going to increase the toll along a road by tollHike dollars, such that the average cost of travelling from sector 0 to sector N-1 is maximized. This average cost is determined as the average cost over all distinct valid paths from sector 0 to sector N-1. Two paths from sector 0 to sector N-1 are distinct if they either visit a different number of sectors or visit sectors in a different order. A path is valid if it does not take you through any sector more than once while travelling from sector 0 to N-1.

Create a class GreedyGovernment which contains a method maxAverageCost. You will be given a String[] tolls and an int tollHike as arguments. The j'th character in the i'th element of tolls indicates the toll to travel between sectors i and j. If the j'th character in the i'th element of tolls is an 'X', then it is not possible to travel from sector i to sector j (although you may still be able to travel from sector j to sector i). If there is no way to travel from sector 0 to sector N-1, your method should return 0. Otherwise, the method should return a double corresponding to the maximum average cost that the government can expect.

Definition

Class:
GreedyGovernment
Method:
maxAverageCost
Parameters:
String[], int
Returns:
double
Method signature:
double maxAverageCost(String[] tolls, int tollHike)
(be sure your method is public)

Notes

  • Your return value must have an absolute or relative error less than 1e-9.

Constraints

  • tolls will contain between 2 and 10 elements, inclusive.
  • Each element of tolls will contain the same number of characters as the number of elements in tolls.
  • Each element of tolls will contain only the characters '1'-'9', inclusive, or the character 'X'.
  • The i'th character of the i'th element of tolls will be 'X' for all i.
  • tollHike will be between 1 and 100, inclusive.

Examples

  1. {"X324", "XXX2", "12X5", "991X"}

    9

    Returns: 10.0

    Note that there are 4 ways to travel from sector 0 to sector 3: sector 0 --> sector 3 sector 0 --> sector 1 --> sector 3 sector 0 --> sector 2 --> sector 3 sector 0 --> sector 2 --> sector 1 --> sector 3 Any other path from sector 0 to sector 3 (for example, sector 0 --> sector 2 --> sector 0 --> sector 3) visits a sector more than once, which is not allowed in your town.

  2. {"X324", "5X22", "12X5", "991X"}

    57

    Returns: 29.2

  3. {"X11", "2X1", "37X"}

    76

    Returns: 39.5

  4. {"X32X", "XXXX", "XXXX", "XXXX"}

    99

    Returns: 0.0

    There is no way to travel from sector 0 to sector 3.

  5. {"X561324534", "1X82346123", "98X1641451", "982X412355", "9812X31235", "82359X8371", "283659X112", "9832465X12", "98246892X1", "982468926X"}

    17

    Returns: 33.75003877701846

  6. {"X9791", "5X5X4", "84X95", "554X3", "9215X"}

    29

    Returns: 28.307692307692307

  7. {"XX49", "9X99", "47X6", "511X"}

    77

    Returns: 64.33333333333333

  8. {"X45864X71", "4X9916233", "58X357392", "351X3X613", "1687XX235", "16495X195", "737387XX2", "285516XX8", "22978484X"}

    68

    Returns: 48.42628722311867

  9. {"XX745", "3X373", "X9X23", "154X4", "7349X"}

    76

    Returns: 48.81818181818182

  10. {"XX7X45355", "5X1362732", "57X982581", "835X53753", "1355X3599", "75281X287", "479136X51", "1927285XX", "X5852753X"}

    67

    Returns: 49.19266595920293

  11. {"X482X3892", "7X4756585", "27XX291X9", "576X625X2", "64X7X5755", "55978X445", "334343X34", "5521543X5", "324575XXX"}

    34

    Returns: 41.6393372982158

  12. {"X49X1586", "XX582836", "59XX5456", "216X9455", "3X65X243", "42241X51", "X3X146X2", "9465892X"}

    7

    Returns: 27.956398104265404

  13. {"X16889", "XX54X8", "29X496", "755X19", "5482X5", "68292X"}

    66

    Returns: 42.407407407407405

  14. {"X8X71218", "7XX59X22", "86X32358", "291X3987", "5713X138", "77X45X35", "785539X5", "34X3187X"}

    33

    Returns: 34.56659619450317

  15. {"X3355991", "1X3475X4", "33X47833", "745X8967", "56X7X894", "5X891X55", "553432X7", "4998X9XX"}

    32

    Returns: 37.762199845081334

  16. {"X6347", "1X585", "33X57", "X77X8", "4136X"}

    80

    Returns: 42.3125

  17. {"X833939X", "7X5X44XX", "97X69582", "221X44XX", "3799X644", "92467X5X", "8X2259X8", "1953828X"}

    87

    Returns: 57.67484662576687

  18. {"X71X95X6", "4X553942", "66X366X3", "384X6363", "2289X116", "6998XXX4", "577776X2", "9222X58X"}

    35

    Returns: 41.4024064171123

  19. {"XX79", "XXX2", "2XX3", "95XX"}

    79

    Returns: 49.0

  20. {"XXX2649", "5X34494", "32X9XX8", "475X28X", "9359XX4", "25917XX", "124116X"}

    14

    Returns: 30.933333333333334

  21. {"X1", "4X"}

    60

    Returns: 61.0

  22. {"X2X89", "9X72X", "X5X98", "627X8", "2974X"}

    98

    Returns: 67.375

  23. {"X1X665", "XXX257", "78X415", "557X19", "84X3X6", "729X5X"}

    57

    Returns: 41.44444444444444

  24. {"X568474", "7X3X126", "54X1196", "X76X975", "3886X55", "X5658X8", "657355X"}

    44

    Returns: 37.66064981949459

  25. {"XX698855", "5X111547", "75X76535", "68XX4336", "7625X559", "X6787X59", "41765XX8", "9939686X"}

    17

    Returns: 36.831042845594176

  26. {"X7X3", "7X63", "X3X3", "55XX"}

    55

    Returns: 46.333333333333336

  27. {"XXX8", "2X73", "5XX3", "477X"}

    23

    Returns: 31.0

  28. {"X625", "5X86", "45X8", "335X"}

    38

    Returns: 27.6

  29. {"X5325555", "9X492845", "4XXX3764", "873X9766", "315XX625", "5453XX29", "358972XX", "X928252X"}

    31

    Returns: 37.91270718232044

  30. {"X8392583", "1XX51698", "56X2527X", "X53X1595", "8756X19X", "8546XX62", "465868X7", "X484291X"}

    32

    Returns: 39.88704965920156

  31. {"X54934693", "4X3366915", "83X546816", "793X54628", "8715X4232", "89968X834", "866982X69", "1715248X3", "15759958X"}

    87

    Returns: 48.784963503649635

  32. {"X2656", "2X996", "87X82", "785X3", "8455X"}

    85

    Returns: 43.0625

  33. {"X998576", "3X31239", "62X8525", "283X122", "5149X35", "76646X7", "296948X"}

    39

    Returns: 32.828220858895705

  34. {"X3462", "2X669", "65X24", "157X5", "8784X"}

    97

    Returns: 45.9375

  35. {"X34", "8X7", "85X"}

    81

    Returns: 47.5

  36. {"X2976445", "3X592614", "51X15876", "382X9299", "7262X627", "85345X21", "994573X7", "9865985X"}

    30

    Returns: 34.66581502299438

  37. {"X86", "5X8", "43X"}

    69

    Returns: 45.5

  38. {"X57978", "5X4592", "11X454", "174X46", "2179X2", "58159X"}

    36

    Returns: 29.476923076923075

  39. {"X978331", "7X26297", "82X6287", "724X678", "2557X42", "52567X6", "616563X"}

    94

    Returns: 45.28834355828221

  40. {"X29143567", "5X8532555", "88X635519", "185X54266", "1529X1522", "25275X357", "845178X13", "5984155X3", "59155997X"}

    22

    Returns: 35.64313868613139

  41. {"X62", "8X9", "37X"}

    33

    Returns: 25.0

  42. {"X9289547", "7X145758", "82X27566", "583X7765", "4678X527", "55435X18", "199397X5", "8328474X"}

    33

    Returns: 39.23300970873787

  43. {"X7655", "7X462", "87X83", "741X6", "1554X"}

    47

    Returns: 29.6875

  44. {"X38586375", "3X7577778", "28X222745", "921X26876", "3811X5564", "94125X921", "157564X99", "5685728X1", "99313558X"}

    83

    Returns: 47.666131386861316

  45. {"X523268", "6X72375", "11X4285", "779X655", "5425X75", "18687X8", "749375X"}

    75

    Returns: 40.38343558282209

  46. {"X3XX5XX235", "6X22XX86X6", "17X3733X6X", "5XXX921X57", "233XX2X295", "46X7XXX28X", "68X4X4X16X", "XX87XXXXX6", "4X1X8823X9", "X854X5793X"}

    23

    Returns: 44.62383770076078

  47. {"XX9X2X65X3", "XXX554X69X", "X6X55294X4", "X45X67X295", "85X6X549X8", "75XX3X9821", "X44XXXXX71", "97685XXX5X", "XX92558XX7", "X95XX8X42X"}

    14

    Returns: 45.600969305331176

  48. {"X57XX6XX51", "XX475X76X5", "24X44XX575", "5X7X885XX9", "5553X15297", "X5763X6X26", "5X7135XXX8", "21X639XX9X", "XX9X5957X5", "9XX911247X"}

    43

    Returns: 55.56570987257047

  49. {"XXX6758838", "3XX2X9X553", "81XX29X56X", "9X6XX97XX4", "X63XX274X6", "1X9X3X585X", "15X94XX52X", "X1X9199X69", "X22X2451X5", "96X779X65X"}

    5

    Returns: 40.406764027671024

  50. {"XX5X7X156X", "XX8X421959", "X7X1575X57", "981XXX7X68", "XXX1XX23XX", "1X3X9X8785", "4X5365X83X", "X8389X5X22", "6X11X455X4", "553574X58X"}

    21

    Returns: 44.390405904059044

  51. {"XXXX3XX478", "2XX981X7X7", "95X455691X", "X33X6X4282", "6X41X55247", "639X1XX572", "1515X2XX11", "X25XX4XXX4", "568915X2X7", "5X98X5XX3X"}

    11

    Returns: 38.9973474801061

  52. {"X52XX928X8", "5XX1X68XXX", "X5X5XX9516", "X28XXX5X37", "X5X1X13651", "73556X397X", "5XXX33XX81", "43X592XXXX", "512X5X94X5", "554XXX922X"}

    91

    Returns: 59.286014169509315

  53. {"X55X29X599", "4X2XXX8X51", "76X8XXX5X2", "392X4X4X26", "791XX758X7", "XXX4XX9X68", "5XX41XXX35", "5175X52X55", "51X55X9XX5", "92XXXX95XX"}

    55

    Returns: 53.45491932932616

  54. {"XX9XX5659X", "7XX975X5XX", "93X49858X5", "X5XX67581X", "8645X3X624", "454X9XX718", "656416XX43", "5X465XXXX2", "XX54235XX4", "5X7X17X17X"}

    95

    Returns: 66.7055124431362

  55. {"XX483X79X5", "7X1X152996", "52XX88X753", "95XX624762", "2512XX3X45", "9X864XX916", "613765X765", "X891877X28", "2534X444X3", "929X54739X"}

    96

    Returns: 61.031095123900876

  56. {"X198514486", "5X38531767", "32X5595353", "171X615445", "8141X22716", "12542X8555", "137219X554", "5211815X21", "23474564X4", "572627591X"}

    97

    Returns: 46.0356474849682

  57. {"X543212677", "4X53452576", "51X3755522", "232X738512", "9956X65484", "31316X1956", "149379X453", "2738683X31", "78159547X5", "879225196X"}

    15

    Returns: 38.714354796032886

  58. {"X973725637", "5X58571757", "18X5342554", "585X461632", "7437X72445", "95425X1865", "846589X523", "3875141X81", "65319996X7", "331348853X"}

    19

    Returns: 41.87504676052226

  59. {"X664111745", "7X56923248", "77X2569869", "281X217778", "7245X41253", "99971X3987", "184839X415", "9428429X62", "99856795X8", "555123533X"}

    80

    Returns: 51.82138849098092

  60. {"X525986369", "7X28585395", "16X9989957", "455X771355", "7912X58947", "35468X8758", "348585X245", "2522753X15", "55469213X4", "595835321X"}

    95

    Returns: 55.267826023485185

  61. {"X255739723", "3X51253585", "99X4556585", "756X243386", "5762X95315", "52324X2275", "839561X182", "3951159X39", "56586283X3", "154535382X"}

    9

    Returns: 39.089296630505196

  62. {"X522684593", "8X27978128", "56X5532665", "487X955124", "2635X56599", "38181X4532", "513571X813", "3555879X75", "56478675X2", "456551598X"}

    4

    Returns: 41.44645578051295

  63. {"X714517452", "6X77439185", "88X8348856", "596X321582", "6358X79583", "71725X3529", "879255X445", "6725561X42", "85555827X5", "655899451X"}

    55

    Returns: 46.821397614985266

  64. {"X831915326", "5X15468442", "59X3237719", "125X576899", "1863X56974", "58362X7695", "781357X728", "9897859X26", "27246523X7", "652172715X"}

    67

    Returns: 50.87498289249186

  65. {"X274253172", "6X55475885", "36X6474639", "554X145141", "9454X92951", "57611X5466", "576528X418", "8255269X25", "86946234X9", "577875988X"}

    49

    Returns: 44.214249869982936

  66. {"X2XX", "XX44", "X1XX", "XXXX"}

    4

    Returns: 10.0

  67. {"X23X", "XX44", "X1XX", "111X"}

    4

    Returns: 11.0

  68. {"X111111111", "1X11111111", "11X1111111", "111X111111", "1111X11111", "11111X1111", "111111X111", "1111111X11", "11111111X1", "111111111X"}

    1

    Returns: 8.1250079835038

  69. {"X324", "5X22", "12X5", "991X" }

    57

    Returns: 29.2

  70. {"X123456789", "1X23456789", "11X3456789", "112X456789", "1123X56789", "11234X6789", "112345X789", "1123456X89", "11234567X9", "112345678X" }

    100

    Returns: 52.999927007965255

  71. {"X324", "5X22", "12X5", "991X" }

    82

    Returns: 39.2

  72. {"X999999999", "9X99999999", "99X9999999", "999X999999", "9999X99999", "99999X9999", "999999X999", "9999999X99", "99999999X9", "999999999X" }

    100

    Returns: 84.4999680659848

  73. {"X11", "2X1", "37X" }

    76

    Returns: 39.5

  74. {"X32445", "5X2223", "12X589", "991X11", "6321X5", "86942X" }

    98

    Returns: 38.261538461538464

  75. {"X123456789", "1X23456789", "12X3456789", "123X456789", "1234X56789", "12345X6789", "123456X789", "1234567X89", "12345678X9", "123456789X" }

    98

    Returns: 55.749938412970685

  76. {"X123456789", "9X12345678", "94X2345678", "192X345678", "9123X45678", "91234X5678", "912345X678", "9123444X67", "91234333X7", "912345678X" }

    10

    Returns: 37.28574556801489

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: