Trip

• Problem Description

  
  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

• Test Case 1

  
  Input (stdin)

  6 3
  
  0
  
  1
  
  3
  
  4
  
  7
  
  10
  
  

  Expected Output

  3 2

• Test Case 2

  
  Input (stdin)

  5 3
  
  0
  
  1
  
  2
  
  4
  
  5
  
  

  Expected Output

  1 1

• Program

• #include <stdio.h>
  #define X 1000000007
  int x[1000000],y[1000000],z[1000000];
  int main()
  {
   int r,s,i,j,k;
   long int c;
   scanf("%d %d",&r,&s);
   for(i=0;i<r;i++)
   scanf("%d",&x[i]);
   z[0]=1;
   j=k=c=0;
   for(i=1;i<r;i++)
   {
    while(x[i]-x[j]>s)
    c-=z[j++];
    y[i]=y[j]+1;
    while(y[k]==y[j])
    c+=z[k++];
    z[i]=c%X;
   }
   printf("%d %d\n",y[r-1]-1,z[r-1]);
   return 0;
   
  }