|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.
|-||Your return value must have an absolute or relative error less than 1e-9.|
|-||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.|