AlbertoTheAviator
SRM 610 · 2013-12-22 · by rng_58
Problem Statement
Alberto is an aviation pioneer. He pilots an airplane called "14-bis". Initially, there are F units of fuel in the fuel tank of his airplane.
There are some flight missions Alberto may take.
The missions all start and end in the same location, and he may do them in any order.
However, he can only do each mission at most once.
You are given two
- duration[i] is the amount of fuel consumed while running mission i
- After Alberto completes mission i and gets paid, he will buy refuel[i] units of fuel. This amount will always be strictly smaller than the amount consumed during the mission.
Alberto can only choose a mission if he has enough fuel for it. That is, at the beginning of the mission his fuel tank must have at least duration[i] units of fuel.
Compute and return the maximum number of missions Alberto can take.
Constraints
- F will be between 1 and 5,000 inclusive.
- duration and refuel will have between 1 and 50 elements, inclusive.
- Each element of duration will be between 1 and 5,000, inclusive.
- Each element of refuel will be between 0 and 5,000, inclusive.
- For each i, refuel[i] will be strictly smaller than duration[i].
- duration and refuel will contain the same number of elements.
10
{10}
{0}
Returns: 1
There is only one mission. Alberto has enough fuel to take it, so the optimal solution is to take it.
10
{8, 4}
{0, 2}
Returns: 2
12
{4, 8, 2, 1}
{2, 0, 0, 0}
Returns: 3
9
{4, 6}
{0, 1}
Returns: 2
100
{101}
{100}
Returns: 0
There is only one mission. Alberto does not have enough fuel to take it. The answer is 0.
Submissions are judged against all 152 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AlbertoTheAviator with a public method int MaximumFlights(int F, vector<int> duration, vector<int> refuel) · 152 test cases · 2 s / 256 MB per case