trains.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 struct tariff { int kmax, price; };
   6
   7 struct tariff tar[] = {
   8   { 10, 6 },
   9   { 15, 8 },
  10   { 20, 11 },
  11   { 25, 13 },
  12   { 30, 16 },
  13   { 35, 19 },
  14   { 40, 22 },
  15   { 50, 27 },
  16   { 60, 32 },
  17   { 70, 38 },
  18   { 80, 43 },
  19   { 90, 48 },
  20   { 100, 53 },
  21   { 110, 58 },
  22   { 120, 62 },
  23   { 140, 72 },
  24   { 160, 82 },
  25   { 180, 92 },
  26   { 200, 101 },
  27   { 225, 114 },
  28   { 250, 126 },
  29   { 275, 138 },
  30   { 300, 148 },
  31   { 350, 170 },
  32   { 400, 192 },
  33   { 450, 214 },
  34   { 500, 236 },
  35   { 550, 258 },
  36   { 600, 278 },
  37   { 650, 298 },
  38   { 700, 318 },
  39   { 99999, 342 }
  40 };
  41
  42 int ftar(int km)
  43 {
  44   int t;
  45   for(t=0; tar[t].kmax < km; t++)
  46     ;
  47   return t;
  48 }
  49
  50 int lo(int t)
  51 {
  52   return t ? tar[t-1].kmax+1 : 0;
  53 }
  54
  55 #define hi(t) tar[t].kmax
  56 #define pri(t) tar[t].price
  57
  58 int main(int argc, char **argv)
  59 {
  60   int km, t, orp, l, h;
  61
  62   if (argc != 2)
  63     {
  64       fprintf(stderr, "Usage: %s <km>\n", argv[0]);
  65       return 0;
  66     }
  67   km = atol(argv[1]);
  68   if (km > 10000)
  69     km = 10000;
  70   t = ftar(km);
  71   printf("Original: %d-%d %d\n", lo(t), hi(t), pri(t));
  72   orp = pri(t);
  73   while (--t >= 0)
  74     {
  75       int l0 = km - hi(t);
  76       int h0 = km - lo(t);
  77       l = ftar(l0);
  78       h = ftar(h0);
  79 //    printf("Trying %d-%d %d-%d\n", lo(t), hi(t), l0, h0);
  80       while (l <= h)
  81         {
  82           int p = pri(t) + pri(l);
  83           int L = lo(l) < l0 ? l0 : lo(l);
  84           int H = hi(l) > h0 ? h0 : hi(l);
  85 //        printf("Combined %d-%d %d-%d: p=%d\n", lo(l), hi(l), L, H, p);
  86           if (p < orp)
  87             printf("::: %d-%d(%d) + %d-%d(%d) = %d (saved %d)\n",
  88                    L, H, pri(l),
  89                    lo(t), hi(t), pri(t),
  90                    p, orp - p);
  91           l++;
  92         }
  93     }
  94
  95   return 0;
  96 }