Connection Status:
Competition Arena > GreedyGovernment

GreedyGovernment

SRM 275 · 2005-11-30 · by NeverMore

SRM 275 · 2005-11-30 · by NeverMore · Graph Theory, Recursion, Search, String Manipulation
Class Name: GreedyGovernment
Return Type: double
Method Name: maxAverageCost
Arg Types: (vector<string>, int)
Problem Statement

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.

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

1)
{"X324", "5X22", "12X5", "991X"}
57
Returns: 29.2
2)
{"X11", "2X1", "37X"}
76
Returns: 39.5
3)
{"X32X", "XXXX", "XXXX", "XXXX"}
99
Returns: 0.0

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

4)
{"X561324534", "1X82346123", "98X1641451", "982X412355", "9812X31235", "82359X8371", "283659X112", "9832465X12", "98246892X1", "982468926X"}
17
Returns: 33.75003877701846

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

Coding Area

Language: C++17 · define a public class GreedyGovernment with a public method double maxAverageCost(vector<string> tolls, int tollHike) · 76 test cases · 2 s / 256 MB per case

Submitting as anonymous