Fișierul intrare/ieșire | tower.in, tower.out | Sursă | Shumen 2016 Juniori |
---|---|---|---|
Autor | autor necunoscut | Adăugată de | Spatarel Dan-Constantin • spatarel |
Timp de execuție pe test | 0.6 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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.