== include(page="template/taskheader" task_id="sort2dist") ==
Poveste și cerință...
Jocul pe care îl joacă Robo atunci când se plictisește este un joc inteligent pentru roboței. Pe ecranul tabletei lui roboțești, sunt N căsuțe de formă pătrată, cu latura egală cu [$1$]. Căsuțele sunt așezate pe un rând, una lângă alta, fiind etichetate, în această ordine, cu numere de la $1$ la [$N$]. 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 [$i$], respectiv cu [$j$], este $j-i (1≤i<j≤N)$.
El își poate fixa în orice moment distanța dintre brațe la $1$ sau își poate dubla distanța curentă dintre brațe, de oricâte ori este necesar, fără a depăși valoarea $N-1$. Astfel, distanța dintre brațele sale poate fi [$1$], apoi, prin dublare, [$2$], apoi, prin dublare [$4$], apoi, prin dublare $8$ etc. La începutul jocului, distanța dintre brațele lui Robo este [$1$]. De fiecare dată când consideră convenabilă distanța dintre brațe, realizează o interschimbare.
h2. Cerință
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.
h2. Date de intrare
Fișierul de intrare $sort2dist.in$ ...
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 se află $N$ numere, reprezentând, în această ordine, identificatorii conținuți în căsuțele tabletei (identificatorul de pe linia $i$ este conținut de căsuța $i-1$).
h2. Date de ieșire
În fișierul de ieșire $sort2dist.out$ ...
Fișierul de ieșire $sort2dist.out$ 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), se vor scrie 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.
h2. Restricții
* $... ≤ ... ≤ ...$
* $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$.
h2. Exemplu
table(example).
|_. sort2dist.in |_. sort2dist.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
5
7
6
2
| 2
2 4
2 1
|
h3. Explicație
...
Tableta are $4$ căsuțe, conținând, în această ordine, identificatorii $(5,7,6,2)$.
Pentru ordonarea crescătoare s-au realizat $2$ interschimbări:
- s-a interschimbat conținutul căsuțelor $2$ și $4$ (distanța dintre centrele lor fiind [$2$]), identificatorii din căsuțe fiind acum $(5, 2, 6, 7)$;
- s-a interschimbat conținutul căsuțelor $1$ și $2$ (distanța dintre centrele lor fiind [$1$]), identificatorii din căsuțe fiind acum $(2, 5, 6, 7)$, ordonați crescător.
== include(page="template/taskfooter" task_id="sort2dist") ==
