ColorfulRabbits
SRM 499 · 2010-11-01 · by lyrically
SRM 499 · 2010-11-01 · by lyrically · Simple Math
Problem Statement
Problem Statement
Cat Pochi visited a town of rabbits and asked some of the rabbits the following question:
"How many rabbits in this town other than yourself have the same color as you?".
The rabbits all replied truthfully, and no rabbit was asked the question more than once.
You are given the rabbits' replies in the int[] replies.
Return the minimum possible number of rabbits in this town.
Constraints
- replies will contain between 1 and 50 elements, inclusive.
- Each element of replies will be between 0 and 1,000,000, inclusive.
Examples
0)
{ 1, 1, 2, 2 }
Returns: 5
If there are 2 rabbits with a color and 3 rabbits with another color, Pochi can get this set of replies.
1)
{ 0 }
Returns: 1
A poor lonely rabbit.
2)
{ 2, 2, 44, 2, 2, 2, 444, 2, 2 }
Returns: 499
3)
{ 999951, 999952, 999953, 999954, 999955, 999956, 999957, 999958, 999959, 999960, 999961, 999962, 999963, 999964, 999965, 999966, 999967, 999968, 999969, 999970, 999971, 999972, 999973, 999974, 999975, 999976, 999977, 999978, 999979, 999980, 999981, 999982, 999983, 999984, 999985, 999986, 999987, 999988, 999989, 999990, 999991, 999992, 999993, 999994, 999995, 999996, 999997, 999998, 999999, 1000000 }
Returns: 49998825
4)
{ 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
Submissions are judged against all 101 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ColorfulRabbits with a public method int getMinimum(vector<int> replies) · 101 test cases · 2 s / 256 MB per case