.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » aranjare2

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
aranjare2


Timp maxim de execuţie / test:
0.3s
Memorie totala disponibilă / stivă:
16MB / 8MB

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, …, rN, iar sticluţele cumpărate din Franţa sunt etichetate cu f1, f2, …, 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, …, rN, f1, f2, …, 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 surpriză şi să-i schimbe aranjarea sticluţelor cu parfum în următoarea ordine: r1, f1, r2, f2, …, 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

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 ≤ 31 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.

Exemple

aranjare2.inaranjare2.outExplicaţii
3 1 3 5 2 3 5 2 4 3 5 3 4 Î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)

autor: stud. Cosmin-Mihai Tutunaru
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2013: split, momente, gradina1, secvente2, flori2, romb1, cumpanit, spider, zone, taxa, ausoara, drumuri2, confuzie, xnumere, bemo, showroom, cntgcd
De acelaşi autor: camera616, secvnumber, posta, oneton, secvente2, interclasare, dreapta, puteri
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
surse trimise | ajutor