4299 - Gravitatie

Cerinţa

Gigel era foarte plictisit așa că a început să se joace cu piese de lego. El a construit turnuleţe de diverse înalţimi pe care le-a aranjat unul lângă celalalt, în linie. Prietenul său, Gogu, intrând în cameră să vadă ce face, a călcat accidental pe turnuleţe, urlând de durere. Când şi-a dat seama Gigel că şi-a supărat prietenul acesta s-a hotărât să îşi rearanjeze turnurile în aşa fel încât gradul de durere, atunci când cineva va călca pe ele sa fie cat mai mic. Ca să calculeze acest grad de durere, Gigel, băiat deştept, a aruncat o placă de plastic peste toate turnuleţele, placă ce s-a rupt în locurile în care două turnuri adiacente au inaltimi diferite. Acesta a stabilit ca gradul de durere să fie egal cu numărul părților în care s-a rupt placa iniţială. Pentru a minimiza gradul de durere, Gigel poate interschimba (de câte ori vrea el) oricare două turnuleţe între ele. (ex: schimbă turnuleţul 1 cu turnuleţul 3, apoi turnuleţul 4 cu turnuleţul 2, etc…).

Date de intrare

În fișierul de intrare gravitatie.in se află pe prima linie, N numărul de turnuleţe. Pe a doua linie se găsesc N numere naturale, reprezentând înalţimea $Hi$ a fiecărui turnuleţ, în ordinea în care acestea sunt aranjate inițial.

Date de ieşire

În fisierul de iesire gravitatie.out se va scrie un singur numar, Nr, reprezentând gradul minim de durere ce se poate obține prin rearanjarea turnulețelor folosind miscări valide.

Restricții și precizări

1 ⩽ n ⩽ 100.000
0 ⩽ Hi ⩽ 4.000.000.000 (patru miliarde)
Bucata de plastic aruncată are lungimea egală cu lungimea șirului de turnulețe.
Pentru 40% din punctaj 0 ⩽ Hi ⩽ 100.000

Exemplul 1

gravitatie.in: 3; 7 3 3
gravitatie.out: 2

Explicație

Gradul minim de durere se poate obține folosind configuratia inițială. Daca de exemplu am schimba primul turnuleț cu al doilea, atunci gradul de durere ar fi 3, placa rupându-se în 3 bucăți diferite.

Exemplul 2

gravitatie.in: 4; 4 7 2 7
gravitatie.out: 3

Explicație

Se observă că dacă inversăm ultimul turn cu penultimul se obține configurația: 4 7 7 2, configurație ce are gradul de durere 3, care este și gradul minim.

Rezolvare

<syntaxhighlight lang="python" line> def durere_minima(N, H):

   # Creăm o listă de perechi (înălțime, poziție inițială)
   turnuri = [(H[i], i) for i in range(N)]
   # Sortăm lista în funcție de înălțime
   turnuri.sort()
   # Calculăm numărul de bucăți în care se rupe placa de plastic
   durere = 1
   for i in range(1, N):
       if turnuri[i-1][1] > turnuri[i][1] or turnuri[i-1][0] != turnuri[i][0]:
           durere += 1
   return durere

Citim datele de intrare din fișier

with open('gravitatie.in', 'r') as f:

   N = int(f.readline())
   H = list(map(int, f.readline().split()))

Calculăm durerea minimă

durere = durere_minima(N, H)

Scriem rezultatul în fișierul de ieșire

with open('gravitatie.out', 'w') as f:

   f.write(str(durere))

</syntaxhighlight>