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

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


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

Gigel are o masă dreptunghiulară împărţită în m×n pătrate egale. În fiecare pătrat se gaseşte cel puţin o bomboană. El are dreptul să ia bomboane din mai multe pătrate care să formeze un “L” de lăţime 1. El poate alege “colţul” L-ului în orice pătrat, singura restricţie fiind ca ramura orizontală şi cea verticală să aibă lungimea cel puţin 2, deci să fie cel puţin încă un pătrat alăturat colţului pe orizontală şi cel puţin unul alăturat pe verticală.

Cerinţă

Găsiţi poziţia L-ului astfel ca numărul bomboanelor de pe pătratele ce compun L-ul să fie maxim.

Date de intrare

Fişierul de intrare el.in conţine pe prima linie numerele naturale m şi n reprezentând dimensiunea mesei. Pe următoarele m linii sunt câte n numere întregi separate de câte un spaţiu, matricea ce dă numărul de bomboane din fiecare pătrat.

Date de ieşire

Fişierul de ieşire el.out va conţine două linii. Pe prima linie numărul maxim de bomboane pe care le poate lua Gigel, iar pe următoarea linie 4 numere întregi separate de câte un spaţiu, precizând poziţia L-ului ce conţine acest număr maxim de bomboane. Poziţia e dată astfel: coordonatele colţului (linia şi coloana sa, numerotarea făcându-se de la 1), apoi lungimea ramurii orizontale, apoi lungimea ramurii verticale. Lungimile ramurilor înseamnă numărul de pătrate (inclusiv colţul) care alcătuiesc ramura, precedat de semnul minus dacă ramura orizontală este in stânga colţului, respectiv ramura verticală este în josul colţului. Dacă sunt mai multe soluţii posibile se alege cea care respectă, în ordine, criteriile următoare: are linia colţului minimă, are coloana colţului minimă, are ramura orizontală în stânga, are ramura verticală în jos.

Restricţii

  • 2 <= m, n <= 200
  • numărul de bomboane dintr-un pătrat este cel mult 1000

Exemple

el.in el.out
4 4
3 1 1 4
2 1 9 2
6 1 1 8
4 3 2 1
24
2 1 4 -3
prof. Nistor Moţ
Colegiul Naţional „Nicolae Bălcescu” Brăila
emotz_ro@yahoo.co.uk
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2010: greiere, divizori, kdist, pestera, partitie, sokoban, pitag, porumb, cheie, conferinta, chei, stelar, atelier, secv9, ny, radical, arbgraf, select, divk, bileprime, nx, reuniune, cazare, proiect, taler, atletism, echipa, ghinion, oldest, war, aliniere, sumb, cavaleri, joct, fluviu, camera616, aritm, stele, covor, subm, mess, secvnumber, cladire, ssmax, parcela, pion, subs, universitate, mahjong, rotund, sirmax, bdotcom, pack
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, tort1, 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, 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
surse trimise | ajutor