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

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


Timp maxim de execuţie/test:
0.1 secunde
Memorie totală disponibilă/stivă:
16 MB/1 MB

Considerăm pentru un număr natural n şirul tuturor numerelor naturale cuprinse între 1 şi 2n - 2, numerele fiind într-o ordine oarecare. Un astfel de şir pentru n=3 este format din numerele de la 1 la 6, de exemplu 3, 1, 5, 4, 6, 2. Reprezentăm fiecare număr din şir pe n biţi, scriind biţii pe verticală. Mai jos este scris sub fiecare număr din şir reprezentarea sa în baza 2:

3 1 5 4 6 2
0 0 1 1 1 0
1 0 0 0 1 1
1 1 1 0 0 0

Se obţine astfel o matrice binară cu n linii şi 2n - 2 coloane (în cazul de mai sus, cu 3 linii şi 6 coloane). Se observă că plecând de la bitul 0 de pe prima coloană şi mergând doar pe valori de 0 învecinate pe linii şi coloane (nu şi diagonale), se poate ajunge pe un 0 de pe ultima coloană. Un astfel de şir îl numim accesibil. Sunt mai multe astfel de şiruri accesibile. Pentru n = 3 şirurile 2, 3, 1, 5, 4, 6 şi 2, 6, 4, 5, 1, 3 sunt de asemenea accesibile. Dintre acestea îl alegem pe cel minim din punct de vedere lexicografic.

Cerinţă

Pentru că şirul accesibil minim lexicografic poate fi foarte lung, nu trebuie să-l determinaţi, ci să scrieţi un program care pentru o valoare dată a lui n şi pentru patru numere naturale x1, x2, x3, x4 cuprinse între 1 şi 2n - 2, determină poziţia acestora în şirul accesibil minim lexicografic.

Date de intrare

Fişierul de intrare accesibil.in conţine pe prima linie numărul natural n, iar pe următoarele 4 linii câte un număr natural: pe linia 2 se află numărul x1, pe linia 3 este numărul x2, pe linia 4 numărul x3, iar pe ultima linie numărul x4.

Date de ieşire

Fişierul de ieşire accesibil.out conţine patru linii, pe fiecare linie aflându-se un singur număr. Linia i conţine un număr natural reprezentând poziţia numărului xi în şirul accesibil minim lexicografic.

Restricţii

  • 3 <= n <= 1 000
  • 1 <= x1, x2, x3, x4 <= 2n - 2
  • Poziţiile în şir se numerotează de la 1 la 2n - 2
  • Spunem că şirul a1, a2, ..., ak este mai mic lexicografic decât b1, b2, ..., bk dacă există o poziţie p, 1 <= p <= k, astfel încât a1=b1, a2=b2, ..., ap-1=bp-1 şi ap <bp.

Exemplu

accesibil.in accesibil.out

4
9
11
3
12

11
10
7
13

prof. Dan Pracsiu
Grupul Şcolar „Ştefan Procopiu” Vaslui
dpracsiu@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2009: efort, muzeu, bal, seti, basm, dansatori, smith, timer, secvsir, vot, cetati, reziduu, biliard, prefix1, dp, jocv, placa, palc, prod3, predecesor, standard, cantor, nkbiti, nori, triti, kperms, sotron1, impozit, tablite, fazan, lanturi, secvpar, tom, joker, matriosca, asociativ, lego, medalii, permutari, cfr, treegame, scanduri, site, fotbal, links, kbiti, segm, album, iepurasi, jucarii, m4, bradut, trmv, colorare, greutati, concat, graphgame, ic, echilibru, brazi, mat, cubinvers, mobil, distsir, parbit
De acelaşi autor: cai, rebus, harta, comun, axa, sir, ocean14, reduceri, div3, patrate6, vot, reziduu, predecesor, permutari, scanduri, ordonare, xor1, paltrei, triunghi1, 123, traseu1, parbit, petrecere, secvbiti, subm, triunghi3, cmmdcsecv, drumuri1, fillmat, secvb, siruri3, acces, segmente, echilibru1, broscute, ksecv, paisprezece, proddiv, perechi2, expeval, maxtri, combcuv, dfs, qtri, blis, maxbin, probleme, divider, eliminare, minm, genab, grafxy, matd3, azeval, matrixdel, speed, maxp, split, binremove, sminus, subsets, tcif, sprime, sir2dif, ecp, arbsum, robotzi, permtr, unudoi, matcnt, ssdj, dominant
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, 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, sort2dist, lightbot, iepuras1, castig
Despre baze de numeraţie: balanta, gray, np, nr01, tablou, aritma, joc8, numere6, ceas2, paritate, test1, visul, numere9, puteri35, sumb, joct, minmax, stele, secvb, goe, copii, b2k, becuri2, codpatrat, patrate7, cifrab, b210
surse trimise | ajutor