| Fişierul intrare/ieşire: | turnuri4.in, turnuri4.out | Sursă | OJI 2018, Clasa a 10-a |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Bogdan Ciobanu •bciobanu |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Turnuri4
Cel mai nou proiect imobiliar din capitală este compus din N blocuri-turn, construite unul lângă altul, de-a lungul unui bulevard central şi numerotate de la 1 la N. Pentru fiecare turn se cunoaşte numărul etajelor din care este compus acesta şi se mai ştie că nu există două turnuri cu acelaşi număr de etaje. Ultimele norme urbanistice definesc coeficientul de frumuseţe al turnului cu numărul T, ca fiind numărul turnurilor din secvenţa de turnuri care începe cu turnul S, se termină cu turnul D şi are următoarele proprietăţi:
- 1 ≤ S ≤ T ≤ D ≤ N
- numărul etajelor fiecărui turn din secvenţă, cu excepţia turnului T, este mai mic decât numărul de etaje ale turnului T;
- Dacă S ≠ 1 atunci turnul S-1 este cel mai apropiat turn din stânga turnului T, care are un număr de etaje strict mai mare decât turnul T;
- Dacă D ≠ N atunci turnul D+1 este cel mai apropiat turn din dreapta turnului T, care are un număr de etaje strict mai mare decât turnul T;
Coeficientul de frumuseţe al întregului ansamblu de turnuri este suma coeficienţilor de frumuseţe avuţi de turnurile componente. Dezvoltatorul proiectului doreşte să renunţe la unul dintre turnuri şi să construiască în locul acestuia un restaurant subteran, acesta considerându-se un turn cu zero etaje. Dezvoltatorul doreşte să calculeze coeficientul de frumuseţe al ansamblului de turnuri, pentru fiecare posibilă amplasare a restaurantului
Cerinţa
Cunoscând numărul N de turnuri şi numărul etajelor fiecăruia, determinaţi coeficientul de frumuseţe al ansamblului de turnuri pentru toate cele N posibilităţi de amplasare ale restaurantului, pe poziţiile 1, 2,..., N.
Date de intrare
Datele de intrare se citesc din fişierul turnuri4.in, care are următoarea structură:
- pe prima linie se află numărul natural N, reprezentând numărul de turnuri;
- pe a doua linie se află N valori naturale nenule, separate prin câte un spaţiu, reprezentând numărul etajelor turnurilor;
Date de ieşire
Datele de ieşire se vor scrie în fişierul turnuri4.out, pe linii separate, astfel: pe linia i (1 ≤ i ≤ N) se găseşte un număr natural reprezentând coeficientul de frumuseţe al ansamblului dacă restaurantul s-ar construi în locul turnului i.
Restricţii
- 1 ≤ N ≤ 100 000
- Numărul de etaje ale unui turn este un număr natural între 1 şi 1 000 000 000
- Pentru teste în valoare de 30 de puncte, avem N ≤ 100
- Pentru teste în valoare de încă 30 de puncte, avem N ≤ 2 000
- Conform regulamentului OJI, se acordă 10 puncte pentru exemple.
Exemplu
| turnuri4.in | turnuri4.out | Explicaţie |
|---|---|---|
| 7 10 3 1 7 8 6 5 | 19 22 22 22 21 22 22 | Figura 1 este reprezentarea grafică a fişierului de intrare. Dacă restaurantul se construieşte în locul turnului 1 (vezi figura 2), avem următorii coeficienţi de frumuseţe: Restaurantul are coeficientul 1 (el însuşi) Turnul 2 are coeficientul 3 (secvenţa compusă din turnurile 1, 2 şi 3) Turnul 3 are coeficientul 1 (el însuşi) Turnul 4 are coeficientul 4 (secvenţa compusă din turnurile 1, 2, 3 şi 4) Turnul 5 are coeficientul 7 (secvenţa compusă din toate turnurile) Turnul 6 are coeficientul 2 (secvenţa compusă din turnurile 6 şi 7) Turnul 7 are coeficientul 1 (el însuşi) Coeficientul de frumuseţe al ansamblului este conform imaginii de mai sus. |
