PowerPlants

SRM 364 · 2007-09-04 · by connect4

SRM 364 · 2007-09-04 · by connect4 · Dynamic Programming, Search

Show categories

Class Name: PowerPlants

Return Type: int

Method Name: minCost

Arg Types: (vector<string>, string, int)

Problem Statement

Our hero, Homer, has just woken to a horrible discovery! While sleeping at work, several of the power plants in the state have lost power. Even worse, his boss is on the way to his office, and if he doesn't have the situation fixed in time, he'll be fired. He's called you, desperately asking for help, and you've agreed to help him figure things out.

Homer has given you connectionCost, in which the j-th character of the i-th element indicates the cost to restart power plant j using power plant i; a digit ('0'-'9') stands for a cost of 0-9, while an uppercase letter ('A'-'Z') stands for a cost of 10-35. Homer has also given you the plantList, in which the i-th character indicates whether the i-th plant is still working after the power outage; a 'Y' indicates that it has power, otherwise, it is an 'N'. A plant can only be used to power another plant if it currently has power. Finally, he gives you numPlants, the minimum number of plants that need to be powered to save Homer's job. You need to return the minimum cost needed to power at least numPlants plants.

Constraints

connectionCost will contain exactly N elements, where N is between 1 and 16, inclusive.
Each element of connectionCost will contain exactly N characters.
Each character of connectionCost will be a digit ('0'-'9') or uppercase letter ('A'-'Z').
plantList will contain exactly N characters.
Each character of plantList will be 'Y' or 'N'.
At least one character of plantList will be 'Y'.
numPlants will be between 0 and N, inclusive.

Examples

{"024",
 "203",
 "430"}
"YNN"
3
Returns: 5

The cheapest way is to restart plant 1 using plant 0. Once plant 1 is active, you can then use it to restart plant 2.

{"0AB",
 "A0C",
 "CD0"}
"YNN"
3
Returns: 21

Here we can use plant 0 to restart both of the others.

{"1ABCD",
 "35HF8",
 "FDM31",
 "AME93",
 "01390"}
"NYNNN"
5
Returns: 14

{"012",
 "123",
 "234"}
"NNY"
2
Returns: 2

{"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAA"}
"NNNNYNNNNNNNNNNN"
16
Returns: 150

37)

{"01","20"}
"YN"
2
Returns: 1

The cost to restart plant 0 using plant 1 may differ from the cost of restarting plant 1 using plant 0.

39)

{"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ",
"ZZZZZZZZZZZZZZZZ"}
"NNNNNNNNNNNNNNNY"
16
Returns: 525

Maximum possible return.

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

Coding Area

Language: C++17 · define a public class PowerPlants with a public method int minCost(vector<string> connectionCost, string plantList, int numPlants) · 80 test cases · 2 s / 256 MB per case