Connection Status:
Competition Arena > BirthdayCandy

BirthdayCandy

TCO19 SRM 742 · 2018-11-27 · by misof

TCO19 SRM 742 · 2018-11-27 · by misof · Simple Math
Class Name: BirthdayCandy
Return Type: int
Method Name: mostCandy
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

Elisa is a primary school student. Tomorrow it's her birthday!

In Elisa's country it is customary that when it's your birthday, you are supposed to bring candy for everyone. Hence, Elisa's mother is now taking Elisa to buy a bag of candy for tomorrow.

Social protocol dictates that candy is always given out to classmates using the following algorithm: 

repeat:
    if there is still enough candy for everyone (including you):
        give everyone else one candy
        take one candy for yourself
    else:
        stop (and you get to keep the candy that remained in the bag)

You know that there are K other kids in Elisa's class.

The store carries different brands of candy. You are given their description in the int[] candy. Each element of candy is the number of pieces of candy in one of the bags available at the store. Find out which bag should Elisa choose if she wants the most candy for herself. Return the number of pieces of candy she will get to keep if she chooses the bag wisely.

Constraints

  • K will be between 1 and 50, inclusive.
  • candy will have between 1 and 50 elements, inclusive.
  • Each element of candy will be between 1 and 1000, inclusive.
Examples
0)
9
{23, 7}
Returns: 7

If Elisa buys the bag with 23 candies, the following will happen: 23 is enough to give everyone a candy, so she gives everyone else a candy and then takes one herself. 13 is enough to give everyone a candy, so she gives everyone else a candy and then takes one herself. 3 is no longer enough to give everyone a candy, so she keeps the remaining 3 candies. In total, she would have 1+1+3 = 5 candies. On the other hand, if she buys the bag with 7 candies, she will get to keep all of them.

1)
1
{1, 2}
Returns: 1

Here it does not matter which bag Elisa buys. In either case she will end with a single candy.

2)
4
{43, 81, 17, 1, 9}
Returns: 17
3)
6
{7}
Returns: 1
4)
9
{4,5,6,7,8,9,10,11,12,13,14,15,16}
Returns: 9

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

Coding Area

Language: C++17 · define a public class BirthdayCandy with a public method int mostCandy(int K, vector<int> candy) · 62 test cases · 2 s / 256 MB per case

Submitting as anonymous