This problem was created by Clive Fraser - many thanks for it!
It is a well-known fact that steel ball bearings rolling on a steel track move with very little friction and that collisions between the ball
bearings are almost perfectly elastic. In this problem we are going to remove the friction entirely and have collisions which are perfectly
elastic. The problem has a large number of ball bearings rolling on a very long, horizontal, frictionless steel track. All ball bearings move
at a speed of 1 metre per second. We will make a further simplification that the size of the ball bearings can be ignored. This means that ball
bearings can be taken to be in the same position when they collide. Because the collisions are perfectly elastic, the ball bearings effectively
bounce off each other and continue to move with speeds of 1 metre per second, but now in the opposite direction to their previous motion.
The track starts at a position designated by 0. The track continues to the right of this position until it reaches the other end at a distance
of E metres from the left hand end. If a ball bearing moves beyond either end of the track it falls into a collecting device and takes no
further part in the movement of the other ball bearings. Consider the following example. At time 0 seconds we have ball bearing A at
position 40 metres on the track, moving to the right (at 1 m/s) and ball bearing B at 50 metres on the track, moving to the left (at 1
m/s); with no other ball bearings between them. At time 5 seconds both ball bearings will reach the 45 metre position on the track. A
collision must take place so ball bearing A will now continue moving at 1 m/s but to the left, while ball bearing B moves at 1 m/s to the
right. Note the fact that the size of the ball bearings has been ignored (as stated above).
In the problem you will be given the positions in metres from the 0 position (at time 0) of all ball bearings on the track, as well as the
position of the right hand end of the track (E). The right hand end of the track will always be 20 metres to the right of the starting
position of ball bearing N. You will also be given the directions (left or right) in which each of the ball bearings is moving. The speeds
of motion will always be 1 m/s. The subsequent motion is likely to contain a large number of collisions. The N ball bearings on the track
are clearly marked with their numbers 1 to N (from left to right along the track). You will be given a time (in seconds) after the start,
when you will be asked to describe the motion of several selected ball bearings. The numbers of these ball bearings will be given as part of
the problem data. For each of these specified ball bearings you must determine 3 things about the ball bearing at the given time. These are:
It is guaranteed that all specified ball bearings will still be on the track at the given time. If one of the specified ball bearings is involved in a collision at the given time then this collision should be counted in the total for that ball bearing and the direction of motion should be the direction after the collision.
For the actual problem we will use the Linear Congruential Generator to generate the positions
and directions of motion of each of the ball bearings. 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 (N = 10) so that you can use it to test your ideas. The number of ball bearings in the actual
problem will be very much larger. For this example, the random seed X(0) is taken to be 0 (it will not be 0 in the actual problem). We
need 10 numbers for the ball bearings numbered 1 to 10. The first 10 values generated for X(n) are
700001 1819434 840897 1603084 1034921 1959835 404272 244507 452828 880237
We will use each number to generate both a position and direction of motion as follows. If the number is odd the ball bearing is moving to the
right. If the number is even, the ball bearing is moving to the left. The same number is used to generate the position. The position for ball
bearing n is given by P(n) = P(n-1) + X(n)%10 + 10. We will take P(0) to be 0. This gives the position of ball bearing 1 as
P(1) = 0 + (700001 %10) + 10 = 11 and for ball bearing 2 as P(2) = 11 + (1819434 %10) + 10 = 25.
The starting positions (in metres) of the 10 ball bearings (in order) are 11, 25, 42, 56, 67, 82, 94, 111, 129 and 146.
So the right end of the track is at position E = 146 + 20 = 166.
Using L and R for directions, the initial directions of motion of the 10 ball bearings (in order) are R L R L R R L R L R.
After the start, the first few events to take place are as follows:
At 6 seconds balls 6 and 7 collide at a position of 88 metres (so their directions of motion immediately reverse).
At 7 seconds balls 1 and 2 collide at 18 metres. At the same time balls 3 and 4 collide at 49 metres.
At 9 seconds balls 8 and 9 collide at 120 metres.
At 13.5 seconds balls 5 and 6 collide at 80.5 metres.
At 20 seconds ball 10 reaches the right end of the track (166 metres) so is collected and takes no further part in the motion.
If you continue to work through the simulation you should be able to verify that, at 59 seconds ball 5 collides for the 4th time. It
collides with ball 4 at a position of 70 metres and (as a result of the collision) it is now moving to the Right. You should also be able to
verify that (at the same time of 59 seconds) ball 3 is at 35 metres and is currently moving to the Left, having undergone a total of 3
collisions; while ball 8 is at 141 metres and is currently moving to the Right, having undergone a total of 2 collisions.
Input/Output description: The first line of the input data will contain 3 space separated integers. These are the random seed X(0),
the problem size N (the number of ball bearings) and the time T (in seconds after the start) when you need to determine data for the
selected ball bearings. The second line of the input data contains a single integer M, which is the number of selected ball bearings. The
final line of the input data contains M space-separated integers. These are the numbers of the selected ball bearings. For each of the
selected ball bearings (at the time T) you need to determine the position P (in metres from the start of the track), the number of
collisions C undergone by this ball bearing up to (and including) the time T, and the direction of motion D (given as L or R). For
each selected ball bearing give your answer as P C D, separated by single spaces. Combine the answers for all ball bearings into a single
string, separated by spaces.
Example:
input:
0 10 59
3
3 5 8
answer:
35 3 L 70 4 R 141 2 R