FarmvilleDiv2
SRM 676 · 2015-11-03 · by lg5293
Problem Statement
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. At the beginning of the game, Farmer John is given one seed of each plant type.
There is a single plot of land. At any time the plot can only contain at most one plant. Whenever the plot is empty, Farmer John can plant one of the seeds. Once a seed of type i is planted, it takes time[i] seconds until it grows into a fully developed plant. When that happens, Farmer John will harvest the plant and the plot will become empty again. Planting a seed and harvesting a plant happens instanteously.
Farmer John also 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
Notes
- The value of n is not given as a separate argument. Instead, you can determine it as the number of elements in time.
Constraints
- n will be between 1 and 50, inclusive.
- time,cost will have exactly n elements.
- Each element of time,cost will be between 1 and 100, inclusive.
- budget will be between 1 and 5,000, inclusive.
{100}
{1}
26
Returns: 74
In this case, we have a single plant that takes 100 seconds to grow. We can reduce the time it takes to grow by 1 second at a cost of 1 coin. Since we have 26 coins, we can use all our coins to reduce the time it takes the plant to grow to only 74 seconds.
{100}
{1}
101
Returns: 0
{2,1}
{1,1}
3
Returns: 0
Here we have two plants. Without payments, plant 0 will grow in 2 seconds and plant 1 will grow in 1 second. We have a budget of 3 coins. We can pay 1+1 to decrease the growing time of plant 0 from 2 to 0. We can then pay 1 to decrease the growing time of plant 1 from 1 to 0.
{1,2,3,4,5}
{5,4,3,2,1}
15
Returns: 6
{100,100,100,100,100,100,100,100,100,100}
{2,4,6,8,10,1,3,5,7,9}
5000
Returns: 50
Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FarmvilleDiv2 with a public method int minTime(vector<int> time, vector<int> cost, int budget) · 77 test cases · 2 s / 256 MB per case