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

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


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

Pentru că nu au luat toţi nota 10 la simulare, conducerea liceului a hotărât să pedepsească elevii într-un mod inuman: aceştia nu au mai avut voie să meargă la teatru şi nici să mai citească din marii clasici ai literaturii. Singura lor mângâiere era o matrice cu N linii şi N coloane care conţine numai litere mici ale alfabetului englez, pentru care trebuiau să identifice submatricele valabile. O submatrice este considerată valabilă dacă îndeplineşte simultan următoarele condiţii:

  • are cel puţin două linii şi cel puţin două coloane
  • literele aflate în colţurile stânga-sus şi dreapta-jos ale submatricei sunt strict mai mari lexicografic decât toate celelalte litere din submatrice

Cerinţă

Ajutaţi elevii liceului să afle numărul submatricelor valabile care există în matrice şi să scape astfel de pedeapsa îngrozitoare.

Date de intrare

Fişierul de intrare ssdj.in conţine pe prima linie numărul natural N, iar pe următoarele N linii se află câte N litere mici, neseparate prin spaţii.

Date de ieşire

Fişierul de ieşire ssdj.out va conţine un singur număr natural reprezentând numărul de submatrice valabile.

Restricţii

  • 1 <= N <= 1000
  • Pentru teste valorând 10 puncte, N <= 50
  • Pentru teste valorând 20 puncte, matricea va conţine numai literele a şi b

Exemplu

ssdj.in ssdj.out Explicaţii
4
maea
bcda
aaae
aaaa
3

Submatricele valabile sunt:

ma
bc
ea
da
ae
da
ae
prof. Dan Pracsiu
Liceul "Stefan Procopiu" Vaslui
dpracsiu@yahoo.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De acelaşi autor: cai, rebus, 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, dominant
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, tablou, 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, 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, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor