Elastic collisions P21399


Statement
 

pdf   zip

html

You have a billiard pool L units long and 1 unit wide, and n identical billiard balls of diameter 1, labeled from left to right with the numbers 1, 2, …, n. Initially, all balls are at integer positions, and the ball 1 is at the very left (at the position 1). After striking the ball 1, it moves to the right, with a speed of 1 unit per second. Supposing that the collisions (between the balls as well as against right and left walls) are completely elastic, and that there is no friction, at which position will a given ball be at a given second?

(140,170) (13.5,155)1 (25.5,155)2 (37.5,155)3 (49.5,155)4 (61.5,155)5 (73.5,155)6 (85.5,155)7 (97.5,155)8 (109.5,155)9 (121.5,155)10 (133.5,155)11

(9,151)(1,0)134 (9,136)(1,0)134 (9,131)(1,0)134 (9,116)(1,0)134 (9,111)(1,0)134 (9,96)(1,0)134 (9,91)(1,0)134 (9,76)(1,0)134 (9,71)(1,0)134 (9,56)(1,0)134 (9,51)(1,0)134 (9,36)(1,0)134 (9,31)(1,0)134 (9,16)(1,0)134 (9,11)(1,0)134 (9,-4)(1,0)134

(9,151)(0,-1)15 (9,131)(0,-1)15 (9,111)(0,-1)15 (9,91)(0,-1)15 (9,71)(0,-1)15 (9,51)(0,-1)15 (9,31)(0,-1)15 (9,11)(0,-1)15

(143,151)(0,-1)15 (143,131)(0,-1)15 (143,111)(0,-1)15 (143,91)(0,-1)15 (143,71)(0,-1)15 (143,51)(0,-1)15 (143,31)(0,-1)15 (143,11)(0,-1)15

(2,143.5)(1,0)8 (14,123.5)(1,0)8 (26,103.5)(1,0)8 (50,83.5)(1,0)8 (86,63.5)(1,0)8 (98,43.5)(1,0)8 (122,23.5)(1,0)8 (138,3.5)(-1,0)8

(16,143.5)12(13.5,140)1 (52,143.5)12(49.5,140)2 (76,143.5)12(73.5,140)3 (88,143.5)12(85.5,140)4 (124,143.5)12(121.5,140)5

(28,123.5)12(25.5,120)1 (52,123.5)12(49.5,120)2 (76,123.5)12(73.5,120)3 (88,123.5)12(85.5,120)4 (124,123.5)12(121.5,120)5

(40,103.5)12(37.5,100)1 (52,103.5)12(49.5,100)2 (76,103.5)12(73.5,100)3 (88,103.5)12(85.5,100)4 (124,103.5)12(121.5,100)5

(40,83.5)12(37.5,80)1 (64,83.5)12(61.5,80)2 (76,83.5)12(73.5,80)3 (88,83.5)12(85.5,80)4 (124,83.5)12(121.5,80)5

(40,63.5)12(37.5,60)1 (64,63.5)12(61.5,60)2 (76,63.5)12(73.5,60)3 (100,63.5)12(97.5,60)4 (124,63.5)12(121.5,60)5

(40,43.5)12(37.5,40)1 (64,43.5)12(61.5,40)2 (76,43.5)12(73.5,40)3 (112,43.5)12(109.5,40)4 (124,43.5)12(121.5,40)5

(40,23.5)12(37.5,20)1 (64,23.5)12(61.5,20)2 (76,23.5)12(73.5,20)3 (112,23.5)12(109.5,20)4 (136,23.5)12(133.5,20)5

(40,3.5)12(37.5,0)1 (64,3.5)12(61.5,0)2 (76,3.5)12(73.5,0)3 (112,3.5)12(109.5,0)4 (124,3.5)12(121.5,0)5

Input

Input consists of several cases. Each case begins with L and n, followed by the n positions of the balls. All the positions are different, between 1 and L, and one of them is 1. Then comes q≥ 1, the number of queries about this case, followed by q pairs of integer numbers i and t. Assume 1 ≤ n ≤ 104, n < L ≤ 106, 1 ≤ i ≤ n, and 0 ≤ t ≤ 108.

Output

For each pair of i and t, print the position of the ball with label i at the second t, following the format of the example. Print an empty line after the output for each case.

Public test cases

  • Input

    11 5
6 4 10 1 7
6
1 0
1 1
1 3
5 3
5 6
3 7

2 1
1
4
1 1
1 0
1 10001
1 10000

    Output

    At second 0, ball 1 is at 1.
At second 1, ball 1 is at 2.
At second 3, ball 1 is at 3.
At second 3, ball 5 is at 10.
At second 6, ball 5 is at 11.
At second 7, ball 3 is at 6.

At second 1, ball 1 is at 2.
At second 0, ball 1 is at 1.
At second 10001, ball 1 is at 2.
At second 10000, ball 1 is at 1.
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++