TopCoder problem "StrengthOrIntellect" used in SRM 424 (Division I Level Two)



Problem Statement

    Your character in a game has two properties: strength and intellect. Initially, both are equal to 1. There are several missions in the game, and to complete mission i, you must have strength of at least strength[i] or intellect of at least intellect[i]. After you complete mission i, you receive points[i] points that can be added to your properties. You can distribute these points however you want between the two properties. Each mission can be completed only once, and missions can be completed in any order. Return the maximum number of missions you can complete.
 

Definition

    
Class:StrengthOrIntellect
Method:numberOfMissions
Parameters:int[], int[], int[]
Returns:int
Method signature:int numberOfMissions(int[] strength, int[] intellect, int[] points)
(be sure your method is public)
    
 

Constraints

-strength will contain between 1 and 50 elements, inclusive.

-strength, intellect and points will contain the same number of elements.

-Each element of strength, intellect and points will be between 1 and 1000, inclusive.

 

Examples

0)
    
{1, 2}
{1, 2}
{1, 2}
Returns: 2
Complete mission 0. After adding 1 point to either inlellect or strength you will be able to complete mission 1.
1)
    
{3}
{2}
{1}
Returns: 0
Only one mission and you can't complete it.
2)
    
{1, 3, 1, 10, 3}
{1, 1, 3, 20, 3}
{2, 1, 1, 5, 1}
Returns: 4
3)
    
{1, 2, 100, 5, 100, 10, 100, 17, 100}
{1, 100, 3, 100, 7, 100, 13, 100, 21}
{1, 2, 3, 4, 5, 6, 7, 8, 1}
Returns: 9
4)
    
{1, 10, 1, 2, 16, 12, 13, 19, 12, 8}
{1, 5, 1, 8, 3, 5, 3, 16, 19, 20}
{1, 1, 1, 2, 1, 1, 2, 3, 5, 1}
Returns: 7

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10174

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13515&pm=10174

Writer:

Gluk

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming