Fişierul intrare/ieşire:turnuri4.in, turnuri4.outSursăOJI 2018, Clasa a 10-a
AutorEugenie Daniel PosdarascuAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inturnuri4.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?