CuttingGrass
SRM 517 · 2011-05-25 · by rng_58
Problem Statement
At time 0, the height of the i-th grass blade is init[i]. At each positive integer time t, the following activities happen (in the specified relative order):
1. First, for each i, 0 &le i < N, the i-th grass blade becomes higher by grow[i].
2. Then, Ciel chooses a single grass blade and cuts it. The height of this grass blade becomes zero.
3. Finally, Ciel calculates the sum of heights of all grass blades. If it is at most H, then she considers her goal achieved.
Return the earliest possible time she can achieve her goal. If the sum of heights of all grass blades doesn't exceed H at time 0, return 0. If it's impossible to achieve the goal, return -1.
Constraints
- init will contain between 1 and 50 elements, inclusive.
- init and grow will contain the same number of elements.
- Each element of init will be between 0 and 100,000, inclusive.
- Each element of grow will be between 1 and 100,000, inclusive.
- H will be between 0 and 1,000,000, inclusive.
{5, 8, 58}
{2, 1, 1}
16
Returns: 1
At time 1: The heights of grass blades 0, 1, 2 become 7, 9, 59, respectively. Suppose that Ciel cuts grass blade 2. The height of grass blade 2 becomes zero. The sum of heights of all grass blades is 7 + 9 + 0 = 16, so she achieves her goal.
{5, 8}
{2, 1}
58
Returns: 0
At time 0, the sum of heights of all grass blades is 13 and doesn't exceed H.
{5, 8}
{2, 1}
0
Returns: -1
It's impossible to achieve the goal.
{5, 1, 6, 5, 8, 4, 7}
{2, 1, 1, 1, 4, 3, 2}
33
Returns: 5
One of the optimal strategies is to cut grass blade 2, 0, 6, 5, 4 (0-indexed) at time 1, 2, 3, 4, 5 respectively.
{49, 13, 62, 95, 69, 75, 62, 96, 97, 22, 69, 69, 52}
{7, 2, 4, 3, 6, 5, 7, 6, 5, 4, 7, 7, 4}
517
Returns: 8
Submissions are judged against all 64 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CuttingGrass with a public method int theMin(vector<int> init, vector<int> grow, int H) · 64 test cases · 2 s / 256 MB per case