== include(page="template/taskheader" task_id="aranjare2") ==
Poveste şi cerinţă...
Toată lumea ştie că Mirel are $2*N$ sticluţe cu parfum aşezate pe un raft cu $2*N$ poziţii, numerotate de la $1$ la $2*N$. El are $N$ sticluţe cu parfum cumpărate din ţară şi alte $N$ sticluţe cu parfum cumpărate din Franţa. Sticluţele cumpărate din ţară sunt etichetate cu $r{~1~}, r{~2~}, r{~3~}, …, r{~N~}$, iar sticluţele cumpărate din Franţa sunt etichetate cu $f{~1~}, f{~2~}, f{~3~}, …, f{~N~}$. Fiecare sticluţă are asociată valoarea cu care a fost cumpărată.
Iniţial, Mirel are aşezate pe primele $N$ poziţii sticluţele cumpărate din ţară sortate crescător după valoare, iar pe următoarele $N$ poziţii sticluţele cumpărate din Franţa sortate tot crescător după valoare. Astfel, cele $2*N$ sticluţe cu parfum sunt aşezate în felul următor: $r{~1~}, r{~2~}, r{~3~}, …, r{~N~}, f{~1~}, f{~2~}, f{~3~}, …, f{~N~}$. Mai exact, sticluţa $r{~i~}$ se află pe poziţia $i$, iar sticluţa $f{~i~}$ se află pe poziţia $N+i$, pentru $i$ din intervalul $[1, N]$.
Prietenul său cel mai bun, Marian, s-a gândit să-i facă o surprinză şi să-i schimbe aranjarea sticluţelor cu parfum în următoarea ordine: $r{~1~}, f{~1~}, r{~2~}, f{~2~}, r{~3~}, f{~3~}, …, r{~N~}, f{~N~}$. Cum Marian are două mâini, el poate face numai următorul tip de operaţie: ia două sticluţe cu parfum de pe raft (de pe două poziţii diferite) şi le interschimbă.
h2. Cerinţă
Dându-se numărul $N$, şi $2*N$ valori reprezentând valoarea fiecărei sticluţe cu parfum, ajutaţi-l pe Marian să facă operaţiile necesare pentru a schimba ordinea sticluţelor cu parfum în ordinea precizată în enunţ.
h2. Date de intrare
Fişierul de intrare $aranjare2.in$ ...
Fişierul de intrare $aranjare2.in$ conţine pe prima linie numărul $N$, iar pe următoarea linie $2*N$ numere naturale, separate prin câte un spaţiu. Primele $N$ numere reprezintă valorile sticluţelor cumpărate din ţară, iar următoarele $N$ numere reprezintă valorile sticluţelor cumpărate din Franţa. Atât primele $N$, cât şi ultimele $N$ numere sunt sortate crescător în funcţie de valoare.
h2. Date de ieşire
În fişierul de ieşire $aranjare2.out$ ...
În fişierul de ieşire $aranjare2.out$ va conţine mai multe linii. Pe fiecare linie se vor afla două numere diferite $x$ şi $y$ din intervalul $[1, 2*N]$, semnificând faptul că Marian trebuie să interschimbe sticluţa de pe poziţia $x$ cu sticluţa de pe poziţia $y$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 100 000$
* Dacă există mai multe soluţii, se poate afişa oricare dintre ele.
* Soluţia nu trebuie să facă neapărat numărul minim de operaţii.
* Pentru $15%$ din teste se garantează că $N ≤ 13$.
* Pentru alte $25%$ din teste se garantează că $N ≤ 300$.
* Pentru alte $30%$ din teste se garantează că $N ≤ 1000$.
h2. Exemplu
table(example). |_. aranjare2.in |_. aranjare2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
1 3 5 2 3 5
| 2 4
3 5
3 4
|
h3. Explicaţie
...
În explicaţia de mai jos, fiecare sticluţă are numele etichetei urmat de valoarea ei în paranteză.
Şirul iniţial este: $r1(1) r2(3) r3(5) f1(2) f2(3) f3(5)$
După prima mutare devine: $r1(1) f1(2) r3(5) r2(3) f2(3) f3(5)$
După a doua mutare devine: $r1(1) f1(2) f2(3) r2(3) r3(5) f3(5)$
După ultima mutare devine: $r1(1) f1(2) r2(3) f2(3) r3(5) f3(5)$
== include(page="template/taskfooter" task_id="aranjare2") ==
== include(page="template/taskfooter" task_id="aranjare2") ==
