Relee
Fie date altitudinile a N puncte, situate în linie dreapta de-a lungul axei Ox, astfel încât ele corespund unor abscise naturale consecutive. Primul punct are abscisa 1. Din acest punct trebuie trimisa o raza laser în ultimul punct (cel de abscisa N). Raza se propaga doar în linie dreapta. Pentru a "ocoli" punctele având altitudini care împiedica trecerea razei, în anumite puncte se monteaza relee care schimba unghiul sub care se propaga raza, cu scopul ca ea sa poata trece de vârfurile care se afla în drumul ei. Releele se vor monta în oricare dintre punctele date, mai putin în primul punct, de unde raza poate porni sub orice unghi si în ultimul punct unde raza poate fi receptionata sub orice unghi.
S-a observat ca daca în anumite puncte releul se monteaza pe un pilon, numarul releelor necesare se poate micsora. Toti pilonii care se vor monta au aceeasi înaltime data H.
Cerinta
Determinati numarul minim de relee pentru ca raza sa ajunga din punctul initial în cel final, precum si punctele în care acestea se vor monta. În cazul în care exista mai multe solutii cu acelasi numar minim de relee, se va alege cea cu numar minim de piloni.
Date de intrare
Fisier de intrare: RELEE.IN
Linia 1: N H
Linia 2: A1 A2 ... AN
Date de iesire
Fisier de iesire: RELEE.OUTLinia 1:
NRreleeLinia 2:
NRpiloniLinia 3:
C1 C2 ... CNRreleeLinia 4:
D1 D2 ... DNRpiloniRestrictii
Exemplu
RELEE.IN
RELEE.OUT
Timp maxim de executie/test: 2
secunde
1
1
7
4
Liniile punctate reprezinta altitudinea punctelor date.
Releu fara pilon se va monta în punctul 7, iar pe pilon în punctul 4.