Rebots elàstics P21399


Statement
 

pdf   zip

thehtml

Teniu una taula de billar de llargada L i amplada 1, i n boles de billar idèntiques de diàmetre 1, etiquetades d’esquerra a dreta amb els números 1, 2, …, n. Inicialment totes les boles es troben en posicions enteres, i la bola 1 es troba a l’esquerra del tot (a la posició 1). Després de colpejar la bola 1, aquesta comença a moure’s cap a la dreta a una velocitat de 1unitat per segon. Suposant que els rebots (tant entre les boles com a la paret esquerra i dreta) són completament elàstics i que no hi ha fregament, a quina posició es trobarà una bola determinada en un cert segon?

(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

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb L i n, seguits de les n posicions de les boles. Totes les posicions són diferents, entre 1 i L, i alguna és 1. A continuació ve p ≥ 1, el nombre de preguntes sobre aquest cas, seguit de p parells d’enters i i t. Assumiu 1 ≤ n ≤ 104, n < L ≤ 106, 1 ≤ i ≤ n, i 0 ≤ t ≤ 108.

Sortida

Per a cada parell de i i t, escriviu la posició de la bola amb etiqueta i al segon t, seguint el format de l’exemple. Escriviu una línia buida després de la sortida de cada cas.

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
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++