Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | towers.in, towers.out | Sursă | Shumen 2016 - Seniori |
| Autor | Rusko Shikov | Adăugată de |  Andrei Constantinescu •Andrei1998 |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Towers
Orasul X este compus din N blocuri, ordonate sub forma unei secvente numerotate de la 1 la N, de la vest la est. Fiecare bloc are o inaltime diferita - un numar intreg, respectiv h1, h2, ..., hN. Guvernul planuieste sa construiasca un turn, stiuat in aceeasi secventa cu blocurile (poate sa fie inaltimea primului bloc, intre oricare doua blocuri sau dupa ultimul bloc). Turnul osa transmita mesaje cetatenilor. *Turnul trebuie sa aiba inaltimea H, care trebuie sa fie diferita de toate celelalte inaltimi ale blocurilor.
Din cauza unor idei ingineresti destul de ciudate, turnul va putea transmite semnale doar in vest (spre inceputul secventei de blocuri). Semnalele sunt de asemenea ciudate - acestea sunt unde care traverseaza orizontal (parelele cu solul, pe care le consideram linii drepte) si sunt emise din toata suprafata blocului (de sus in jos). Deci, ne putem imagina ca turnul emite o banda continua de semnale cu latimea egala cu inaltimea turnului. Cand o unda intalneste un bloc, se opreste. *Fiecare bloc primeste semnalele semnalele folosind un receptor localizat in varful acestuia. Un bloc primeste un mesaj daca cel putin o unda atinge receptorul.
Cu alte cuvinte, blocul cu indicele i va primi mesaje de la turn doar atunci cand: blocul i este situat in stanga turnului; i nu este mai inalt decat turnul si nu exista un alt bloc j intre ele ($j$ > i), care este mai inalt decat blocul i.
(Poza)
Uitati-va la exemplul din figura de mai sus: blocurile care receptioneaza mesaje sunt cele cu indicii 2, 5, 6, 9.
Date de intrare
Fişierul de intrare towers.in ...
Date de ieşire
În fişierul de ieşire towers.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| towers.in | towers.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
