Fişierul intrare/ieşire:tower.in, tower.outSursăShumen 2016 Juniori
AutorAutor NecunoscutAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test0.6 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.intower.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 sa te autentifici pentru a trimite solutii. Click aici