Fișierul intrare/ieșire tower.in, tower.out Sursă Shumen 2016 Juniori
Autor autor necunoscut Adăugată de avatar spatarel Spatarel Dan-Constantin spatarel
Timp de execuție pe test 0.6 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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 h1, h2, .., hN.
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.

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.

În exemplu putem observa că mesajele sunt primite de clădirile 2, 5, 6 și 9.
Scrieți un program care să afișeze care este numărul maxim de clădiri care pot să primească mesajele. Ca date de intrare o sa aveți înalțimile cladirilor și înalțimea turnului. Trebuie să vă gandiți care este locul optim pentru construirea turnului.

Date de intrare

Fișierul de intrare tower.in conține pe prima linie două numere întregi pozitive, separate de un spațiu: N care reprezintă numărul de clădiri și H care reprezintă înalțimea turnului.
Fișierul conține pe a doua linie N numere întregi pozitive, separate de spații care reprezintă înalțimile clădirilor din oraș, ordonate în funcție de numărul de ordine al clădirilor (de la 1 la N).

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.

Restricții

  • 1 ≤ N ≤ 1 000 000
  • În 30% din teste N ≤ 1 000
  • 1 ≤ înalțimea fiecarei clădiri și înalțimea turnului ≤ 109

Exemplu

tower.in tower.out
12 180
200 170 130 90 150 140 40 30 100 160 50 110
5

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii