Fişierul intrare/ieşire:aranjare2.in, aranjare2.outSursăONI 2013, clasa a 9-a
AutorCosmin-Mihai TutunaruAdăugată deMagnvsDaniel Constantin Anghel Magnvs
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Aranjare 2

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 r1, r2, r3, …, rN, iar sticluţele cumpărate din Franţa sunt etichetate cu f1, f2, f3, …, fN. 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: r1, r2, r3, …, rN, f1, f2, f3, …, fN. Mai exact, sticluţa ri se află pe poziţia i, iar sticluţa fi 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: r1, f1, r2, f2, r3, f3, …, rN, fN. 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ă.

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ţ.

Date de intrare

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.

Date de ieşire

Î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.

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.

Exemplu

aranjare2.inaranjare2.out
3
1 3 5 2 3 5
2 4
3 5
3 4

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)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content