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

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


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

O metodă de codificare a imaginilor, folosită, de exemplu, în formatul .jpeg, se bazează pe împărţirea unei regiuni pătratice dintr-o imagine în patru pătrate egale, numerotate ca în figura de mai jos.



Acest procedeu de împărţire poate continua la nivele de detaliere mai mari, ceea ce conduce la obţinerea unor numere în care pot să apară cifrele 1, 2, 3 sau 4, şi care corespund unor porţiuni pătratice din imaginea iniţială. În cea de a doua figură sunt prezentate codificările câtorva pătrate.



Un pătrat al cărui cod este cunoscut poate fi deplasat înspre stânga, înspre dreapta, în sus sau în jos cu un anumit număr de poziţii. O comandă de deplasare este de forma
d nr
unde d este un caracter din mulţimea {L,U,R,D}, el arată direcţia pe care este efectuată mutarea, iar nr este un număr natural nenul şi mai mic sau egal decât 10, număr care arată deplasamentul faţă de poziţia curentă. De exemplu, comanda L 1 înseamnă mutarea pătratului cu o poziţie înspre stânga, U 2 înseamnă mutarea pătratului cu două poziţii mai sus, R 3 înseamnă mutarea pătratului cu trei poziţii înspre dreapta, D 1 înseamnă mutarea pătratului cu o poziţie mai jos. De exemplu, comanda de deplasare D 2, aplicată pătratului cu codul 132, îl va duce pe acesta în pătratul cu codul 422. În urma unei comenzi un pătrat poate să ajungă peste un alt pătrat de aceeaşi mărime sau în afara imaginii. Dacă o comandă de deplasare are ca efect ieşirea pătratului în afara zonei ce corespunde întregii imagini, atunci respectiva comandă conduce la oprirea interpretării comenzilor care, eventual, o urmează.

Cerinţă

Scrieţi un program care citeşte o codificare a unui pătrat, apoi o succesiune de comenzi de deplasare referitoare la acel pătrat. Programul trebuie să afişeze numărul de ordine al primei comenzi care conduce la ieşirea pătratului în afara regiunii codificate. Dacă la finalul şirului de comenzi pătratul este încă în interiorul regiunii codificate, fără să fi ieşit vreodată în afara ei, atunci ca rezultat se va scrie codul poziţiei în care a ajuns pătratul după ultima mutare.

Date de intrare

Fişierul de intrare codpatrat.in conţine pe prima linie o succesiune de cifre care semnifică codul pătratului care urmează să fie deplasat. Cifrele nu sunt separate de spaţii şi pot fi 1,2,3 sau 4. În continuare, pe fiecare dintre următoarele linii, până la sfârşitul fişierului, se găsesc comenzi de deplasare a pătratului. Într-o comandă apar un caracter şi un număr, separate printr-un spaţiu. Caracterul poate fi U, D, L sau R, cu semnificaţia descrisă in enunţ. Numărul dintr-o comandă este un număr natural nenul şi mai mic sau egal decât 10.

Date de ieşire

Fişierul de ieşire codpatrat.out va conţine o singură linie, pe care va fi scris, după caz, numărul de ordine al primei comenzi care conduce la ieşirea pătratului în afara imaginii, sau codul poziţiei în care ajunge pătratul în urma efectuării comenzilor de deplasare, sub forma unei secvenţe de cifre 1, 2, 3 sau 4, între care nu există alte caractere.

Restricţii

  • Codul pătratului care urmează să fie deplasat este compus din cel mult 100 caractere.
  • Numărul de comenzi de deplasare este de cel mult 100.

Exemple

codpatrat.in codpatrat.out Explicaţii
1
D 1
R 1
L 1
R 1
D 1
5 Pătratul 1 iese în afara regiunii la mutarea a cincea
133
R 2
U 3
L 3
D 4
421
În urma efectuării celor patru comenzi pătratul care la început era în 133 ajunge în 421
prof. Lucian Ilea
Colegiul Naţional "Emil Racoviţă" Cluj-Napoca
ylucian@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2011: ore, pegals, valet, xpn, efect, nrperm, b2k, sumdivprod, nr0, maxviz, oneton, oras1, ksecv, ripstick, antic, oak, nor, nrpomi, sumprod, paisprezece, cover1, prisme, gxor, progresii, anagramabil, zuma, nrpal, sdmin, lista, operatii1, codarb, adprod, puncte4, qtri, reconst, gsm, subsiruri, mijloc, trifoi, cubulete, romb, maxbin, albine2, probleme, triburi1, megascoala, 2ndesc
De acelaşi autor: sokoban, select, puncte4
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, 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, accesibil, puteri35, sumb, joct, minmax, stele, secvb, goe, copii, b2k, becuri2, patrate7, cifrab, b210
Despre numere mari: fib, 2sir, test, sort, gray, siruri, vecini, div, sir2, nrcuv2, scor, hanoig, red, matrice3, pavaj, depou, pm, sqr, set, albine, teatru1, descfib, tub, m01, soldati1, euclid, mutare, munte1, bifo, banda10, sg1, cutii, zumzi, numere7, trapez, patrate6, muguri, impozit, kbiti, m4, numar3, parbit, petrecere, randomizare, radical, ghinion, aliniere, sumb, cavaleri, camera616, numar4, pavari, asfalt, rotund, cos, risipa, xpn, dale, culori1, plus, minm, pomi, cifrab, subsets, doitrei, conjectura, ech, inventie
surse trimise | ajutor