TopCoder problem "Caketown" used in College Tour Sichuan (Division I Level One)



Problem Statement

    

You and some friends are making a visit to a cake restaurant in scenic Caketown. On the table are a variety of cakes of different sizes, with size being measured in "bites". You've decided to take turns picking cakes until all of the cakes are picked by either you or one of your friends. You all like big cakes, so each person on their turn will pick the biggest remaining cake. If there's a tie for the biggest cake, it doesn't matter which of the tied cakes is picked. Since it's your birthday, you get to pick the first cake.

 

For example, suppose you have two friends and there are 5 cakes with sizes of 6, 7, 9, 6, and 4. You will pick the 9 bite cake, your first friend will pick the 7 bite cake, your other friend will get one of the 6 bite cakes, you will get the other 6 cake, and your first friend will get the 4. You will get a total of 15 bites of cake.

 

numFriends will be the number of friends you have with you (not including you). cakeSizes will be a list of integers, each of which is the size of one cake - not necessarily in order of size. Return the total bites of cake you will get.

 

Definition

    
Class:Caketown
Method:howManyBites
Parameters:int[], int
Returns:int
Method signature:int howManyBites(int[] cakeSize, int numFriends)
(be sure your method is public)
    
 

Constraints

-cakeSize will contain between 1 and 10 elements, inclusive.
-Each element of cakeSize will be between 1 and 10, inclusive.
-numFriends will be between 1 and 5, inclusive.
 

Examples

0)
    
{10}
5
Returns: 10
There may be more people than cakes, but luckily you get first pick.
1)
    
{1,1,1,5,1}
3
Returns: 6
You will pick the size 5 cake, and you'll also end up getting one of the size 1 cakes.
2)
    
{6,7,9,6,4}
2
Returns: 15
The example from the problem statement.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8047

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10949&pm=8047

Writer:

jmzero

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Simulation