StrengthOrIntellect
SRM 424 · 2008-11-05 · by Gluk
SRM 424 · 2008-11-05 · by Gluk · Dynamic Programming
Problem Statement
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.
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
Submissions are judged against all 121 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class StrengthOrIntellect with a public method int numberOfMissions(vector<int> strength, vector<int> intellect, vector<int> points) · 121 test cases · 2 s / 256 MB per case