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:
~ pe prima linie numărul natural N, cu semnificația din enunț;
~ 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:
~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);
~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;\
~ identificatorii sunt numere naturale de maximum 30 de cifre;
~ pentru 25% din punctaj, fișierele de test conțin numere cu maximum 18 cifre;
~ 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

Exemplu 2

Intrare

sort2dist.in

2

5

6

3

7

Ieșire

sort2dist.out

2 3

4 2 2

Rezolvare

#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()