WC '17 Contest 2 J3 - Escaping the Mines

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 16M

Problem type
Woburn Challenge 2017-18 Round 2 - Junior Division

Pursued by a swarm of goblins, the N (1 \le N \le 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 \le M \le 10) metres wide. The i^{th} member of the Fellowship can jump a distance of up to J_i (1 \le J_i \le 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 Specification

The first line of input consists of two space-separated integers, N and M.
The next line consists of N space-separated integers, J_{1 \dots N}.

Output Specification

Output a single integer, the maximum number of Fellowship members who can escape.

Sample Input

5 6
3 6 4 1 10

Sample Output


Sample Explanation

One optimal strategy is for the 2^{nd} member to jump across while carrying the 3^{rd} member, and for the 5^{th} member to jump across while carrying the 4^{th} member. Unfortunately, this leaves the 1^{st} member unable to cross by themselves, but there's no way for the entire Fellowship to escape.


There are no comments at the moment.