oglinzi

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, conform imaginii de mai jos. Axa Ox este o oglinda, astfel ca raza de lumina se va reflecta daca atinge axa Ox.

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".
 
*TODO: adauga imagine*.
 

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

h2. Restricţii
* $1 ≤ T ≤ 10$

* $1 ≤ N ≤ 500$
* $1 ≤ h{~i~}, H ≤ 1000$
* {$0 &le; l{~1~} < r{~1~} < l{~2~} < r{~2~} < ... < l{~n~} < r{~n~} < L &le; 1000$}

* $1 ≤ N ≤ 200$
* $1 ≤ h{~i~}, H ≤ 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 sau ecranul in unul din colturi, aceasta se va reflecta (vezi exemplul).

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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") ==