TopCoder problem "GreedyGovernment" used in SRM 275 (Division II Level Three)



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

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.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8072&pm=5910

Writer:

NeverMore

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Graph Theory, Recursion, Search, String Manipulation