Troubling Times

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Alex takes the entire Komputer Kids Klub onto a field trip through time and space. Being all smart and powerful, Alex leads the club into his time machine he invented. However, since Alex is also a procrastinator, he waited until the last second, finishing the time machine just minutes before the club starts, not leaving him enough time to figure out how to make the machine work efficiently.

Alex's time machine works by jumping forward and back through time in regular intervals. For example, the time machine can be configured to jump in intervals of 4 days, which means the time machine is able to travel forward 4 days with at least 1 jump, travel forward 8 days with at least 2 jumps, or travel backward 16 days with at least 4 jumps.

Obviously tired from the hard work put into making the time machine, Alex asks you to help him determine the optimal interval to use to get to the destination time.

His time machine has N different interval options that can be used, and he wishes to take the club to D days into the future, whereas negative D signifies travelling to the past. He wants you to tell him what is the lowest number of jumps the machine has to perform to reach D. Be aware, once an interval is chosen, it cannot be changed. Also, there might be times when D cannot be reached with the available intervals, in that case, output This is not the best time for a trip..

Input Specification

The first line of the input will contain two integers N (1 \le N \le 10^4), representing the number of different interval options, and D (-10^4 \le D \le 10^4), the destination time.

The next line will contain N integers denoting the length of each of the different interval option.

Output Specification

Output an integer J, the minimum number of jumps the machine has to perform to reach D, or This is not the best time for a trip. if the destination is unreachable.

Sample Input 1

5 -10
1 2 3 4 5

Sample Output 1


Explanation 1

With the interval 5, -10 can be reached with 2 jumps.

Sample Input 2

2 10
3 7

Sample Output 2

This is not the best time for a trip.

Explanation 2

10 cannot be visited no matter whether you choose 3 or 7 as the interval.