Thanks a lot to Clive Fraser for creating this problem!
The country of Erehwon is roughly rectangular in shape. It has borders with other countries to the north and south. There is considerable travel across these borders so a number of border towns have grown up. Two railway lines have been built to provide communication between the border towns. One railway line runs through the towns on the northern border. The other line runs through the towns on the southern border. The east and west sides of the country are characterised by marshlands backed by mountains, so there is no need for any significant communication links here.
Naturally, towns on the northern border need to have good connections to towns on the southern border. To facilitate this, a rail network has been developed. Each connecting line starts at a town on the northern border and ends at a town on the southern border. Some of these new lines cross each other and at each crossing point a new town has grown up. These towns are called crossing towns, to distinguish them from the border towns.
The railway lines which link towns on the northern border to towns on the southern border have only a single connection to each of the border railway lines. These connecting lines may be straight for much of their length but change direction in order to fit better into the local topography. Two such lines may or may not cross. If a pair of lines does have a crossing point, then the same pair of lines will not cross each other again. Any crossing point is restricted to a pair of these connecting lines. There will always be exactly two railway lines passing through any one of the crossing towns. A single border town can be the start (or finish) of several connecting lines going to towns on the other border. It is even possible for a northern border town to be connected by more than one line to a single town on the southern border. In such a situation, the connecting lines will follow different routes and will not cross each other. Not all of the border towns are at the start or finish of a connecting line. From these towns it would be necessary to travel along the border line to reach a suitable connecting line to the other border.
Naturally, all of the border towns and crossing towns have their own distinctive names. However, for the purpose of this problem, we will number each of the northern border towns, starting from 0 and moving from east to west. We will use the same numbering system for towns on the southern border. A particular connecting line can be represented by coordinates (n,s). For example; (0,7) represents the connecting line which runs from town 0 on the northern border to town 7 on the southern border. In this problem you will be given the coordinates of each of the crossing lines. You are asked to find the number of crossing towns in the country of Erehwon.
Since there is a great deal of data in this problem (the coordinates of a very large number of connecting lines), we will use a random number generator to create it, as follows. There will be N connecting lines in total. 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. These will be the numbers of the border towns at the northern and southern ends of the connecting lines.
Consider a simple example with just 8 connecting lines (N = 8). This means that we need 16 random values to provide the border town numbers. 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 16 random numbers needed to create this data. The first values generated for X(n) are 700001 1819434 840897 1603084 1034921 ... We read these values as n1, s1, n2, s2, n3, s3, etc. So the coordinates of the first two connecting lines are (700001, 1819434) and (840897, 1603084).
You should be able to verify that these 8 connecting lines will lead to 10 different intersections and hence 10 crossing towns. The pairs of lines which give rise to these crossing towns are listed below.
(234863, 355586) (404272, 244507)
(234863, 355586) (1648096, 93571)
(395716, 631425) (404272, 244507)
(395716, 631425) (1648096, 93571)
(404272, 244507) (1648096, 93571)
(452828, 880237) (1648096, 93571)
(700001, 1819434) (840897, 1603084)
(700001, 1819434) (1648096, 93571)
(840897, 1603084) (1648096, 93571)
(1034921, 1959835) (1648096, 93571)
The actual problem will use a different random seed and a much larger number of connecting lines. You will need to use the random number generator described above to generate the coordinates (n,s) of each connecting line in turn. You must then find the number of crossing towns in the country. With a good algorithm this should take less than 1 second.
Input/Output description: The first and only line of the input data will contain 2 space separated integers. These are the random seed X(0) and the number of connecting lines. Your answer is a single integer; the number of crossing towns in Erehwon.
Example 1:
input:
0 8
answer:
10
Example 2:
input:
376796 109549
answer:
3003810713