Farmville
SRM 676 · 2015-11-03 · by lg5293
Problem Statement
This problem has a non-standard time limit: 5 seconds.
Farmer John recently found out about a popular online farming game.
There are n types of plants in the game. The types are numbered 0 through n-1.
Growing a plant consists of four steps:
- Farmer John must acquire a seed of the plant. This is described below in more detail.
- He must plant the seed. He can do this instantaneously. He can have arbitrarily many plants growing at the same time.
- The seed of plant i will grow for time[i] seconds until it becomes a fully developed plant.
- Farmer John will harvest the plant. He can do this instantaneously.
Some plants have prerequisites.
These are described by the
Note that a single grown plant can be used to satisfy multiple prerequisites. For example, if both plant 0 and plant 1 require John to grow plant 2 first, he only has to grow a single plant of type 2 in order to "unlock" both plant 0 and plant 1.
There is one final complication: Farmer John has budget coins. He can spend these coins to make his plants grow faster. For each i, Farmer John may pay cost[i] coins to reduce time[i] by 1. Farmer John may pay for the same plant multiple times, each time decreasing its growing time by 1. Obviously, the growing time cannot be reduced below 0.
You are given the
Constraints
- n will be between 2 and 50, inclusive.
- s will have exactly n elements.
- Each element of s will contain exactly n characters.
- Each character of s[i] will either be '0' or '1'.
- There will only be at most 50 '1' characters among all characters in all elements of s.
- It is guaranteed that it is possible to grow at least one plant of each type given the constraints in s.
- time will have exactly n elements.
- Each element of time will be between 1 and 25, inclusive.
- cost will have exactly n elements.
- Each element of cost will be between 1 and 10^9, inclusive.
- budget will be between 0 and 10^9, inclusive.
{"000",
"000",
"000"}
{25,15,10}
{1,2,3}
50
Returns: 6
There are no prerequisites. Hence, Farmer John will acquire all three seeds at time 0 and he will plant them all simultaneously. If he didn't spend any coins, the process would be over at time 25 when the plant of type 0 finally becomes fully developed. He can improve that time by spending his 50 coins. One optimal solution looks as follows: He will spend 19 coins on plant 0, decreasing its growing time from 25 to 25 - 19 = 6. He will spend 18 coins on plant 1. As cost[1]=2, every 2 coins decrease the time by 1. Hence, plant 1 will now grow in 15 - (18/2) = 15 - 9 = 6 units of time. He will spend 12 coins on plant 2. These will decrease its growing time by 12/3 = 4, which means it drops from 10 to 10 - 4 = 6. He will have 1 unused coin.
{"0000",
"1000",
"0100",
"0010"}
{25,25,25,25}
{100,200,300,400}
2800
Returns: 74
In this test case Farmer John must grow his plants sequentially in the order 0,1,2,3. If he didn't pay anything, this would take 25 + 25 + 25 + 25 = 100 units of time. One optimal solution is to spend 2500 coins on the plant 0 (making it grow in zero time) and the remaining 300 coins on plant 2 (decreasing its growing time by 1). Thus, in this solution the total growing time is 0 + 25 + 24 + 25 = 74.
{"01110",
"00010",
"00000",
"00000",
"10000"}
{25,10,23,12,5}
{123,456,789,1011,1213}
1000000000
Returns: 0
{"00",
"00"}
{25,25}
{1000000000,1000000000}
1000000000
Returns: 25
{"0000000000000000",
"1000000000000000",
"1000000000000000",
"0100000000000000",
"0110000000000000",
"0010000000000000",
"0001000000000000",
"0001100000000000",
"0000110000000000",
"0000010000000000",
"0000001100000000",
"0000000110000000",
"0000000011000000",
"0000000000110000",
"0000000000011000",
"0000000000000110"}
{24,25,23,25,23,24,25,24,23,22,25,24,23,25,23,25}
{82912,129482,235934,3294812,523942,460492,349281,592384,
109248,2305923,340945,2304934,582396,548935,767872,423981}
87654321
Returns: 49
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Farmville with a public method int minTime(vector<string> s, vector<int> time, vector<int> cost, int budget) · 65 test cases · 2 s / 256 MB per case