All submissions for this problem are available.
You are starting out on a long (really long) trip. On the way, there are N gas stations, the locations of which are given as a_1,a_2,...,a_N. Initially you are located at the gas station at a_1, and your destination is at location a_N. Your car can only store enough fuel to travel atmost M units without refilling. You can stop at any station and refill the car by any amount. Now you wish to plan your trip such that the number of intermediate stops needed to reach the destination is minimum, and also how many ways are there to plan your trip accordingly.
The first line two space seperated integers N and M. N lines follow, and the ith line has the value a_i (0 <= a_i <= 1000000000). The input will be such that a solution will always exist.
Output two space seperated integers : The least number of stops, and the number of ways to plan the trip which uses the least number of stops. Output this value modulo 1000000007.
Sample Input :
6 3 0 1 3 4 7 10
Sample Output :
2 <= N <= 1000000 1 <= M <= 1000 a_1 < a_2 < .. < a_N
|Tags||april10, easy, syco|
|Time Limit:||0.192577 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, CS2, PAS fpc, PAS gpc, RUBY, PHP, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, SQL, TEXT|
Fetching successful submissions