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.
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.
Date de intrare
Fişierul 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).
Date de ieşire
Fişierul 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.
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.
Exemple
sort2dist.in
sort2dist.out
Explicaţii
4
5
7
6
2
2
2 4
2 1
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.
