Fişierul intrare/ieşire:	oglinzi.in, oglinzi.out	Sursă	Romanian Collegiate Programming Contest 2019
Autor	Stefan Popa	Adăugată de	RCPC2019 •RCPC2019
Timp execuţie pe test	0.5 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Oglinzi

Se considera un sistem de coordonate 2D. In origine, se afla un laser ce emite o raza de lumina la 45 de grade, conform imaginii de mai jos. Axa Ox este o oglinda, astfel ca raza de lumina se va reflecta daca atinge axa Ox.

Mai exista N oglinzi orizontale. Oglinda i este caracterizata de 3 parametri: l_i, r_i si h_i, fiind din punct de vedere geometric un segment intre (l_i, h_i) si (r_i, h_i). Daca raza de lumina atinge o oglinda, va fi reflectata. Oglinzile functioneaza pe ambele parti. Mai mult, intervalele [l_i, r_i] sunt disjuncte si sunt date in ordine crescatoare (l₁ < r₁ < l₂ < r₂ < ... < l_n < r_n).

Dupa toate oglinzile, la x = L > r_n, exista un ecran de inaltime H. Din punct de vedere geometric, acesta este un segment intre (L, 0) si (L, H). Iti doresti ca raza de lumina sa ajunga pe ecran. Pentru asta, poti face mai multe operatii. O operatie consta in a muta o oglinda vertical cu o pozitie (de la h_i la h_i-1 sau h_i+1 ).

Se cere numarul minim de operatii pentru ca raza de lumina sa ajunga pe ecran. In cazul in care acest lucru nu se poate realiza, se va afisa "Imposibil".

Date de intrare

Fişierul de intrare oglinzi.in va contine pe prima linie numarul de teste T. Urmeaza descrierile celor T teste.
Pe prima linie a fiecarui test, se vor afla numerele intregi N, L si H.
Vor urma N linii, linia i continand cele 3 numere intregi ce descriu oglinda i: l_i, r_i si h_i.

Date de ieşire

În fişierul de ieşire oglinzi.out afisati T linii cu raspunsurile pentru cele T teste.

Restricţii

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 200
• 1 ≤ h_i, H ≤ 400
• 0 ≤ l₁ < r₁ < l₂ < r₂ < ... < l_n < r_n < L ≤ 400
• Un ecran aflat la inaltimea 1 nu poate fi mutat in jos.
• Daca raza de lumina atinge o oglinda sau ecranul in unul din colturi, aceasta se va reflecta (vezi exemplul).

Exemplu

Explicaţie

Cum se trimit solutii?