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

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>