Editing 1225 - Sort 2 Dist

== Cerința ==
Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum 12500 interschimbări de tipul celei precizate mai sus.
== Date de intrare ==
Fișierul de intrare sort2dist.in conține:
<br>
~ pe prima linie numărul natural N, cu semnificația din enunț;
<br>
~ pe următoarele N linii, N numere, reprezentând, în această ordine, identificatorii aflați în căsuțele tabletei (identificatorul de pe linia i se află în căsuța i-1).
== Date de ieșire == 
Fișierul de ieșire sort2dist.out va conține:
<br>
~pe prima linie un număr natural M, reprezentând numărul de interschimbări realizate de Robo (nu neapărat numărul minim de interschimbări necesare);
<br>
~pe fiecare dintre următoarele M linii (doar dacă M este nenul), câte două numere naturale, separate prin câte un spațiu, reprezentând etichetele căsuțelor al căror conținut s-a interschimbat, în ordinea realizării acestor interschimbări.
== Restricții și precizări ==
~ 1 ≤ N ≤ 1000;\
<br>
~ identificatorii sunt numere naturale de maximum 30 de cifre;
<br>
~ pentru 25% din punctaj, fișierele de test conțin numere cu maximum 18 cifre;
<br>
~ pentru 25% din punctaj, N ≤ 100.
== Exemplu 1 ==
; Intrare
: sort2dist.in
:4
:5
:7
:6
:2
; Ieșire
: sort2dist.out
:2
:2 4
:2 1
<br>
== Exemplu 2 ==
; Intrare
: sort2dist.in
:2
:5
:6
:3
:7
; Ieșire
: sort2dist.out
:2 3
:4 2 2
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#1225 - Sort 2 Dist
def sortare_distanta_minima(N, identificatori):
    interschimbari = []

    distanta_brate = 1
    while distanta_brate <= N - 1:
        for i in range(0, N - distanta_brate, distanta_brate * 2):
            if identificatori[i] > identificatori[i + distanta_brate]:
                interschimbari.append((i + 1, i + distanta_brate + 1))
                identificatori[i], identificatori[i + distanta_brate] = identificatori[i + distanta_brate], identificatori[i]

        distanta_brate *= 2

    return interschimbari

def main():
    with open("sort2dist.in", "r") as file_in:
        N = int(file_in.readline())
        identificatori = [int(file_in.readline()) for _ in range(N)]

    interschimbari = sortare_distanta_minima(N, identificatori)

    with open("sort2dist.out", "w") as file_out:
        file_out.write(str(len(interschimbari)) + "\n")
        for interschimbare in interschimbari:
            file_out.write(f"{interschimbare[0]} {interschimbare[1]}\n")

if __name__ == "__main__":
    main()
</syntaxhighlight>