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

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


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

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

autor: Prof. Marius Nicoli
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONIG 2015: cript, scadere, tv1, nebuni, spioni1, ssk, magic7, restaurare, echer, lightbot, teren1, iepuras1, inventie
De acelaşi autor: secvente1, raze, bile5, 235, dreptunghiuri, triunghi2, albine1, puteri35, miere, left, arbgraf, reuniune, cazare, atletism, fluviu, stele, zar1, poteci, avioane, obstacole, liste, acoperire1, minusk, efect, b2k, progresii, reconst, mijloc, romb, alune, patru, galbeni, schi1, restaurare
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, aranjare2, 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, lightbot, iepuras1, castig
surse trimise | ajutor