]> mj.ucw.cz Git - misc.git/blob - trains.c
Merge with git+ssh://git.ucw.cz/home/mj/GIT/misc.git
[misc.git] / 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 }