Woburn Challenge 2017-18 Round 2 - Junior Division
Problem 3: Escaping the Mines
Pursued by a swarm of goblins, the N (1 ≤ N ≤ 9) members of the Fellowship of the Ring are trying to escape from the Mines of Moria. To do so, they must cross a chasm which is M (1 ≤ M ≤ 10) metres wide. The i-th member of the Fellowship can jump a distance of up to Ji (1 ≤ Ji ≤ 10) metres. Therefore, they can only cross the chasm by themselves if they can jump a distance of at least M metres.
Fortunately, if someone is able to jump over the chasm themselves, they can also carry at most one other person along with them. This does not affect their jumping distance. Unfortunately, there isn't enough time for them to then jump back and carry yet another person across.
Assuming that the Fellowship works together, what's the maximum number of its members who can end up getting across the chasm and escaping the Mines of Moria?
Input Format
The first line of input consists of two space-separated integer, N and M.
The next line consists of N space-separated integers, J1..N.
Output Format
Output a single integer, the maximum number of Fellowship members who can escape.
Sample Input
5 6 3 6 4 1 10
Sample Output
4
Sample Explanation
One optimal strategy is for the 2nd member to jump across while carrying the 3rd member, and for the 5th member to jump across while carrying the 4th member. Unfortunately, this leaves the 1st member unable to cross by themselves, but there's no way for the entire Fellowship to escape.
All Submissions
Best Solutions
Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 23, 2018
Author: SourSpinach
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)