TopCoder Statistics - Problem Statement

Problem Statement

Once there was a powerful artifact and the legend said that the owner of this artifact will have unlimited power. A long time ago a few mages found this artifact and decided that nobody should own it. So each of them cast a protection spell on it. You learned about that and decided that the artifact should be yours, so the plan is to give bribes to the mages to make them remove their spells. You know that if you give a bribe to the i-th mage, he will easily remove his own spell and up to power[i] spells of any other mages. Now you want to calculate the minimal number of mages you should pay to remove all spells from the artifact.

Definition

Class:: CorruptMages
Method:: minimalNumber
Parameters:: int[]
Returns:: int
Method signature:: int minimalNumber(int[] power)
(be sure your method is public)

Constraints

power will contain between 1 and 50 elements, inclusive.
Each element of power will be between 0 and 50, inclusive.

Examples

{0,0,0,0,0}

Returns: 5

Here each of five mages can only remove his own spell. So, we have to give bribes to all of them.
{0,1,3,0}

Returns: 1

Now there is a powerful mage who can remove his own spell and all three spells of his colleagues. So it is enough to give a bribe to him.
{0}

Returns: 1

We have to give a bribe to the single mage.
{0,1,2,2,0,1,3,1}

Returns: 3
{50}

Returns: 1
{50,50}

Returns: 1
{0,1}

Returns: 1
{1,1,1,1}

Returns: 2
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

Returns: 50
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0}

Returns: 49
{50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50,50}

Returns: 1
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

Returns: 27
{2,2,1,2,2,2,1}

Returns: 3
{1,1,1,1,0,0,0,1,0,1,1,0}

Returns: 6
{5,4,2,0,2,1,7,2,6,7,4,5,0,2,2,10,8,10,3,8,4,6,1,4,7,8,6,2,6,1,5,7,8,9,6,6,5,4,6,7,10,5,3,7,10,5,6,7,7,9}

Returns: 5
{3,4,4,4,4,3,3,3,3,3,4,4,4,4,4,4,3,4,3,4}

Returns: 4
{20,20,21,20,21,20,20,20,21,20,20,20,21,21,21,21,21,21,20,21,21,21,21,21,20,20,21,21,20,21}

Returns: 2
{48,47,50,47,48,47,50,47,49,48,50,50,47,50,47,50,49,49,49,48,50,48,50,49,48,49,50,49,48,47,48,47,47,50,49,49,47,48,49,49,47,47,49,50,50,49,47,48,48}

Returns: 1
{3,3,3,1,2,1,1,1,3,1,1,1,2,3,3,2,2,3}

Returns: 5
{15,24,5,37,12,6,15,2,18,34,1,2,15,22,7,32,7,29,31,43,9,3,31,20,14,43,25,8,42,49,36,2,5,20,37,42,3,43,10,32,48,27,13,13,46,46,34,11}

Returns: 1
{50,50}

Returns: 1
{1,2,1,2}

Returns: 2
{2,3,3,4,3,2,2,3,4,4,2,4,2,3}

Returns: 3
{5,4,4,3,4,4,5,3,3,5,4,4,3,4,5,4,5,5,5,4,3,3,5,5,3,4,4}

Returns: 5
{2,2,3,2,2,3,3,2,2,2,3,3,3,2,3,3,2,3,2,2,3,2,2,2,2,3,3,2,2,3,2,3,2,2,3,2,2,3,3,2,2,3,3,3,3,3,2,2}

Returns: 12
{0,1,1,0,1,1,1,1,0,1,1,1,0,1,1,0,0,1,0,0,0,1,1,1,1,1,0,1,0,1,0,1,1,0,0,1,1,1,0,0,1,0,0,1,1,1,0,0,1,0}

Returns: 25
{1,1,1,4,2,2,3,4,3,0,3,4,2,5,1,1,0,4,1,2,1,4,2,3,3,5,1,4,4,5,1,3,3,5,1,1,3,5,0,3,3,4,3,5,3,4,2,2}

Returns: 9
{3,2,3,4,2,4,4,4,3,4,2,3,3,3,2,3,2,2,2,3,4,2,3,3,3,4,3,3,3}

Returns: 6
{5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5}

Returns: 6
{1,2,1,2,2,2,2,2,2,2,2,1,1,2,2,2,1,1,2,1,1,1,2,2,2,1,2,1,1,2,2,1,2,2,1,1,1,2,1,1,2,2,1,2,1,1,2}

Returns: 16
{0, 1, 3, 0 }

Returns: 1
{0, 1, 2, 2, 0, 1, 3, 1 }

Returns: 3
{5 }

Returns: 1
{0, 0, 0, 0, 0 }

Returns: 5
{1, 1, 1, 1, 1, 1 }

Returns: 3
{1, 1, 9 }

Returns: 1

Statistics

Problem Statement for "CorruptMages"

Problem Statement

Definition

Constraints

Examples