This problem was created by Clive Fraser - many thanks!
John likes hiking in the mountains. He particularly likes being at the top of a mountain with a wide panoramic view. John has made a trip to the
Blackrock mountain range and is considering which of the mountains to climb. The range has some remarkable properties. All of the peaks are
situated on a single straight line and adjacent peaks are separated by exactly 1 kilometre. John asks local advice to find the mountain with
the widest panoramic view. He defines the width of the panoramic view as the distance between the two furthest mountain peaks which he can see
from the peak on which he is standing.
John can only see a mountain if its peak is not obscured by a mountain which is closer to him. In the special case of mountains A, B and C
where mountain B lies between mountains A and C, and the straight line connecting the peaks of A and C passes through the peak of B,
and the line passes through no other mountains between A and C; we consider that John would NOT be able to see mountain C while standing
on the peak of A. For all calculations you should ignore the height of John in comparison with the height of the mountains; in other words
assume that John has zero height.
Since there is a great deal of data in this problem (the heights of a very large number of mountains), we will use a random number generator
to create it, as follows. There will be N mountains in total, numbered 1 to N, from one end of the range.
The Linear Congruential Generator
has been used before in CodeAbbey 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 cannot be used directly for this
problem. For each random value X(n) we will create the required mountain height R(n) using the formula:
R(n) = X(n) % Q where Q = 1000000-abs(500000-k) and k is the number of the mountain. abs is an absolute value
It has been necessary to use this fairly complicated expression in order to get a reasonably realistic mountain range. The value of R(n)
gives the height of the mountain in centimetres. The variation in the size of Q ensures that mountains are more likely to be higher if they
are situated nearer to the centre of the range.
Consider a simple example with just 10 mountains (N = 10); numbered from 1 to 10. This means that we need 10 random values to provide
the height data. 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 10 random
numbers needed to create this data. The first 10 values generated for X(n) are
700001 1819434 840897 1603084 1034921 1959835 404272 244507 452828 880237
When we apply the formula for R(n) we get the following heights for the mountains (numbered 1 to 10).
1 200000
2 319428
3 340894
4 103072
5 34911
6 459817
7 404272
8 244507
9 452828
10 380227
From peak 6 John cannot see peak 1 because mountain 3 blocks the view. He can see peak 2 because mountains 3, 4 and 5 do not block
the view. John cannot see peak 10 because mountain 9 blocks the view. He can see peak 9 because peaks 7 and 8 do not block the view.
So the furthest mountains that John can see from peak 6 are mountains 2 and 9. The distance between these two mountains is 7 km so the
panoramic width is 7. With these 10 mountains it is not possible to do better than this.
The actual problem will use a different random seed and a much larger number of mountains (N = 1000000). You will need to use the random
number generator described above to generate the heights of each mountain in turn. You must then find the mountain peak which has the greatest
panoramic width. You need to find this width and the number of the mountain which John needs to stand on. If there is more than one mountain
with the same largest panoramic width you must give the smallest of these mountain numbers.
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 N of mountains. Your answer is two integers separated by a space. These are the largest panoramic width followed by the
corresponding mountain number.
Example 1:
input:
0 10
answer:
7 6
Example 2:
input:
0 1000000
answer:
417007 346723