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

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


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

Ovi este un băiat căruia îi place să rezolve rebus. Un rebus poate fi privit ca o matrice de caractere cu L linii şi C coloane şi care iniţial memorează doar valorile ‘.’ şi ‘#’. Componentele marcate cu ‘.’ semnifică spaţiu gol şi care urmează a fi completat cu litere, iar ‘#’ este un separator. Pe oricare linie sau coloană, spaţiile dintre două caractere ‘#’ sau spaţiile dintre marginea matricei şi un caracter ‘#’ formează o definiţie, cu condiţia ca numărul spaţiilor să fie cel puţin 2.

În imaginea de mai sus este un rebus cu 7 linii şi 8 coloane. Pe prima linie sunt două definiţii: prima este de două litere, iar a doua de 5 litere. Pe linia a treia este o singură definiţie care ocupă întreaga linie. La fel şi pe coloanele 1 şi 7. Pe ultima coloană este tot o singură definiţie, deoarece în colţul din dreapta-jos este un singur spaţiu, care nu poate fi considerat definiţie. În imaginea de mai jos sunt cinci definiţii completate, dintre care trei sunt marcate cu ‘o’ şi două cu ‘x’.

Pentru că a rezolvat foarte multe rebusuri, Ovi s-a plictisit deja, aşa că atunci când rezolvă unul nou, pentru a fi mai complicat de rezolvat, el adoptă următoarea regulă: întâi scrie o primă definiţie, oriunde în rebus, apoi completează o altă definiţie care are proprietatea că are cel puţin o literă comună cu altă definiţie scrisă anterior. Astfel definiţiile formează un singur grup. În exemplul de mai sus, cele trei definiţii completate cu ‘*’ respectă regula, deci sunt un grup, în schimb definiţiile marcate cu ‘x’ nu respectă regula, fiecare formând câte un grup. Într-o zi, Ovi găseşte un rebus completat parţial de cineva şi doreşte să afle câte grupuri există.

Cerinţă

Dat un rebus completat parţial, ajutaţi-l pe Ovi să determine câte grupuri de definiţii există.

Date de intrare

Fişierul de intrare rebus.in conţine pe prima linie două numere naturale L şi C separate printr-un spaţiu. Pe următoarele L linii se găsesc câte C caractere reprezentând fiecare linie a rebusului parţial completat. Caracterele de pe un rând nu sunt separate prin spaţii şi pot fi: '.' (spaţiu liber), '*' (literă dintr-o definiţie) , '#' (separator de definiţii).

Date de ieşire

Fişierul rebus.out va conţine pe prima linie un singur număr natural reprezentând numărul de grupuri de definiţii care apar în rebusul completat parţial.

Restricţii

  • 1 <= L, C <= 100
  • Rebusul dat este corect, în sensul că nu există definiţii doar parţial completate

Exemple

rebus.in rebus.out Explicaţii
7 8
.*#.....
****#...
.*......
.*#**#..
****#...
.#..*..#
...#*...
3 Exemplul corespunde celei de-a doua figuri de mai sus. Sunt 3 grupuri, primul format din trei definiţii, iar celelalte două grupuri au fiecare câte o definiţie.

rebus.in rebus.out Explicaţii
5 5
*#...
*#***
***#.
#****
...*.
3 Primul grup este format din definţia de pe prima coloană şi cea de pe linia a treia.
Al doilea grup este format de definiţia de pe linia a doua.
Al treilea grup este format din definiţia de pe linia a patra şi cea de pe coloana a patra-jos.


prof. Dan Pracsiu
Grup Scolar "Stefan Procopiu" Vaslui
dpracsiu@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2008: celule, premii, cai, scp, forum, vedete, film, finala, ab, nice, supertri, mod3, degrade, fractii, balanta, inginer, camp, ozn, hora, trei, sl, detinut, fbr, noroc, simetric, egal, manevre, connect3, gropi, nrcuv, ruleta, carti, pod, bonuri, tgv, fib, uscat, 2sir, atac, matrice2, zeratul, afise, an, dezbateri, test, miniasm, platforma, lac, vopsea, harta, nrbun2, barfa, nrbun, bunici, opmat, acop, tren, cub, picnic, cursa, rv, compus, comun, magic, votare, onu, tramvai, bipal, nspecial, retea, secvop
De acelaşi autor: cai, harta, comun, axa, sir, ocean14, reduceri, div3, patrate6, vot, reziduu, accesibil, 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 coada: balanta, inginer, camp, harta, insule, volei, lbd, magic3, axa, cadere, reinvent, ocean14, iepuras2, sah, balls, cd, toys, radio, caini, subperm, castel, excursia, casute, soricel2, masina2, salvare, paianjen, suma2, garaj, alee, lanterna, rj, caraibe, taxe1, sotron1, lanturi, tom, k1, dreptunghiuri, sokoban, ny, oldest, drumuri1, alpinist, tsunami, robot3, joc19, valet, oras1, gheizere, zone, taxa, abq, cartite, joc21, traseu3, panda, expand
Despre fill: sarpe, insule, lacuri, zuzu, joc11, gradina, dreptunghiuri, drenaj, fillmat, parcela, acces, tsunami, betasah, zona, zone, taxa, foto, ferma1, antitero, robotzi
surse trimise | ajutor