For this puzzle we are again much obliged to Clive Fraser - many thanks!
The Mysterons live on a planet which is shaped like a doughnut, i.e. a ring with a hole through the middle.
The technical term for this shape is a torus. The Mysterons have a communications system of roads which is
loosely based on a grid of squares. There are two sets of roads which intersect each other at right angles.
At each intersection there is a major settlement. Each road is a continuous loop going completely around the
planet. The two sets of roads are referred to as the Y roads and the X roads. The Y roads are all roughly
parallel to each other and equally spaced from each other. The same is true of the set of X roads. Each of
the Y roads lies in a plane which is parallel to the plane of the ring of the doughnut. Each of the X roads
is in a plane perpendicular to this and passes through the hole in the middle of the doughnut. The net affect
for someone on the surface of the planet is that the Y and X roads form a grid of squares which is somewhat
distorted by the fact that the roads have to bend to fit in with the surface topology and because the
settlements (and hence the road intersections) need to be sited in strategic positions.
There are 40 Y roads and 40 X roads on the planet. Being mathematically minded, the Mysterons use
x,y coordinates to number all of the road intersections (and hence settlements). The main settlement is
naturally at coordinates 0,0. The X coordinates and the Y coordinates range from 0 to 39. However,
the roads are continuous loops. If we follow one of the Y roads the intersections will go through successive
values of x from 0, 1, 2, ... 37, 38, 39 and then back to 0 again. The same is true for the X roads.
Distances between adjacent intersections are all either 1, 2, 3 or 4 clicks (the local unit of distance).
Each Y road and each X road has 40 separate sections between adjacent intersections. There are 80,
roads which means that there are 3200 road sections on the planet. There are 1600 intersections and hence
1600 settlements.
The Mysterons frequently need to travel between two settlements. They will usually want to use the shortest
route between the two settlements. However, it is frequently the case that there are several routes having the
same shortest length. In this problem we are concerned with travel from the main settlement (at 0,0) to one
of the other settlements. We want to know the shortest distance between the two settlements but also the number
of different routes between these two settlements which have this value.
Clearly we need to know the lengths of each of the 3200 road sections. Since these need to be different for
each person solving the problem, we will use a random number generator to create them, as follows. The
Linear Congruential Generator
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 formula above creates a reasonable sequence of roughly random values. However, these are much too
large for this problem. For each random value X(n) we will create the required length of road section R(n)
using the formula:
R(n) = 1 + X(n) %4
It should be obvious that the values of R(n) can only be 1, 2, 3 or 4. The Mysteron planet has 40
Y roads and 40 X roads. Let us refer to this as Size 40. In order to provide an example to illustrate the
problem it makes sense to choose a much smaller Size. Let us choose Size 5. So our example planet has just 5
Y roads and 5 X roads, 25 intersections and 50 road sections. If we take the random seed X(0) to be 0
(it will not be 0 in the actual problem) then we can generate the 50 random numbers needed to create the
road sections. This sequence is 700001, 1819434, 840897, 1603084, 1034921, 1959835, ...,
1943705, 1615098. When we apply the second formula to get the lengths of the road sections, the sequence
becomes 2, 3, 2, 1, 2, 4, ..., 2, 3. We will assign these values to road sections in the following order.
We will begin with the Y roads in order from y = 0 to y = 4. For each Y road we will fill the values of
the 5 sections, again in order. Having completed the Y roads we assign values to the X roads in a similar
manner. The following table shows how the 50 road section lengths are to be assigned.
2 3 2 1 2 y = 0 sections with x values 0 - 1 - 2 - 3 - 4 - 0
4 1 4 1 2 y = 1 sections with x values 0 - 1 - 2 - 3 - 4 - 0
4 3 1 4 1 y = 2 sections with x values 0 - 1 - 2 - 3 - 4 - 0
2 1 1 2 3 y = 3 sections with x values 0 - 1 - 2 - 3 - 4 - 0
1 4 2 4 3 y = 4 sections with x values 0 - 1 - 2 - 3 - 4 - 0
4 4 3 2 2 x = 0 sections with y values 0 - 1 - 2 - 3 - 4 - 0
4 3 3 2 4 x = 1 sections with y values 0 - 1 - 2 - 3 - 4 - 0
1 3 1 4 4 x = 2 sections with y values 0 - 1 - 2 - 3 - 4 - 0
2 3 4 4 1 x = 3 sections with y values 0 - 1 - 2 - 3 - 4 - 0
3 3 2 2 3 x = 4 sections with y values 0 - 1 - 2 - 3 - 4 - 0
The first line of the table shows that the second section length is 3. This section is between the x values
of 1 and 2. The y value for this road is 0 so the road section from 1,0 to 2,0 has a length of 3.
Notice that the final (5th) section of this road has length 2 and connects x values 4 and 0 or
coordinates 4,0 to 0,0.
This example is sufficiently small for you to try it out on paper. If we consider a journey from the main
settlement (0,0) to the settlement at 4,3 we can soon establish that the shortest route between the two
settlements has a length of 7 clicks. There are 3 separate routes between these two settlements which have
the same shortest length of 7 clicks. These are:
0,0 --> 0,4 --> 0,3 --> 4,3
0,0 --> 4,0 --> 4,4 --> 4,3
0,0 --> 0,4 --> 4,4 --> 4,3
Input/Output description: The first line of the input data will contain two space separated integers,
the random seed X(0) and the problem Size (which will be 40 for the actual problem). The next line
contains a single integer N for the number of sets of test data. N lines will follow. Each line contains 2
space-separated integers for the x,y coordinates of the destination settlement. For each set of test data find
the shortest distance between the main settlement and the destination settlement. You also need to find the
number of different routes which have this shortest distance. Give the distance and number of routes, separated
by a space. Combine all answers on a single line, separated by single spaces.
Example:
input:
0 5
4
4 3
2 2
3 2
4 4
answer:
7 3 7 1 8 2 5 2