Connection Status:
Competition Arena > MysticAndCandiesEasy

MysticAndCandiesEasy

SRM 608 · 2013-12-22 · by rng_58

SRM 608 · 2013-12-22 · by rng_58 · Math
Class Name: MysticAndCandiesEasy
Return Type: int
Method Name: minBoxes
Arg Types: (int, int, vector<int>)
Problem Statement

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.

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
0)
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.

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

2)
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.

3)
26
5
{6, 9, 15, 3, 11, 6, 8, 12}
Returns: 5
4)
168
30
{2, 15, 6, 1, 1, 10, 14, 18, 13, 11, 17, 17, 11, 12, 18, 11, 9, 7}
Returns: 4

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

Coding Area

Language: C++17 · define a public class MysticAndCandiesEasy with a public method int minBoxes(int C, int X, vector<int> high) · 58 test cases · 2 s / 256 MB per case

Submitting as anonymous