2437 - Turnuri

Enunt

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.

Cerinta

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 turnuri.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 turnuri.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 și precizări

• 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 ≤ 2000
• În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplul din enunț.

Exemplul 1

intrare

7

10 3 1 7 8 6 5

iesire

Datele introduse corespund restrictiilor impuse.

19

22

22

22

21

22

22

Exemplul 2

intrare

-1

2 11 5 3 6 8 5

iesire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python3" line="1">

1. 2437 - Tunuri

def coeficient_frumusete(turnuri):

   n = len(turnuri)
   rezultate = []

   for restaurant in range(n):
       coef_frumusete_turn = 0

       # Verificăm fiecare turn în stânga restaurantului
       for stanga in range(restaurant, -1, -1):
           if stanga == restaurant:
               continue

           if turnuri[stanga] > turnuri[restaurant]:
               coef_frumusete_turn += 1
               break

       # Verificăm fiecare turn în dreapta restaurantului
       for dreapta in range(restaurant, n):
           if dreapta == restaurant:
               continue

           if turnuri[dreapta] > turnuri[restaurant]:
               coef_frumusete_turn += 1
               break

       rezultate.append(coef_frumusete_turn)

   return rezultate

print("Coeficientele de frumusețe pentru fiecare poziție posibilă a restaurantului:") print(rezultate)

</syntaxhighlight>