Problem Statement |
| | You are playing a strategy game and you wish to train the strongest army for the final fight. There are creatures of N levels in the game, numbered from 0 to N-1, inclusive. You already have some creatures in your army and D days to train them. The number of creatures you have is given in a int[] count. It contains N elements and its i-th element is the number of creatures of level i.
During each day, you can choose one creature and train it. Training increases a creature's level by 1, i.e., a creature of level 0 becomes a creature of level 1, a creature of level 1 becomes a creature of level 2, and so on. The only exception is creatures of level N-1 - such creatures can't be trained as N-1 is the largest possible level. You can train the same creature during more than one day. For example, if you train a creature during 3 days, it will gain 3 levels. You can also skip days and not train any creatures during those days.
You are given a int[] power, where the i-th element of power is the power of one creature of level i. The power of your army is the sum of the powers of all its creatures. Return the maximum possible power your army can have after all D days of training are finished. |
| |
Definition |
| | | Class: | CreatureTraining | | Method: | maximumPower | | Parameters: | int[], int[], int | | Returns: | long | | Method signature: | long maximumPower(int[] count, int[] power, int D) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | count will contain between 1 and 50 elements, inclusive. |
| - | power will contain the same number of elements as count. |
| - | Each element of count and power will be between 0 and 1,000,000, inclusive. |
| - | D will be between 1 and 100, inclusive. |
| |
Examples |
| 0) | |
| | {1, 2, 3, 4, 5} | {1, 2, 3, 4, 5} | 10 |
| Returns: 65 | | The initial power of your army is 1*1 + 2*2 + 3*3 + 4*4 + 5*5 = 55. Independent of a creature's level, training increases its power by 1. After 10 days of training the power of your army will be 55 + 10 = 65. |
|
|
| 1) | |
| | {1, 2, 3, 4, 5} | {1, 4, 9, 16, 25} | 10 |
| Returns: 309 | | Now it's better to train higher level creatures, as it'll give your army more additional power. In 10 days you're able to convert 3 creatures with initial level 3 and 4 creatures with initial level 4 into level 5. |
|
|
| 2) | |
| | {1000, 0, 0, 0, 0} | {0, 100, 10, 1000, 0} | 8 |
| Returns: 2200 | | You have 1000 newcomers of level 0. The best solution is to train 2 of them up to level 3, and 2 up to level 1. |
|
|
| 3) | |
| | {1, 2, 3, 4, 5} | {5, 4, 3, 2, 1} | 50 |
| Returns: 35 | | It doesn't make sense to train anybody. |
|
|
| 4) | |
| | {0, 5, 0, 0, 5, 0} | {13, 20, 21, 30, 32, 36} | 12 |
| Returns: 318 | | Train 5 creatures from level 1 to level 3, and 2 creatures from level 4 to level 5. |
|
|
| 5) | |
| | {0, 2, 1, 0, 0, 1, 2} | {25, 292, 328, 391, 618, 771, 952} | 11 |
| Returns: 5088 | | Train everybody except a creature with initial level 2 up to the maximum possible level. |
|
|