Equity | Topcoder Archive

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.

Definition

Class:: Equity
Method:: minPieces
Parameters:: int, int
Returns:: int
Method signature:: int minPieces(int n, int k)
(be sure your method is public)

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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.