MysticAndCandies
SRM 608 · 2013-12-22 · by rng_58
SRM 608 · 2013-12-22 · by rng_58 · Math
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:
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 theint s C and X, and the int[] s low and high.
Return the smallest number of boxes mystic_tc may choose.
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 low[i] 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
Constraints
- low and high will contain between 1 and 50 elements, inclusive.
- low and high will contain the same number of elements.
- Each element of low and high will be between 1 and 10,000,000, inclusive.
- For each i, high[i] will be greater than or equal to low[i].
- C will be between the sum of all elements of low and the sum of all elements of high, inclusive.
- X will be between 1 and C, inclusive.
Examples
0)
15
12
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}
Returns: 3
Here he knows the exact number of candies in each box. The best strategy is to open boxes 2, 3, and 4 (0-based indices). This way he will get 3+4+5 = exactly 12 candies.
1)
60
8
{5, 2, 3}
{49, 48, 47}
Returns: 2
Open box 0 and box 2.
2)
58
30
{3, 9, 12, 6, 15}
{8, 12, 20, 8, 15}
Returns: 2
Open box 2 and box 4.
3)
15332074
11335384
{663309, 1576013, 1362582, 1301332, 1179780, 1505690, 2559372, 2546878}
{2024137, 2210961, 2444442, 2934786, 3470826, 2038099, 2595278, 3454584}
Returns: 7
4)
61417010
11111585
{1555959, 1395093, 460858, 297481, 942197, 1139062, 397459, 172960, 1828543, 588657, 1743011, 331370, 859276, 177404, 498886, 287026, 830838, 151876, 539393, 181170, 748592, 1239008, 2061806, 970607, 1503050, 886266, 281903, 327908, 1002223, 466731, 410800, 1297600, 1498774, 596691, 250986, 552188, 2356868, 520075, 1526253, 671257, 1188185, 1029074, 1871859, 1764730, 951012, 1030391, 1216433, 2551940, 1215789, 827680}
{2022927, 2224211, 1397776, 400859, 966034, 1365729, 1636894, 2464090, 2418389, 1077051, 2540093, 548474, 962704, 1114948, 963904, 364091, 1859203, 2602565, 2116599, 1704501, 2513185, 2289410, 2278827, 1181048, 2403737, 1297251, 2143945, 1387390, 1599054, 472031, 1787984, 2550663, 1514676, 806425, 590507, 1922573, 2380000, 2137909, 2388202, 1027133, 2302353, 2524664, 1897474, 2108876, 1101160, 2324498, 1217524, 2563846, 1738784, 2118559}
Returns: 6
Submissions are judged against all 81 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MysticAndCandies with a public method int minBoxes(int C, int X, vector<int> low, vector<int> high) · 81 test cases · 2 s / 256 MB per case