Rebots elàstics P21399

Statement

0.60

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?

0.40

(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)(13.5,140)1 (52,143.5)(49.5,140)2 (76,143.5)(73.5,140)3 (88,143.5)(85.5,140)4 (124,143.5)(121.5,140)5

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

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

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

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

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

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

(40,3.5)(37.5,0)1 (64,3.5)(61.5,0)2 (76,3.5)(73.5,0)3 (112,3.5)(109.5,0)4 (124,3.5)(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 \ge 1$ , el nombre de preguntes sobre aquest cas, seguit de $p$ parells d’enters $i$ i $t$ . Assumiu $1 \le n \le 10^4$ , $n < L \le 10^6$ , $1 \le i \le n$ , i $0 \le t \le 10^8$ .

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

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++