PEG Test - Halloween 2014
Problem A: Trick-or-Treat
Ben is going trick-or-treating this Halloween.
Ben only has D minutes of trick-or-treat time. He has planned out a list of N houses to visit. In order to attain the maximum amount of candy possible, he will need to spend time bartering with each household. He knows that the i-th house will require ti minutes of bartering.
Because of his excellent athletic abilities, it will take Ben exactly 1 minute to move between any pair of houses.
Determine the maximum number of houses Ben can visit on Halloween night. Note that he can begin at any house and visit the houses in any order, but will only receive candy from a house at the end of the bartering period.
Line 1 of input contains two integers N, D (1 ≤ N ≤ 10000; 1 ≤ D ≤ 108).
Line 2 of input will have N space-separated integers – the time in minutes it takes to barter with the i-th house. (1 ≤ ti ≤ 10000).
Output a single integer, the greatest number of houses Ben can receive candy from.
Sample Input 1
4 12 4 2 5 4
Sample Output 1
Ben can spend 4 minutes bartering at the first house, move to the second house in 1 minute, spend 2 minutes bartering with the second house, move to the fourth house in 1 minute, and spend 4 minutes bartering at the fourth house. This will take a total of 4 + 1 + 2 + 1 + 4 = 12 minutes.
Sample Input 2
2 10 9 1
Sample Output 2
Ben can spend 9 minutes collecting candy from the first house, but will not have enough time to move to the second house to barter.
Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 07, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3