Equity

TCO '03 Semifinals 3 · 2003-10-07 · by dgoodman

TCO '03 Semifinals 3 · 2003-10-07 · by dgoodman · Advanced Math

Show categories

Class Name: Equity

Return Type: int

Method Name: minPieces

Arg Types: (int, int)

Problem Statement

We are given k candy bars to divide up among n people. Each bar may be left whole, split into 2 equal pieces, or split into 3 equal pieces. We must distribute all the candy to the people, but we want to be as fair as possible. Define the "inequity" of a distribution of the candy to be the difference between the minimum amount received by a person and the maximum amount received by a person. We want to minimize the inequity.

Among solutions that have minimum inequity, we want to choose the one that has the fewest pieces. Each whole bar counts as one piece, while each split bar counts as either two or three pieces depending on how it was split. Create a class Equity that contains a method minPieces that takes n, the number of people, and k, the number of candy bars, and returns the smallest number of pieces that we will need in order to divide the candy bars with minimum inequity.

Constraints

n will be between 1 and 1000 inclusive
k will be between 1 and 1000 inclusive

Examples

12
11
Returns: 18

Split 2 of the bars into thirds, and 3 of the bars into halves. Give 6 of the people a third of a bar and a half of a bar each. Give the other 6 people a whole bar each. This results in an inequity of 1 - (1/2+1/3) = 1/6 which is the minimum possible inequity. There are 18 pieces: 6 thirds, 6 halves, and 6 wholes.

12
4
Returns: 12

Give each person a third of a bar.

12
1
Returns: 3

The best we can do is to give 3 people a third, and the other 9 nothing.

12
1000
Returns: 1008

13
1000
Returns: 1007

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

Coding Area

Language: C++17 · define a public class Equity with a public method int minPieces(int n, int k) · 61 test cases · 2 s / 256 MB per case