JOIN
Get Time

   Problem Statement  

 Problem Statement for AlbertoTheAviator

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 int[]s of the same length: duration and refuel. For each valid i:



  • 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.

 

Definition

    
Class:AlbertoTheAviator
Method:MaximumFlights
Parameters:int, int[], int[]
Returns:int
Method signature:int MaximumFlights(int F, int[] duration, int[] refuel)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
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.
1)
    
10
{8, 4}
{0, 2}
Returns: 2
2)
    
12
{4, 8, 2, 1}
{2, 0, 0, 0}
Returns: 3
3)
    
9
{4, 6}
{0, 1}
Returns: 2
4)
    
100
{101}
{100}
Returns: 0
There is only one mission. Alberto does not have enough fuel to take it. The answer is 0.
5)
    
1947
{2407, 2979, 1269, 2401, 3227, 2230, 3991, 2133, 3338, 356, 2535, 3859, 3267, 365}
{2406, 793, 905, 2400, 1789, 2229, 1378, 2132, 1815, 355, 72, 3858, 3266, 364}
Returns: 3

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 610 Round 1 - Division I, Level Two