00222 - Budget Travel
(Gilbert Lee)

#include <stdio.h>

typedef struct{
  double d, c;
} Station;

Station s[55];
double costs[55];
double dist, cap,  mpg, maxdist;
int n;

double min(double a, double b){ return a < b ? a : b;}


/* Best solution after filling up at station x */
double GetCost(int x){
  int i, found, last;
  double addon;
  double delta;

  if(costs[x] != -1) return costs[x];
  costs[x] = 0;
  if(dist-s[x].d > maxdist){
    addon = 9999999;
    found = 0;
    last = x+1;
    for(i = x+1; i <= n; i++){
      delta = s[i].d - s[x].d;
      if(delta < maxdist/2.0){
        last = i;
        continue;
      }
      if(delta > maxdist) break;
      found = 1;
      addon = min(addon, (delta*s[i].c)/(mpg*100.0) + 2.00 +GetCost(i));
    }
    if(!found){
      addon = min(addon, (delta*s[last].c)/(mpg*100.0) + 2 + GetCost(last));
    }
    costs[x] = addon;
  }
  return costs[x];
}


int main(){
  int tnum =1, i;

  while(scanf("%lf", &dist) == 1 && dist != -1){
    printf("Data Set #%d\n", tnum++);
    scanf("%lf %lf %lf %d", &cap, &mpg, &s[0].c, &n);
    maxdist = cap*mpg;
    s[0].d = 0;
    s[0].c -= 2.00;
    costs[0] = -1;
    for(i = 1; i <= n; i++){
      scanf("%lf %lf", &s[i].d, &s[i].c);
      costs[i] = -1;
    }
    printf("minimum cost = $%.2f\n", GetCost(0)+s[0].c+2);
  }
  return 0;
}