3820 - Mordor Trip - Revision history

RebecaBud: Pagină nouă: == 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
2024-06-03T17:36:16Z

Pagină nouă: == 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 n...

New page
== 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>