Fişierul intrare/ieşire:towers.in, towers.outSursăShumen 2016 Seniori
AutorAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test3 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Towers

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.

Se va construi un singur turn. Guvernul ia în considerare K variante pentru construirea turnului. Pentru fiecare variantă se cunsoaşte înalţimea turnului. Cele K variante sunt numerotate de la 1 la K. Fiecare variantă a turnului are înălţimea diferită de înălţimile celorlalte clădirilor din oraş.
Guvernul doreşte să ştie care este numărul maxim de clădiri care ar putea să primească mesajele pentru fiecare din cele K variante inainte de a decide ce variată să aleagă. Aceste calcule ar trebui facute pentru fiecare ofertă ţinând cont de amplasamentul optim al turnului.

Să se scrie un program care să afişeze numărul maxim de clădiri care ar putea să primească mesaje pentru fiecare variantă. Ca date de intrare o să aveţi înalţimile cladirilor şi înalţimile turnurilor pentru fiecare variantă. Trebuie să vă gandiţi care este locul optim pentru construirea fiecărui turn.

Date de intrare

Fişierul de intrare towers.in conţine pe primul rând două numere întregi pozitive, N şi K: N reprezintă numărul clădirilor din oraş şi K reprezină numărul variantelor pentru construirea turnului. Al doilea rând conţine N numere întregi pozitive reprezentând înălţimile clădirilor din oraş ordonate în funcţie de numărul clădirii (de la 1 la N). Al treilea rând conţine K întregi pozitivi reprezentând înălţimile turnurilor.

Date de ieşire

În fişierul de ieşire towers.out se afişează pe un singur rând şi separate prin spaţii, K numere întregi reprezentând numărul maxim de clădiri care ar putea să primească meajele dacă amplasamentul turnului este optim.

Restricţii

  • 1 ≤ N ≤ 1 000 000
  • 1 ≤ K ≤ 100 000
  • 1 ≤ înalţimea fiecarei clădiri şi înalţimea turnului ≤ 109
  • În 20% din teste N ≤ 1 000 şi K ≤ 20
  • În 30% din teste N ≤ 1 000 000 şi K ≤ 20

Exemplu

towers.intowers.out
16 3
200 170 155 90 150 140 40 30 185 160 50 110 80 15 70 35
165 180 120
5 6 4

Explicaţie

Clădirile care primesc mesaje sunt: 10, 12, 13, 15 şi 16.

Clădirile care primesc mesaje sunt: 2, 3, 5, 6, 7 şi 8.

Clădirile care primesc mesaje sunt: 12, 13, 15 şi 16.

Trebuie sa te autentifici pentru a trimite solutii. Click aici