Fişierul intrare/ieşire:turnuri.in, turnuri.outSursăLot 2008 - Piatra Neamt, Baraj3
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.45 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Turnuri

Andreea si Ioana au N turnuri de diferite inaltimi. Ele aseaza turnurile pe masa, in linie dreapta si numeroteaza turnurile de la 1 la N de la cel mai din stanga la cel mai din dreapta. Cele doua fete plaseaza apoi in fiecare turn cate un soldatel de jucarie. Soldatelul din turnul i poate vedea orice turn j aflat in stanga sa (j<i) daca intre cele doua turnuri nu exista un turn k (j<k<i) astfel incat turnul k are o inaltime strict mai mare decat turnul i. Definim vizibilitatea totala a soldateilor ca fiind suma numarului de turnuri pe care le vede fiecare soldatel. Pentru fiecare turn i (1≤i≤N) cele doua fete se intreaba care ar fi vizibilitatea totala a soldateilor daca ar elimina de pe masa turnul i. Determinati suma vizibilitatilor totale ale soldateilor ce se obtin eliminand pe rand fiecare dintre cele N turnuri.

Date de intrare

Prima linie a fisierului de intrare turnuri.in va contine numarul natural N, reprezentand numarul de turnuri. Urmeaza N linii, pe linia i+1 aflandu-se inaltimea turnului i.

Date de iesire

Fisierul de iesire turnuri.out va contine o singura linie pe care va fi scrisa suma vizibilitatilor totale ale soldateilor, vizibilitati totale ce se obtin eliminand pe rand fiecare dintre cele N turnuri.

Restrictii

  • 1 ≤ N ≤ 1 000 000
  • Inaltimile turnurilor sunt numere naturale din intervalul [1,2 000 000 000] si sunt distincte doua cate doua

Exemplu

turnuri.inturnuri.out
4
7
10
2
5
10

Explicatie

Daca eliminam turnul 1 se obtine sirul de turnuri 10, 2, 5. Vizibilitatea soldatelului din turnul cu inaltimea 2 este 1, iar vizibilitatea celui din turnul cu intaltimea 5 este 2. Suma vizibilitatilor totale obtinute prin eliminarea turnului 1, 2, 3, respectiv 4 este 3+3+2+2=10.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content