Connection Status:
Competition Arena > CreatureTraining

CreatureTraining

TCO08 Round 2 · 2008-01-21 · by ivan_metelsky

TCO08 Round 2 · 2008-01-21 · by ivan_metelsky · Dynamic Programming
Class Name: CreatureTraining
Return Type: long
Method Name: maximumPower
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

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.

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.

Submissions are judged against all 194 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CreatureTraining with a public method long long maximumPower(vector<int> count, vector<int> power, int D) · 194 test cases · 2 s / 256 MB per case

Submitting as anonymous