Editing 1225 - Sort 2 Dist


Jocul pe care îl joaca Robo atunci când se plictisește este un joc inteligent pentru roboței. Pe ecranul tabletei lui roboțești, sunt <code>N</code> căsuțe de formă pătrată, cu latura egală cu <code>1</code>. Căsuțele sunt așezate pe un rând, una lângă alta, fiind etichetate, în această ordine, cu numere de la <code>1</code> la <code>N</code>. Fiecare căsuță conține câte un număr natural, identificatorul câte unuia dintre prietenii săi, roboței, ca și el. Identificatorii se pot repeta.

Robo poate interschimba conținutul a două căsuțe, numai dacă distanța dintre centrele acestora pe orizontală este egală cu distanța dintre brațele sale; distanța, pe orizontală, dintre centrele a două căsuțe etichetate cu <code>i</code>, respectiv cu <code>j</code>, este <code>j-i</code> (<code>1≤i<j≤N</code>).

El își poate fixa în orice moment distanța dintre brațe la <code>1</code> sau își poate dubla distanța curentă dintre brațe, de oricâte ori este necesar, fără a depăși valoarea <code>N-1</code>. Astfel, distanța dintre brațele sale poate fi <code>1</code>, apoi, prin dublare, <code>2</code>, apoi, prin dublare <code>4</code>, apoi, prin dublare <code>8</code> etc. La începutul jocului, distanța dintre brațele lui Robo este <code>1</code>. De fiecare dată când consideră convenabilă distanța dintre brațe, realizează o interschimbare.

= Cerința =
Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum <code>12500</code> interschimbări de tipul celei precizate mai sus.

= Date de intrare =
Fișierul de intrare <code>sort2distIN.txt</code> conține:

* pe prima linie numărul natural <code>N</code>, cu semnificația din enunț;
* pe următoarele <code>N</code> linii, <code>N</code> numere, reprezentând, în această ordine, identificatorii aflați în căsuțele tabletei (identificatorul de pe linia <code>i</code> se află în căsuța <code>i-1</code>).

= Date de ieșire =
Fișierul de ieșire <code>sort2distOUT.txt</code> va conține:

* pe prima linie un număr natural <code>M</code>, 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 <code>M</code> linii (doar dacă <code>M</code> 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. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N ≤ 1000</code>;
* identificatorii sunt numere naturale de maximum <code>30</code> de cifre;
* pentru 25% din punctaj, fișierele de test conțin numere cu maximum <code>18</code> cifre;
* pentru 25% din punctaj, <code>N ≤ 100</code>.

= Exemplul 1 : =
<code>sort2distIN.txt</code>
 4
 5
 7
 6
 2
<code>sort2distOUT.txt</code>
 2
 2 4
 2 1

=== Explicație ===
Tableta are <code>4</code> căsuțe, conținând, în această ordine, identificatorii <code>(5,7,6,2)</code>.

Pentru ordonarea crescătoare s-au realizat <code>2</code> interschimbări:

* s-a interschimbat conținutul căsuțelor <code>2</code> și <code>4</code> (distanța dintre centrele lor fiind <code>2</code>), identificatorii din căsuțe fiind acum <code>(5, 2, 6, 7)</code>;
* s-a interschimbat conținutul căsuțelor <code>1</code> și <code>2</code> (distanța dintre centrele lor fiind <code>1</code>), identificatorii din căsuțe fiind acum <code>(2, 5, 6, 7)</code>, ordonați crescător.

== Exemplul 2 : ==
<code>sort2distIN.txt</code>
 1001
 5
 7
 6
 2
<code>sort2distOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare == 
<syntaxhighlight lang="python" line="1">
import os

DIM = 1010

sol = []
v = [0] * DIM
s = [""] * DIM
aux = ""
w = [""] * DIM

def myStrcmp(s1, s2):
    if len(s1) == len(s2):
        return (s1 > s2) - (s1 < s2)
    else:
        return -1 if len(s1) < len(s2) else 1

def schimba(x, y):
    sol.append((x, y))
    aux = v[x]
    v[x] = v[y]
    v[y] = aux

def verify_restrictions(n, strings):
    if not (1 <= n <= 1000):
        return False
    for string in strings:
        if not (1 <= len(string) <= 30):
            return False
    return True

def main():
    with open("sort2distIN.txt", "r") as fin:
        n = int(fin.readline().strip())
        for i in range(1, n + 1):
            s[i] = fin.readline().strip()
            w[i] = s[i]

    if not verify_restrictions(n, s[1:n+1]):
        with open("sort2distOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse")
        return

    for i in range(1, n):
        for j in range(i + 1, n + 1):
            if myStrcmp(w[i], w[j]) > 0:
                w[i], w[j] = w[j], w[i]

    k = 1
    for i in range(2, n + 1):
        if myStrcmp(w[i], w[k]) != 0:
            k += 1
            w[k] = w[i]

    for i in range(1, n + 1):
        st = 1
        dr = k
        while st <= dr:
            mid = (st + dr) // 2
            if myStrcmp(s[i], w[mid]) == 0:
                v[i] = mid
                break
            if myStrcmp(s[i], w[mid]) < 0:
                dr = mid - 1
            else:
                st = mid + 1

    for i in range(n, 1, -1):
        m = v[1]
        p = 1
        for j in range(2, i + 1):
            if v[j] > m:
                m = v[j]
                p = j
        if p != i:
            d = i - p

            putere = 1
            last = p
            while d != 0:
                if d % 2 == 1:
                    schimba(last + putere, last)
                    last += putere
                d = d // 2
                putere *= 2

    with open("sort2distOUT.txt", "w") as fout:
        fout.write(f"{len(sol)}\n")
        for x, y in sol:
            fout.write(f"{x} {y}\n")

if __name__ == "__main__":
    main()

</syntaxhighlight>