Connection Status:
Competition Arena > PrimalUnlicensedCreatures

PrimalUnlicensedCreatures

SRM 579 · 2012-12-13 · by vexorian

SRM 579 · 2012-12-13 · by vexorian · Greedy
Class Name: PrimalUnlicensedCreatures
Return Type: int
Method Name: maxWins
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

The Primal Grez are ferocious creatures. They constantly fight each other. When a Grez wins a battle against another Grez, the winner captures the loser's essence, thus becoming stronger. More formally:
  • The power level of each Grez is a positive integer.
  • A Grez can only defeat creatures that have a strictly smaller power level.
  • When a Grez of power level X defeats a Grez of power level Y, the first Grez's power level is increased to X + Y/2. Note that Y/2 represents integer division, i.e., the fractional part is discarded. For example, for Y=3 we have Y/2 = 1.
Your goal is to help a Grez that currently has power level equal to int initialLevel battle against a set of other Grez. For each i, Grez number i (0-based index) has a power level equal to grezPower[i]. Your Grez can challenge the other creatures in any order.

You are given the int initialLevel and the int[] grezPower. Return the maximum number of creatures your Grez can defeat, one after another.

Constraints

  • initialLevel will be between 1 and 1000, inclusive.
  • grezPower will contain between 1 and 50 elements, inclusive.
  • Each element of grezPower will be between 1 and 1000, inclusive.
Examples
0)
31
{10, 20, 30}
Returns: 3

It is possible to defeat all the available opponents. For example: Defeat the creature with power level 30. Your creature's power level becomes 31 + 15 = 46. Defeat the creature with power level 10. Your creature's power level becomes 46 + 5 = 51. Defeat the creature with power level 20. Your creature's power level becomes 51 + 10 = 61.

1)
20
{24, 5, 6, 38}
Returns: 3

It is best to defeat creatures 1 and 2 before facing creature 0. Your creature's power level will be 25 when facing creature 0. It is not possible to defeat creature 3.

2)
20
{3, 3, 3, 3, 3, 1, 25 }
Returns: 6

It is possible to defeat the 6 weakest creatures. After that your creature's power level will be 25, which is not strong enough to defeat another level 25 creature.

3)
4
{3, 13, 6, 4, 9}
Returns: 5
4)
7
{7, 8, 9, 10}
Returns: 0

All the available opponents are too strong for your creature to defeat.

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

Coding Area

Language: C++17 · define a public class PrimalUnlicensedCreatures with a public method int maxWins(int initialLevel, vector<int> grezPower) · 55 test cases · 2 s / 256 MB per case

Submitting as anonymous