Oglinzi

problema/oglinzi

== include(page="template/taskheader" task_id="oglinzi") ==
 
Se considera un sistem de coordonate 2D. In origine, se afla un laser ce emite o raza de lumina la 45 de grade (vezi exemplul). 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{~1~} < r{~1~} < l{~2~} < r{~2~} < ... < 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$.
 
h2. 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~}*.
 
 
h2. Date de ieşire
 
În fişierul de ieşire $oglinzi.out$ afisati $T$ linii cu raspunsurile pentru cele $T$ teste.
 
h2. Restricţii
 
* $1 &le; T &le; 10$
* $1 &le; N &le; 200$
* $1 &le; h{~i~}, H &le; 400$
* {$0 &le; l{~1~} < r{~1~} < l{~2~} < r{~2~} < ... < l{~n~} < r{~n~} < L &le; 400$}
* Un ecran aflat la inaltimea $1$ nu poate fi mutat in jos.
* Daca raza de lumina atinge o oglinda in unul din colturi, aceasta se va reflecta (vezi exemplul). De asemenea, daca raza de lumina atinge ecranul in capatul de sus, se considera ca a ajuns pe ecran.
 
h2. Exemplu
 
table(example). |_. oglinzi.in |_. oglinzi.out |
| 2
  3 15 1
  4 6 5
  7 8 4
  10 11 5
  1 10 1
  1 2 1
| 2
  Imposibil
|
 
h3. Explicaţie
 
Pentru primul test, solutia optima este mutarea oglinzii 2 cu o pozitie mai jos si a oglinzii 3 cu o pozitie mai sus, conform imaginii. Costul optim este asadar 2.
Pentru cel de-al doilea test, raza de lumina nu va ajunge niciodata pe ecran, indiferent de cum mutam singura oglinda existenta.
 
!problema/oglinzi?oglinzi.png!
 
== include(page="template/taskfooter" task_id="oglinzi") ==

task: oglinzi

public