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

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


Timp maxim de execuţie / test:
0.7s
Memorie totala disponibilă / stivă:
5MB / 5MB

Manole a învăţat de la profesorul de informatică cum să calculeze suma elementelor oricărei matrice A cu N linii şi M coloane. El numerotează liniile de la 1 la N şi coloanele de la 1 la M. Mai mult, Manole fiind extrem de pasionat de numere, va calcula sumele tuturor subtablourilor din cadrul matricei A. Şirul acestor sume îl scrie pe o hârtie, după ce l-a ordonat crescător.
Prin subtablou el înţelege o zonă dreptunghiulară din matricea A, identificată prin colţul stânga-sus (x1,y1) şi colţul dreapta-jos (x2,y2), elementele subtabloului fiind toate elementele A[i][j] pentru care x1≤i≤x2 şi y1≤j≤y2. Suma unui subtablou este suma tuturor elementelor sale.

Cerinţă

Scrieţi un program care, cunoscând valorile elementelor matricei A, determină al K-lea termen din şirul ordonat al sumelor tuturor subtablourilor matricii A.

Date de intrare

Fişierul de intrare ssk.in conţine pe prima linie numerele naturale N M K separate prin câte un spaţiu, având semnificaţia din enunţ. Pe următoarele N linii se află câte M numere naturale separate prin spaţii, reprezentând elementele matricei A.

Date de ieşire

Fişierul de ieşire ssk.out va conţine o singură linie pe care va fi scris un număr natural reprezentând răspunsul la cerinţă.

Restricţii

• 1 ≤ N ≤ 150
• 1 ≤ M ≤ 150
• 1 ≤ K ≤ numărul de termeni din şirul ordonat
• 0 ≤ A[i][j] ≤ 1000 unde 1 ≤ i ≤ N şi 1 ≤ j ≤ M
• Numerotarea termenilor din şirul ordonat al sumelor tuturor subtablourilor se va face începând de la 1.

Exemple

ssk.inssk.outExplicaţii
2 3 14 3 2 7 4 1 0 9 Şirul ordonat al tuturor sumelor subtablourilor matricei este
0 1 1 2 3 3 4 5 5 5 7 7 7 9 10 10 12 17
A patrusprezecea sumă este 9

autor: Prof. Dana Lica
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONIG 2015: cript, scadere, tv1, nebuni, spioni1, magic7, restaurare, sort2dist, echer, lightbot, teren1, iepuras1, inventie
De acelaşi autor: compus, taste, arce, balbe, drept, scor, sume3, spair, bitslang, police, tree, reteta2, farfurii, caramele, apm, maraton, masina1, bomboane, soldati1, concurs1, puncte, pipe, camion, imax, litoral, dreptc, bal, prefix1, tablite, lanturi, loto, bila, popic, activ, game1, pitag, secv9, divk, taler, bdotcom, oak, ozn1, optim, puncte5, swap, tetris3, monede2
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, 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, teren1, fence, cifre6
Despre căutare binară: gropi, pod, uscat, checkin, copaci, aven, br, furtuna, livada, numar, matrice, sume, bacan, toys, chimie2, trafic, ants, multiplu, ghici, sirag1, tabara, puncte1, centru, harta1, salvare, spion, poze, dist1, patrate5, resturi, lanterna, sea2, vot, standard, cantor, medalii, binperm, mobil, stalpi1, expo, miere, conferinta, subs, pack, obstacole, dag, acoperire, verigi, bradut2, triburi, intervale, mijloc, patru, eliminare, vectori1, calcule, secvp, dreapta, colina, robotics, cabana
surse trimise | ajutor