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

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


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

De ziua lui, Gigel a primit un tort de formă dreptunghiulară, ornat cu un caroiaj ce împarte tortul în mxn pătrate, în fiecare pătrat aflându-se câte o cireaşă sau o căpşună. Caroiajul cu fructe este reprezentat printr-o matrice cu 0 şi 1, 0 însemnând cireaşă şi 1 căpşună. Sărbătoritul are dreptul să taie k felii de tort. O felie se poate obţine prin tăierea după liniile caroiajului, dintr-un capăt în celălalt, având lăţimea egală cu 1, de pe oricare latură a tortului, codificate cu N, E, S, V. Gigel fiind mare amator de căpşuni vrea să taie cele k felii astfel încât numărul căpşunilor din aceste felii să fie cât mai mare.
Spre exemplu, dacă tortul iniţial este reprezentat ca o matrice având 6x6 linii şi coloane, după 3 tăieturi N, E, V bucata rămasă şi feliile obţinute vor fi conform figurii alăturate.


Cerinţă

Să se scrie un program care să determine numărul de posibilităţi de tăiere a k felii de tort, pentru a obţine un număr maxim de căpşuni. Două variante în care diferă doar ordinea de tăiere, dar rămâne aceeaşi bucată de tort, nu sunt considerate distincte. De exemplu, dacă numărul maxim de căpşuni se poate obţine prin una dintre variantele: VSNNV sau VVNSN, acestea nu sunt considerate distincte.

Date de intrare

Pe prima linie a fişierului de intrare tort1.in sunt scrise dimensiunile tortului, m n, precum şi numărul k al feliilor de tort tăiate de Gigel, separate prin câte un spaţiu. Pe următoarele m linii e descris caroiajul cu fructe printr-o matrice cu valori de 0 şi 1.

Date de ieşire

Prima linie a fişierului tort1.out va conţine numărul maxim de căpşuni care poate fi obţinut din cele k felii de tort. Pe linia a doua se va găsi numărul de posibilităţi distincte de a obţine numărul maxim de căpşuni.

Restricţii

2 ≤ m, n ≤ 500
1 ≤ k < min(m,n)

Exemple

tort1.intort1.outExplicaţii
6 6 3 0 1 1 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 10 5 Tortul este format dintr-un caroiaj cu m=6 linii şi n=6 coloane şi se pot tăia k=3 felii.
Se pot obţine maxim 10 căpşuni.
Cele 5 posibilităţi de a tăia cele 3 felii sunt:
NNS, NSE, NSV, VEV şi NEV

autor: Prof. Nistor-Eugen Moţ
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2011: sport2, macheta, butoane, acces, mxl, segmente, tsunami, ec, ape, poligon4, stalpi2, furnici1, telecab, ikebana, posta, fotbal1, xmoto, radare, pamant, fagure, goe, papusa, taburet, joc17, mesaj3, zar1, joc16, talent, xy, arbore1, robot3, copii, hacker, terenuri3d, terenuri, expresie2, poteci, joc18
De acelaşi autor: cursa, insule, termen, div, mese, hperm, zmeu, chimie2, mere2, vile, dans, multiplu, paralel, divizor, ghici, barca1, fibo, parc, circular, sant, mobile, pattern, mutare, concurs2, soricel1, soricel2, vizibil, bloc, soricel3, sah1, gramada, gramezi1, aranjari, numere5, cifru1, lacusta, sir6, puncte3, peri, atelier, radical, pion, el, triunghi4, bile6, zmax
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, 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
surse trimise | ajutor