SpaceWarDiv1
SRM 582 · 2012-12-13 · by semiexp
Problem Statement
You are given a
Each Magical Girl will always fight one enemy at a time. A Magical Girl will defeat her enemy if her strength is greater than or equal to the strength of that enemy.
At the beginning of the fight the fatigue of each Magical Girl is 0. Each time a Magical Girl defeats an enemy, her fatigue increases by 1.
The Magical Girls want to defeat all the enemies. That is, each of the enemies must be defeated by one of the Magical Girls. Additionally, the Magical Girls want to minimize the maximum fatigue among them.
If it is impossible to defeat all of the enemies, return -1. Otherwise, return the smallest F with the following property: the Magical Girls can defeat all enemies in such a way that at the end the fatigue of each girl is at most F.
Notes
- The elements of enemyStrength are not necessarily pairwise distinct.
Constraints
- magicalGirlStrength will contain between 1 and 50 elements, inclusive.
- Each element of magicalGirlStrength will be between 1 and 10,000, inclusive.
- enemyStrength and enemyCount will each contain between 1 and 50 elements, inclusive.
- enemyStrength and enemyCount will contain the same number of elements.
- Each element of enemyStrength will be between 1 and 10,000, inclusive.
- Each element of enemyCount will be between 1 and 100,000,000,000,000 (10^14), inclusive.
{2, 3, 5}
{1, 3, 4}
{2, 9, 4}
Returns: 7
There are 3 Magical Girls, their strength are 2, 3, and 5. There are 3 kinds of enemies: 2 enemies with strength 1 each, 9 enemies with strength 3 each, and 4 enemies with strength 4 each. This is one of the ways how to minimize the maximal fatigue: Magical girl 0 defeats 2 enemies with strength 1. Magical girl 1 defeats 7 enemies with strength 3. Magical girl 2 defeats 2 enemies with strength 3 and 4 enemies with strength 4.
{2, 3, 5}
{1, 1, 2}
{2, 9, 4}
Returns: 5
Each of the Magical Girls can defeat any of the enemies. The optimal strategy is that each girl should defeat 5 of the enemies.
{14, 6, 22}
{8, 33}
{9, 1}
Returns: -1
None of the magical girls can defeat the enemy with strength 33.
{869, 249, 599, 144, 929, 748, 665, 37, 313, 99, 33, 437, 308, 137, 665, 834, 955, 958, 613, 417}
{789, 57, 684, 741, 128, 794, 542, 367, 937, 739, 568, 872, 127, 261, 103, 763, 864, 360, 618, 307}
{20626770196420, 45538527263992, 52807114957507, 17931716090785, 65032910980630, 88711853198687, 26353250637092,
61272534748707, 89294362230771, 52058590967576, 60568594469453, 23772707032338, 43019142889727, 39566072849912,
78870845257173, 68135668032761, 36844201017584, 10133804676521, 6275847412927, 37492167783296}
Returns: 75030497287405
{674, 527, 829, 824, 365, 6, 826, 726, 302, 155, 187, 162, 880, 857, 417, 738, 239,
41, 987, 674, 847, 493, 224, 540, 597, 195, 689, 218, 200, 571, 509, 683, 389, 229,
230, 101, 120, 862, 105, 387, 117, 602, 441, 499, 872, 273, 770, 179, 951, 476}
{675, 374, 681, 771, 164, 381, 270, 389, 219, 334, 646, 24, 625, 755, 807, 822, 932,
803, 59, 163, 895, 634, 472, 768, 845, 33, 518, 304, 546, 292, 144, 791, 739, 126,
334, 954, 470, 522, 461, 583, 430, 914, 944, 904, 848, 341, 406, 111, 301, 54}
{539, 2461, 8289, 254, 9151, 2104, 6425, 2694, 531, 4440, 975, 7840, 5117, 3242, 676, 6743, 2670,
6163, 8060, 965, 4979, 2025, 7266, 8803, 6297, 6777, 798, 2765, 4351, 5602, 3205, 419, 9241, 785,
9050, 1911, 4811, 2243, 3596, 3197, 1442, 2120, 1141, 8917, 3487, 5775, 3612, 5341, 5942, 8307}
Returns: 10869
Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SpaceWarDiv1 with a public method long long minimalFatigue(vector<int> magicalGirlStrength, vector<int> enemyStrength, vector<long long> enemyCount) · 107 test cases · 2 s / 256 MB per case