Many thanks to Clive Fraser for this new puzzle from the land of Erehwon :)
The kingdom of Erehwon has a grid system of roads. These are named X-roads and Y-roads. The X-roads all run from north to south, while the Y-roads all run from east to west. Both sets of roads are numbered from 0 at the origin of the grid system. There are W X-roads, numbered from 0 to W-1. There are H Y-roads numbered from 0 to H-1.
Wherever two roads meet or cross there is a toll booth. The toll payable at a toll booth is dependent on the two roads which meet at that point. Every road has a particular toll which is payable at every toll booth along the road. When arriving at a toll booth two separate tolls are payable. One is the toll for the X-road; the other is the toll for the Y-road.
In this problem you will be given the toll charges for each of the X-roads and for each of the Y-roads. You are asked to find the minimum cost of the toll charges in travelling between the point (0,0) where X-road 0 meets Y-road 0 and the point (W-1,H-1) where X-road W-1 meets Y-road H-1. Note that two toll charges are payable at each toll booth on the route and that this includes the toll booths at the start and end of the route.
The full problem requires a large number of toll charges, so we will use the Linear Congruential Generator to generate these. This has been used before in Code Abbey problems. A random value X(n) is generated using the formula:
X(n) = (A * X(n-1) + C) % M
In this problem we will use the values A = 445, C = 700001 and M = 2097169. Note that % M means the remainder after dividing by the modulus value of M. The value X(n-1) is the previous random value to be generated by this expression. In order to generate the first random value X(1) we need to be given a value for X(0) which is called the seed for the generator. This value will be supplied as part of the data for the problem.
The example below is made deliberately small (W = 9 and H = 10) so that you can use it to test your ideas. The values of W and H in the actual problem will be very much larger (but always less than 180,000). For this example, the random seed X(0) is taken to be 86 (it will not be 86 in the actual problem). Since W = 9 we need to generate 9 toll charges for the X-roads 0 to 9. The first 9 values generated for X(n) are: 738271, 2072232, 88881, 405835, 940042, 1682060, 527368, 495833, 1142941. These will be used as the toll charges for the X-roads. Since H = 10 the next 10 random numbers will be used as toll charges for Y-roads 0 to 9. The values generated are: 1793848, 2038141, 1695738, 322571, 1636604, 1271138, 120781, 2018321, 1264514, 1367439.
The table below shows the positions of the 90 toll booths in the grid. The positions are marked with the total toll to be paid. This is the sum of the tolls for the two roads meeting at this position. The table shows the starting point (0,0) at the bottom left and the destination (9,10) at the top right.
9 2105710 3439671 1456320 1773274 2307481 3049499 1894807 1863272 2510380
8 2002785 3336746 1353395 1670349 2204556 2946574 1791882 1760347 2407455
7 2756592 4090553 2107202 2424156 2958363 3700381 2545689 2514154 3161262
6 859052 2193013 209662 526616 1060823 1802841 648149 616614 1263722
5 2009409 3343370 1360019 1676973 2211180 2953198 1798506 1766971 2414079
4 2374875 3708836 1725485 2042439 2576646 3318664 2163972 2132437 2779545
3 1060842 2394803 411452 728406 1262613 2004631 849939 818404 1465512
2 2434009 3767970 1784619 2101573 2635780 3377798 2223106 2191571 2838679
1 2776412 4110373 2127022 2443976 2978183 3720201 2565509 2533974 3181082
0 2532119 3866080 1882729 2199683 2733890 3475908 2321216 2289681 2936789
0 1 2 3 4 5 6 7 8
At the point (0,0) the toll payable is 2532119. This is the sum of 738271 and 1793848 which are the tolls for X-road 0 and Y-road 0. Similarly, at the point (8,9) we have a toll of 2510380 = 1142941 + 1367439 for the tolls on X-road 8 and Y-road 9. One route which minimises the total cost of travelling from (0,0) to (8,9) is:
(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 4), (2, 5), (2, 6),
(3, 6), (4, 6), (5, 6), (6, 6), (7, 6), (7, 7), (7, 8), (7, 9), (8, 9).
The corresponding total cost is 28207999.
Input/Output description: The first and only line of the input data will contain 3 space separated integers. These are W, H and X(0), the number of X-roads, the number of Y-roads and the random seed X(0) respectively. You need to determine the minimum cost of travelling from (0,0) to (W,H).
Example 1:
input:
9 10 86
answer:
28207999
Example 2:
input:
173838 165316 1734334
answer:
355273684171