View source for 3820 - Mordor Trip

== Cerinţa ==
Dr. Le Quack , fiind un mare fan al Lord Of The Rings , decide să plece în Mordor , locul unde a fost făurit inelul atotputernic . Când acesta ajunge la turnul lui Sauron , observă că intrarea are un cifru . Cifrul este un șir de numere întregi. Dr. Le Quack poate aplică următorul algoritm șirului :

  for(int i=1;i<n;i++){
      if(a[i]<=a[i+1]){
          swap(a[i], a[i+1]);
      }
  }
Dr. Le Quack poate aplica acest tip de operatie de un număr nelimitat de ori ( posibil 0 ). Intrarea se va deschide atunci când șirul va fi unul descrescator. Un șir este descrescător dacă pentru fiecare i din intervalul [1 , n-1] se respectă condiția a[i] ≥ a[i+1]. Dr. Le Quack fiind lacom vrea să stie care este numărul minim operații pentru a deschide intrarea. Pentru că acesta a chiulit de la orele de informatică uitat cum se rezolvă problemele de natură algoritmica , vă roaga sa îl ajutați în schimbul a 100 de puncte și asigurare medicală la cabinetul său.
== Date de intrare ==
Fișierul de intrare mordortrip.in conține pe prima linie numărul n, iar pe a doua linie n numere întregi separate prin spații.
== Date de ieșire ==
Fișierul de ieșire mordortrip.out conține pe prima linie un număr ans reprezentând numărul minim de operații ale
algoritmului specificat mai sus pentru a sorta vectorul dat la input într-unul descrescător.
== Restricţii şi precizări ==
* Numerele sunt întregi , din intervalul [ -1.000.000.000 , 1.000.000.000 ] , NU neapărat distincte.
* Se garantează că avem mereu soluție dintr-un număr finit de operații ale algoritmului descris.
* Pentru teste în valoare de 20 de puncte , N ≤ 5.000.
* Pentru restul testelor , N ≤ 1.000.000.
== Exemplul 1 ==
; mordortrip.in

  5
  5 1 3 2 4
; mordortrip.out

  3
; mordortrip.in

  4
  3 1 2 2
; mordortrip.out

 1
== Explicație ==
În primul exemplu , sunt necesare doar 3 aplicări ale algoritmului : 1 – 5 3 2 4 1 ; 2 – 5 3 4 2 1 ; 3 – 5 4 3 2 1
<br>


== Rezolvare ==
<syntaxhighlight lang="python" line>
def minimum_operations(n, arr):
    operations = 0
    
    for i in range(1, n):
        if arr[i] <= arr[i-1]:
            operations += arr[i-1] - arr[i] + 1
            arr[i] = arr[i-1] + 1
    
    return operations

def read_input(file_name):
    with open(file_name, 'r') as file:
        n = int(file.readline().strip())
        arr = list(map(int, file.readline().strip().split()))
    return n, arr

def write_output(file_name, result):
    with open(file_name, 'w') as file:
        file.write(str(result))

def main():
    n, arr = read_input("mordortrip.in")
    result = minimum_operations(n, arr)
    write_output("mordortrip.out", result)

if __name__ == "__main__":
    main()

</syntaxhighlight>