Statistics

Problem Statement for "ShoppingStickers"

Problem Statement

Your favorite store has a promotion: each time you pay for your shopping, for every S dollars spent on the bill the cashier will give you a random sticker.

For example, suppose S = 10. If you purchase items worth a total of 27 dollars, you would get two stickers from the cashier. (This is because 27 dollars is 10 dollars + 10 dollars + 7 dollars, so you get a sticker + a sticker + nothing for the last 7 dollars.)

If you purchased items worth a total of 30 dollars instead, you would get three stickers.


You really like the stickers and you want to have as many of them as possible.

There is a collection of items you want to purchase. You are given their prices in dollars in the int[] items. You want to purchase exactly these items, each of them exactly once, and nothing else.

You are not required to do all your shopping at once. Instead, you can split it into as many purchases as you want. I.e., you can take some subset of items, pay for them, get the stickers for that payment, take another subset of items, pay for those, get stickers for the second payment, and so on.


Sadly, it is also possible that your mother will send your cousin Bob to do the shopping instead of you. If this happens, Bob is also going to purchase the exact same set of items. He can also do the shopping as a sequence of arbitrarily many purchases of subsets of desired items. Bob does not care about stickers.


Let A be the maximum total number of stickers you can get. (I.e., we are assuming you do the shopping in the smartest possible way.)

Let B be the minimum total number of stickers Bob can get. (I.e., we are assuming Bob does the shopping in the worst possible way.)

Return the int[] {A, B}.

(That is, the correct return value is a int[] with two elements: element at index 0 has the value A, and element at index 1 has the value B.)

Definition

Class:
ShoppingStickers
Method:
purchase
Parameters:
int, int[]
Returns:
int[]
Method signature:
int[] purchase(int S, int[] items)
(be sure your method is public)

Constraints

  • S will be between 1 and 1000, inclusive.
  • items will contain between 1 and 10 elements, inclusive.
  • Each element of items will be between 1 and 1000, inclusive.

Examples

  1. 10

    {47}

    Returns: {4, 4 }

    You want a single item worth 47 dollars. Regardless of who does the purchase, they will get four stickers.

  2. 7

    {10, 21, 98, 19}

    Returns: {21, 20 }

    One possible way how you can get the most stickers: Purchase the item worth 21, pay 21, get 3 stickers. Purchase the other three items, pay (10 + 98 + 19) = 127, get 18 stickers. Your total is 21 stickers. One possible way how Bob can get the least stickers: He'll purchase the item worth 19, pay 19, get 2 stickers. Then he'll purchase the other three items, pay (10 + 21 + 98) = 129, get 18 stickers. Bob's total is 20 stickers.

  3. 6

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: {1, 0 }

    You will get a sticker if and only if one of your purchases includes at least six of these ten items. (Even though they all have the same price, they are still ten different items.)

  4. 1

    {10, 20, 30, 40, 50, 60}

    Returns: {210, 210 }

    If S = 1, it does not matter how you shop: the total number of stickers you'll get will always be equal to the total price of the items you are buying.

  5. 11

    {2, 3, 4, 5, 6, 7, 8, 9, 11, 12}

    Returns: {6, 2 }

  6. 2

    {1}

    Returns: {0, 0 }

  7. 1

    {1}

    Returns: {1, 1 }

  8. 1

    {1, 1}

    Returns: {2, 2 }

  9. 36

    {567, 465, 585, 352, 264, 525, 396}

    Returns: {87, 84 }

  10. 69

    {675, 25, 981, 105, 1, 271, 966}

    Returns: {43, 41 }

  11. 130

    {582, 438, 236, 244, 536, 527}

    Returns: {19, 17 }

  12. 60

    {35, 575, 384, 734}

    Returns: {28, 27 }

  13. 53

    {589, 781, 201, 245, 808, 861, 747, 937, 958}

    Returns: {115, 112 }

  14. 1

    {101, 372, 593, 393, 521, 554}

    Returns: {2534, 2534 }

  15. 19

    {950, 716, 866, 343}

    Returns: {151, 150 }

  16. 15

    {792, 427}

    Returns: {81, 80 }

  17. 50

    {829, 569, 945, 268}

    Returns: {52, 50 }

  18. 34

    {320, 577, 799, 405, 267, 968, 748, 532}

    Returns: {135, 131 }

  19. 9

    {389, 498, 260, 986}

    Returns: {237, 235 }

  20. 332

    {16, 175, 561, 643, 824, 780, 85, 77}

    Returns: {9, 6 }

  21. 31

    {375, 941, 778, 34, 623, 272, 921}

    Returns: {127, 125 }

  22. 497

    {850, 23, 591, 249, 217, 355}

    Returns: {4, 2 }

  23. 87

    {482, 944, 204}

    Returns: {18, 17 }

  24. 4

    {748, 804, 584}

    Returns: {534, 534 }

  25. 57

    {274, 455}

    Returns: {12, 11 }

  26. 1

    {69, 379, 22, 271, 43, 144, 186}

    Returns: {1114, 1114 }

  27. 507

    {802, 792, 832, 507}

    Returns: {5, 4 }

  28. 488

    {581, 11, 712, 76, 180, 856, 155, 944, 557, 347}

    Returns: {9, 5 }

  29. 1

    {388}

    Returns: {388, 388 }

  30. 2

    {310, 56}

    Returns: {183, 183 }

  31. 413

    {628, 918, 752, 548}

    Returns: {6, 5 }

  32. 6

    {879, 585, 83, 577, 504, 351, 570, 54, 977, 118}

    Returns: {783, 779 }

  33. 117

    {929, 311, 578, 865, 778, 501}

    Returns: {33, 30 }

  34. 4

    {120, 925, 473, 669, 806, 465, 844, 19, 446}

    Returns: {1191, 1189 }

  35. 289

    {803, 722, 502, 515, 117}

    Returns: {9, 6 }

  36. 13

    {171, 474, 24, 602, 101, 688}

    Returns: {158, 155 }

  37. 245

    {654, 558, 703, 712, 706}

    Returns: {13, 10 }

  38. 1

    {42, 791, 270, 556, 495}

    Returns: {2154, 2154 }

  39. 7

    {8, 8, 8, 8, 8, 8, 1}

    Returns: {7, 6 }

  40. 4

    {1, 2, 2, 2 }

    Returns: {1, 0 }

  41. 5

    {7, 12, 22, 32 }

    Returns: {14, 13 }

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: