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

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


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

Se consideră un tablou bidimensional de dimensiuni date m (numărul de linii) şi n (numărul de coloane), ale cărei elemente sunt cifre ale sistemului de numeraţie zecimal. Cu elementele unei linii se construieşte un număr scris în cea mai mică bază posibilă, utilizând toate cifrele de pe linia respectivă, luate de la stânga la dreapta. Se spune că acest număr se ataşează liniei respective. După această regulă se ataşează numere fiecărei linii, numere care se transformă apoi în baza 10. Se identifică cel mai mare număr scris în baza 10 dintre numerele ataşate fiecărei linii şi linia pe care se află; dacă sunt mai multe linii pe care se află cel mai mare număr, se alege cea cu indicele cel mai mic (cea mai de sus). Să notăm indicele acestei linii cu p. De pe linia p se identifică, dacă există, coloana cu indicele cel mai mic (cea mai din stânga) pe care se află o cifră pară. Să notăm indicele acestei coloane cu q. Dacă există o astfel de coloană, atunci se elimină din tablou linia p şi coloana q. Prin eliminare, numărul de linii şi numărul de coloane ale tabloului scad cu 1, astfel, dacă, de exemplu, s-ar elimina linia 3, atunci linia 4 va deveni linia 3, linia 5 va deveni linia 4, ..., linia m va deveni linia m-1, iar dacă, de exemplu, s-ar elimina coloana 4, atunci coloana 5 va deveni coloana 4, coloana 6 va deveni coloana 5, ..., coloana n va deveni coloana n-1. S-a obţinut astfel un nou tablou bidimensional, în care liniile se consideră având indicii 1, 2, ... , ş.a.m.d., iar coloanele indicii 1, 2, ... , ş.a.m.d. Dacă pe linia p nu se poate găsi o cifră pară, tabloul nu se modifică.
Se reia procedeul de mai sus pentru noul tablou, începând cu ataşarea numerelor pentru noile linii, identificarea celui mai mare număr în baza 10, identificarea liniei p şi coloanei q (dacă există) şi apoi eliminarea liniei p şi coloanei q, dacă este cazul. Procedeul se opreşte fie când nu se mai identifică pe linia p o cifră pară, fie când cel puţin una dintre dimensiunile tabloului (numărul de linii sau numărul de coloane) a ajuns la valoarea 1.

Cerinţă

Dându-se tabloul bidimensional cu m linii şi n coloane, se cere:
a) Să se afişeze bazele minime care au fost alese pentru fiecare număr ataşat fiecărei linii din tabloul iniţial;
b) Să se afişeze cel mai mare număr scris în baza 10 dintre numerele ataşate tabloului iniţial;
c) Să se afişeze numărul de linii şi numărul de coloane pentru tabloul final, precum şi tabloul final.

Date de intrare

Fişierul de intrare tablou.in va conţine:
- pe prima linie din fişier se află numărul natural m care reprezintă numărul de linii şi numărul natural n care reprezintă numărul de coloane din tabloul iniţial, numere separate între ele printr-un spaţiu
- pe următoarele m linii câte n numere separate două câte două printr-un spaţiu

Date de ieşire

Fişierul de ieşire tablou.out va conţine:
- pe prima linie se vor afişa m numere separate două câte două printr-un spaţiu, reprezentând bazele conform cerinţei a);
- pe a doua linie se află numărul solicitat conform cerinţei b);
- pe a treia linie se află numărul de linii şi numărul de coloane pentru tabloul final, numere separate printr-un spaţiu (fie acestea x şi y);
- pe următoarele x linii se află câte y numere separate două câte două printr-un spaţiu.

Restricţii

2 ≤ m,n ≤ 10.
Cel mai mare număr ataşat unei linii, număr scris în baza 10 este 2 000 000 000. Cea mai mică bază în care poate fi scris un număr ataşat unei linii este baza 2 şi cea mai mare este 10.

Exemple

tablou.intablou.outExplicaţii
4 4 1 0 1 1 2 0 1 2 1 3 1 3 3 0 0 0 2 3 4 4 192 2 2 1 1 1 3 Numerele ataşate liniilor sunt: 1011 în baza 2, 2012 în baza 3, 1313 în baza 4, 3000 în baza 4. Valorile acestora în baza 10 sunt: 11, 59, 119, 192. Cel mai mare este 192 şi se află pe linia 4. Primul element par de pe linia 4 este pe coloana a doua. Se vor elimina deci linia 4 şi coloana 2. Tabloul rămas are 3 linii şi 3 coloane şi are valorile:
1 1 1
2 1 2
1 1 3
şi se reia procedeul.
Numerele ataşate liniilor noului tablou sunt: 111 în baza 2, 212 în baza 3, 113 în baza 4. Valorile acestora în baza 10 sunt: 7, 23, 23. Cel mai mare este 23, iar primul egal cu 23 se află pe linia 2. Primul element par de pe linia 2 este pe prima coloană. Se vor elimina deci linia 2 şi coloana 1. Tabloul rămas are 2 linii şi 2 coloane şi are valorile:
1 1
1 3
şi se reia procedeul.
Numerele ataşate liniilor sunt: 11 în baza 2, 13 în baza 4. Valorile acestora în baza 10 sunt: 3, 7. Cel mai mare este 7 şi se află pe linia 2. Pe această linie nu se află niciun element par, deci procedeul se încheie.

autor: Prof. Roxana Timplaru
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2008: ab2, iepuras, palind, auto, div, teatru, pm, submat, reteta2, rezervatie, creioane, melci, mere2, felinare, joc3, 2numere, fi, borcane, mexc, tcast, dep, dist1, stiva, banda, pavare, poarta, aranjare, bile4, subgeom, albinuta1, curent, pviz, atac2, virus
De acelaşi autor: numere4, numar1, prieteni2, roboti, numere6, cartonas, test1, v, cuvant, roboti1, asfalt, grupe2, joc17, numar5, munte3
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, 2ndesc, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, incadrare, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
Despre baze de numeraţie: balanta, gray, np, nr01, aritma, joc8, numere6, ceas2, paritate, test1, visul, numere9, accesibil, puteri35, sumb, joct, minmax, stele, secvb, goe, copii, b2k, becuri2, codpatrat, patrate7, cifrab, b210
surse trimise | ajutor