TheAirTripDivTwo
SRM 479 · 2009-11-12 · by Vasyl[alphacom]
SRM 479 · 2009-11-12 · by Vasyl[alphacom] · Graph Theory, Simple Search, Iteration
Problem Statement
Problem Statement
John and Brus have their own airplane. They are going to take several consecutive flights.
The i-th element of flights is the number of liters of fuel needed for the i-th flight.
The flights can be performed only in the same order as they are described in flights.
Initially there are fuel liters of fuel in the airplane. In order to perform a flight, the amount of fuel in the airplane must be at least as much as the amount of fuel needed for this flight. Return the maximum number of flights they will be able to make without a refuel.
Initially there are fuel liters of fuel in the airplane. In order to perform a flight, the amount of fuel in the airplane must be at least as much as the amount of fuel needed for this flight. Return the maximum number of flights they will be able to make without a refuel.
Constraints
- flights will contain between 1 and 47 elements, inclusive.
- Each element of flights will be between 1 and 1000, inclusive.
- fuel will be between 1 and 1000, inclusive.
Examples
0)
{1, 2, 3, 4, 5, 6, 7}
10
Returns: 4
Exactly 10 liters of fuel are required to perform the first four flights.
1)
{7, 6, 5, 4, 3, 2, 1}
10
Returns: 1
These are the same flights as in the previous example, but in different order.
2)
{1}
1000
Returns: 1
A single flight here.
3)
{8, 7, 7, 1, 5, 7, 9}
21
Returns: 2
4)
{1, 3, 3, 6, 6, 9, 9}
30
Returns: 6
Submissions are judged against all 87 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TheAirTripDivTwo with a public method int find(vector<int> flights, int fuel) · 87 test cases · 2 s / 256 MB per case