Statistics

Problem Statement for "MysticAndCandiesEasy"

Problem Statement

TopCoder admin mystic_tc is sitting in front of a table. He found N sealed boxes of candies on the table.

He is not sure how many candies each box contains. However, he knows the following information:
  • The total number of candies in the boxes is C.
  • For each i, box i (0-based index) contains between 0 and high[i] candies, inclusive.

You know that mystic_tc eats candies as follows: first he chooses a subset of the boxes, then he opens them and eats all the candies he found inside. He wants to eat at least X candies. And as he is smart, he will always choose a subset of boxes for which he is sure that they must contain at least X candies.

You are given the ints C and X, and the int[] high. Return the smallest number of boxes mystic_tc may choose.

Definition

Class:
MysticAndCandiesEasy
Method:
minBoxes
Parameters:
int, int, int[]
Returns:
int
Method signature:
int minBoxes(int C, int X, int[] high)
(be sure your method is public)

Constraints

  • high will contain between 1 and 50 elements, inclusive.
  • Each element of high will be between 1 and 50, inclusive.
  • C will be between 1 and the sum of all elements of high, inclusive.
  • X will be between 1 and C, inclusive.

Examples

  1. 10

    10

    {20}

    Returns: 1

    There is only one box. It contains all 10 candies. In order to eat 10 candies mystic_tc must open it.

  2. 10

    7

    {3, 3, 3, 3, 3}

    Returns: 4

    Now there are many possibilities for the contents of boxes. For example, there could be three boxes with 3 candies each, one box with 1 candy, and one empty box. Another possibility is that there could be five boxes with 2 candies each. Note that in this case mystic_tc could open three boxes and still get only 6 candies, so he needs to open at least four boxes to be sure he gets at least 7 candies. And it can be proved that if mystic_tc opens any four of these boxes, they will always contain at least 7 candies in total.

  3. 100

    63

    {12, 34, 23, 45, 34}

    Returns: 3

    Open boxes 1, 3, 4 (0-based). It can be proved that these boxes contain at least 65 candies in total.

  4. 26

    5

    {6, 9, 15, 3, 11, 6, 8, 12}

    Returns: 5

  5. 168

    30

    {2, 15, 6, 1, 1, 10, 14, 18, 13, 11, 17, 17, 11, 12, 18, 11, 9, 7}

    Returns: 4

  6. 5

    3

    {9, 1}

    Returns: 1

  7. 19

    12

    {12, 9, 15, 1, 6, 4, 9, 10, 10, 10, 14, 14, 1, 1, 12, 10, 9, 2, 3, 6, 1, 7, 3, 4, 10, 3, 14}

    Returns: 22

  8. 712

    285

    {35, 5, 15, 2, 35, 26, 20, 28, 1, 8, 28, 16, 36, 36, 20, 22, 30, 31, 8, 8, 32, 35, 20, 31, 19, 1, 17, 12, 29, 12, 11, 25, 14, 17, 12, 8, 30, 12, 24, 9, 8, 8, 12, 28, 17, 2, 13, 31, 36, 28}

    Returns: 17

  9. 29

    26

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

    Returns: 22

  10. 326

    109

    {9, 13, 6, 6, 6, 16, 16, 16, 10, 16, 4, 3, 10, 8, 11, 17, 12, 5, 7, 8, 7, 4, 15, 7, 14, 2, 2, 1, 17, 1, 7, 7, 12, 17, 2, 9, 7, 1, 8, 16, 7, 4, 16, 2, 13, 3, 13, 1, 17, 6}

    Returns: 15

  11. 198

    136

    {16, 17, 7, 20, 17, 19, 13, 18, 9, 19, 6, 15, 15, 22, 15, 2, 15, 16, 6, 19, 6, 21, 20, 19, 1, 2, 3, 7, 2, 19, 17, 22, 4, 2, 3, 11, 22, 15, 12, 11, 17, 19, 1, 9, 15, 21, 18, 6, 13, 16}

    Returns: 35

  12. 2

    1

    {4}

    Returns: 1

  13. 20

    5

    {18, 22, 20, 2, 13, 3, 11, 22, 17, 2, 9, 22, 11, 11, 7, 21, 4, 21, 9, 2, 7, 4, 7, 9, 3, 18, 19, 12, 22}

    Returns: 24

  14. 128

    42

    {3, 4, 2, 5, 4, 2, 3, 6, 3, 2, 3, 2, 5, 4, 4, 4, 3, 1, 3, 3, 1, 1, 4, 3, 6, 6, 3, 4, 1, 4, 5, 2, 3, 1, 2, 6, 2, 6, 1, 1, 2, 3, 2}

    Returns: 9

  15. 135

    106

    {2, 3, 2, 1, 5, 5, 5, 4, 6, 2, 1, 1, 3, 5, 3, 1, 5, 5, 5, 3, 2, 4, 6, 5, 3, 1, 3, 6, 1, 1, 3, 2, 5, 4, 6, 3, 1, 2, 5, 5, 1, 1, 3, 1, 4, 4, 1, 3, 6, 4}

    Returns: 31

  16. 66

    6

    {5, 35, 45, 17, 15, 30, 36, 22, 38, 41, 1, 40, 21, 3, 40, 12, 22, 30, 25, 6}

    Returns: 13

  17. 62

    29

    {9, 8, 16, 3, 3, 3, 9, 16, 12, 13, 4, 16, 15, 9, 11, 17, 16, 16, 14, 13, 13, 12, 9, 7, 15, 3, 10, 4, 5, 11, 4, 11, 6, 9, 6, 3, 7}

    Returns: 28

  18. 258

    9

    {32, 19, 39, 14, 2, 13, 19, 36, 21, 16, 25, 11, 21, 21, 19, 6, 9, 14, 10, 24, 38, 28, 30, 18, 32, 2, 31, 16, 34}

    Returns: 12

  19. 425

    225

    {36, 21, 38, 30, 38, 10, 23, 26, 38, 16, 40, 1, 38, 42, 33}

    Returns: 6

  20. 48

    41

    {28, 25, 25, 30, 17, 27, 32, 4, 10, 30, 36, 23, 32}

    Returns: 12

  21. 96

    16

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

    Returns: 28

  22. 538

    47

    {38, 21, 34, 30, 19, 40, 37, 33, 27, 22, 13, 3, 37, 32, 45, 28, 14, 10, 18, 13, 34, 9, 20, 10, 22, 16, 50, 4, 23, 32, 49, 8, 8, 12, 22, 20, 33, 39, 47, 35, 41, 50, 4, 21, 5}

    Returns: 16

  23. 139

    58

    {1, 6, 4, 3, 3, 4, 7, 2, 5, 3, 5, 1, 1, 3, 4, 2, 5, 5, 5, 1, 1, 7, 4, 7, 6, 5, 7, 5, 1, 1, 4, 5, 2, 1, 2, 1, 7, 7, 3, 3, 5, 6, 3, 1, 4, 1, 1, 2, 3, 2}

    Returns: 17

  24. 415

    257

    {43, 30, 22, 21, 23, 36, 15, 4, 48, 46, 10, 23, 29, 23, 12, 7, 26, 33, 27, 17, 33, 20}

    Returns: 12

  25. 413

    220

    {10, 8, 14, 6, 18, 4, 17, 12, 8, 10, 16, 20, 12, 20, 20, 15, 10, 8, 12, 4, 9, 18, 2, 14, 15, 6, 8, 5, 7, 3, 7, 11, 12, 4, 13, 15, 8, 20, 16, 12, 4, 12, 19, 12, 13, 5, 6, 5, 9, 2}

    Returns: 22

  26. 73

    37

    {6, 5, 2, 6, 2, 3, 1, 6, 2, 2, 6, 3, 5, 3, 1, 2, 6, 1, 5, 3, 3, 4, 6, 1, 3, 6, 2, 6, 1, 6, 2, 4, 4, 4, 6, 1, 1, 1, 6, 6, 2, 2, 5, 4, 4, 2, 5, 4, 2, 2}

    Returns: 29

  27. 156

    93

    {16, 12, 7, 14, 6, 7, 2, 2, 15, 8, 15, 13, 13, 13, 10, 8, 14, 10, 1, 18, 7, 1, 2, 6}

    Returns: 12

  28. 21

    9

    {8, 15}

    Returns: 1

  29. 145

    43

    {15, 2, 5, 19, 11, 14, 14, 12, 18, 10, 25, 24, 12, 16, 5, 11, 16, 18, 6, 9, 2, 12, 2, 1, 20, 12, 8, 18, 2, 1, 12, 14, 9, 14, 13, 8, 17, 15, 6, 23, 2, 4, 9, 15, 4, 14, 6, 20, 10, 11}

    Returns: 30

  30. 156

    84

    {25, 29, 21, 5, 12, 8, 18, 9, 16, 8, 26, 18, 18, 29, 18, 3, 11, 14, 19, 13, 7, 9, 16, 28, 19, 21, 23, 11, 14, 10, 29, 12, 13, 25, 25, 6, 19, 12, 4, 29, 4, 23, 23, 6, 4, 1, 4, 5, 21, 22}

    Returns: 37

  31. 149

    33

    {26, 8, 11, 22, 4, 5, 25, 30, 10, 2, 28, 22, 24, 20, 13, 30}

    Returns: 7

  32. 7

    3

    {1, 2, 4, 5, 6, 3, 3, 5, 13, 11, 13, 13}

    Returns: 10

  33. 30

    26

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

    Returns: 46

  34. 4

    1

    {3, 1, 6, 1, 5, 1, 6, 6, 3, 2, 1, 2, 9, 6, 6, 6, 6, 9, 9, 4, 4, 5, 7, 7, 3, 2, 1, 2, 7, 4, 8, 1, 6, 5}

    Returns: 31

  35. 577

    413

    {10, 21, 14, 9, 18, 37, 7, 44, 26, 47, 26, 10, 39, 39, 46, 34, 20, 9, 13, 15, 24, 29, 30, 6, 48, 24, 28, 47, 17, 19, 29, 26, 19, 19, 34, 23, 41, 47, 22, 20, 13, 44, 14, 11, 30, 17, 31, 48, 28, 14}

    Returns: 36

  36. 329

    290

    {6, 20, 16, 30, 18, 8, 9, 17, 25, 31, 4, 15, 29, 16, 3, 4, 4, 15, 18, 25, 19, 2, 7, 13, 6, 27, 1, 12, 28, 19, 2, 32, 27, 6, 12, 27, 6, 14, 8, 21, 4, 6, 7, 21, 21, 16, 23, 21, 2}

    Returns: 38

  37. 89

    26

    {15, 1, 11, 13, 1, 18, 8, 14, 11, 11}

    Returns: 3

  38. 165

    110

    {29, 35, 26, 3, 33, 42, 25, 29, 2, 13, 42, 26, 25}

    Returns: 9

  39. 19

    11

    {14, 12, 13, 16, 15}

    Returns: 5

  40. 263

    151

    {28, 32, 37, 2, 13, 13, 5, 2, 36, 6, 30, 16, 17, 30, 20, 3, 9, 7, 32, 10, 38, 24, 26, 4, 37, 15, 8, 25, 14, 35, 14, 25, 25, 29, 38, 11, 13, 17, 1, 38, 28, 26, 22, 14}

    Returns: 29

  41. 589

    275

    {31, 14, 24, 24, 32, 5, 17, 10, 2, 24, 22, 14, 23, 38, 19, 10, 5, 23, 18, 15, 28, 8, 37, 23, 28, 29, 12, 28, 11, 24, 23, 32, 32, 26, 22, 25, 20, 19, 11, 16, 33, 13, 35, 33, 11, 4, 10, 34, 5, 23}

    Returns: 25

  42. 32

    9

    {8, 21, 10, 21, 21, 26, 5, 5, 20, 19, 21, 22, 20, 12, 31, 32, 26, 11, 8, 11, 31, 18, 35, 22, 36}

    Returns: 22

  43. 56

    51

    {2, 3, 3, 2, 2, 1, 5, 1, 3, 3, 1, 4, 3, 2, 1, 5, 2, 4, 2, 3, 2, 5, 2, 1, 4, 3, 4, 5, 3, 1, 3, 1, 2, 2, 4, 2, 5, 2, 2, 5, 4, 4, 1, 3, 4, 3, 4, 3, 4, 5}

    Returns: 45

  44. 1

    1

    {1}

    Returns: 1

  45. 439

    357

    {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50}

    Returns: 49

  46. 1

    1

    {1}

    Returns: 1

  47. 454

    221

    {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50}

    Returns: 46

  48. 326

    109

    {9, 13, 6, 6, 6, 16, 16, 16, 10, 16, 4, 3, 10, 8, 11, 17, 12, 5, 7, 8, 7, 4, 15, 7, 14, 2, 2, 1, 17, 1, 7, 7, 12, 17, 2, 9, 7, 1, 8, 16, 7, 4, 16, 2, 13, 3, 13, 1, 17, 6 }

    Returns: 15

  49. 10

    10

    {20 }

    Returns: 1

  50. 10

    10

    {5, 5, 5 }

    Returns: 3

  51. 1

    1

    {50, 50 }

    Returns: 2

  52. 19

    12

    {12, 9, 15, 1, 6, 4, 9, 10, 10, 10, 14, 14, 1, 1, 12, 10, 9, 2, 3, 6, 1, 7, 3, 4, 10, 3, 14 }

    Returns: 22

  53. 10

    7

    {3, 3, 3, 3, 3 }

    Returns: 4

  54. 2

    2

    {1, 1 }

    Returns: 2

  55. 20

    10

    {15, 15 }

    Returns: 2

  56. 2500

    2500

    {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }

    Returns: 50

  57. 100

    63

    {12, 34, 23, 45, 34 }

    Returns: 3

  58. 50

    40

    {49, 10 }

    Returns: 1

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: