Diferențe pentru problema/tower între reviziile #69 si #64

Tower

tower

== include(page="template/taskheader" task_id="tower") ==

page="template/taskheader" task_id="tower") ==

Orașul _X_ este format din _N_ cladiri, aranjate de la vest la est și numerotate de la 1 la _N_. *Fiecare clădire are o înaltime diferită - un număr întreg, respectiv $h[~1~], h[~2~], .., h[~N~]$*.
Guvernul plănuiește să construiască un turn care să fie în rând cu celelalte clădiri (poate să fie construit înaintea primei clădiri, între oricare două clădiri sau după ultima cladire). Turnul va difuza mesaje catre cetățeni. *Înalțimea turnului trebuie să fie _H_, înălțime care trebuie să fie diferită de înălțimile celorlalte cladiri*.

Din cauza unor idei ciudate ale inginerilor, turnul va putea difuza semnal doar către partea de vest (doar către primele clădiri). Semnalul este de asemenea ciudat - sunt raze transmise orizontal (paralel cu solul, pe care il considerăm o linie dreaptă) și sunt emise din intreaga structură a turnului (de la vârf spre bază). Ne putem imagina că turnul emite o bandă continuă de semnale cu lățimea egală cu înălțimea turnului. Când o rază atinge o clădire, se oprește. *Fiecare clădire primește semnalul utilizând un receptor localizat pe acoperiș*. O clădire primește un mesaj dacă cel puțin o rază ajunge la receptorul ei.

Din cauza unor idei ciudate ale inginerilor, turnul va putea difuza semnal doar către partea de vest (doar către primele clădiri). Semnalul este de asemenea ciudat - sunt raze transmise orizontal (paralel cu solul, pe care il considerăm o linie dreaptă) și sunt emise din intreaga structură a turnului (de la vârf spre bază). Ne putem imagina că turnul emite o bandă continuă de semnale cu lățimea egală cu înălțimea turnului. Când o rază atinge o clădire, se oprește. *Fiecare clădire primește semnalul utilizând un receptor localizat pe acoperiș*. O clădire primește un mesaj dacă ce puțin o rază ajunge la receptorul ei.

Cu alte cuvinte, o clădire cu numărul de ordine _i_ o sa primească mesajele de la turn doar când: clădirea _i_ este situată la vestul turnului; _i_ nu este mai înaltă decât turnul și nu există o altă clădire _j_ intre ele ([_j_] > _i_) care să fie mai mare decât cladirea _i_.

h2. Date de ieșire

Fișierul de ieșire $tower.out$ va conține un singur număr întreg, reprezentând numărul maxim de clădiri care ar putea să primească mesajele dacă turnul se construiește în locul optim.

Fișierul de ieșire $tower.out$ va conține pe un singur rând un singur număr întreg care reprezintă numărul maxim de clădiri care ar putea să primească mesajele dacă turnul se construiește în locul optim.

h2. Restricții
* $1 ≤ _N_ ≤ 1 000 000$

* În $30%$ din teste $_N_ ≤ 1 000$

* În $30%$ din teste $_N_ ≤ 1000$

* $1 ≤$ înalțimea fiecarei clădiri și înalțimea turnului $≤ 10[^9^]$
h2. Exemplu

table(example).
|_. tower.in |_. tower.out |
| 12 180

200 170 130 90 150 140 40 30 100 160 50 110

200 170 130 90 150 140 40 30 100 160 50 110.

| 5
|
h3. Explicație

În imaginea de mai jos este dată poziția optimă pentru turn. Mesajele sunt primite de clădirile: 2, 5, 6, 7 și 8.

În imaginea de mai jos este dată locația optimă pentru turn. Mesajele sunt primite de clădirile : 2, 5, 6, 7 si 8.

!problema/tower?tower2.png!