Statistics

Problem Statement for "Equity"

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

  1. 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.

  2. 12

    4

    Returns: 12

    Give each person a third of a bar.

  3. 12

    1

    Returns: 3

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

  4. 12

    1000

    Returns: 1008

  5. 13

    1000

    Returns: 1007

  6. 5

    1

    Returns: 3

  7. 1

    1

    Returns: 1

  8. 1

    6

    Returns: 6

  9. 7

    6

    Returns: 13

  10. 13

    12

    Returns: 19

  11. 15

    12

    Returns: 30

  12. 1

    1000

    Returns: 1000

  13. 1000

    1

    Returns: 3

  14. 1000

    1000

    Returns: 1000

  15. 384

    385

    Returns: 396

  16. 450

    784

    Returns: 1350

  17. 265

    385

    Returns: 530

  18. 864

    858

    Returns: 900

  19. 428

    772

    Returns: 1284

  20. 744

    869

    Returns: 2226

  21. 83

    137

    Returns: 241

  22. 415

    833

    Returns: 866

  23. 905

    945

    Returns: 1385

  24. 600

    165

    Returns: 495

  25. 260

    482

    Returns: 748

  26. 870

    378

    Returns: 870

  27. 517

    785

    Returns: 1091

  28. 299

    950

    Returns: 1476

  29. 401

    844

    Returns: 1306

  30. 83

    852

    Returns: 947

  31. 976

    341

    Returns: 976

  32. 224

    680

    Returns: 768

  33. 991

    619

    Returns: 1732

  34. 242

    624

    Returns: 840

  35. 452

    203

    Returns: 452

  36. 138

    430

    Returns: 606

  37. 974

    11

    Returns: 33

  38. 372

    955

    Returns: 1266

  39. 902

    895

    Returns: 944

  40. 63

    350

    Returns: 399

  41. 93

    173

    Returns: 264

  42. 267

    393

    Returns: 534

  43. 444

    794

    Returns: 1332

  44. 189

    876

    Returns: 1098

  45. 994

    832

    Returns: 1966

  46. 241

    291

    Returns: 664

  47. 894

    983

    Returns: 1962

  48. 877

    786

    Returns: 1423

  49. 841

    23

    Returns: 69

  50. 86

    17

    Returns: 51

  51. 894

    112

    Returns: 336

  52. 674

    347

    Returns: 734

  53. 578

    225

    Returns: 578

  54. 345

    272

    Returns: 690

  55. 450

    285

    Returns: 810

  56. 112

    355

    Returns: 558

  57. 973

    435

    Returns: 973

  58. 539

    645

    Returns: 1520

  59. 199

    276

    Returns: 398

  60. 471

    432

    Returns: 705

  61. 246

    152

    Returns: 420

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.
This problem was used for: