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

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


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

Se consideră o matrice dreptunghiulară A cu m linii şi n coloane cu valori 0 sau 1, liniile şi coloanele fiind numerotate de la 1 la m, respectiv de la 1 la n. Numim dreptunghi de colţuri (x1,y1) (x2,y2) cu x1<x2 şi y1<y2 mulţimea elementelor Aij cu x1≤i≤x2 si y1≤j≤y2. Numim perimetru al dreptunghiului de colţuri (x1,y1) (x2,y2) mulţimea elementelor Aij pentru care (i=x1 şi y1≤j≤y2) sau (i=x2 şi y1≤j≤y2) sau (j=y1 şi x1≤i≤x2) sau (j=y2 şi x1≤i≤x2).

Cerinţă

Determinaţi diferenţa maximă dintre numărul de elemente egale cu 1 şi numărul de elemente egale cu 0 aflate pe perimetrul aceluiaşi dreptunghi, precum şi numărul de dreptunghiuri pentru care se obţine această diferenţă.

Date de intrare

Pe prima linie a fişierului de intrare peri.in sunt scrise numerele m şi n, separate printr-un singur spaţiu. Pe următoarele m linii este dată matricea A, numerele de pe aceeaşi linie fiind separate de câte un spaţiu.

Date de ieşire

Fişierul de ieşire peri.out va conţine o singură linie pe care se află două numere întregi separate printr-un spaţiu. Primul număr este diferenţa maximă dintre numărul de elemente 1 şi numărul de elemente 0 de pe perimetrul unui dreptunghi. Al doilea întreg este numărul de dreptunghiuri pentru care diferenţa dintre numărul de elemente 1 şi numărul de elemente 0 de pe perimetru este maximă.

Restricţii

1 <= m, n <= 250
Prin diferenţă nu se înţelege diferenţă în valoare absolută!

Exemple

peri.inperi.out
4 5 1 0 0 1 0 0 1 1 0 0 0 1 0 1 0 1 1 1 0 1 4 2

autor: Prof. Nistor-Eugen Moţ
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2004: cuvinte1, gaina, materom, puncte3, rez, sortari, base3, coach, color, magic5, patrate6, turnuri, invsort, trans, politie, sea, poligon3, sir7, poligon2, logic, coduri, snipers, sablon1, submdisj, v, jetoane, prodmax, printesa, palindrom, reziston
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, atelier, radical, pion, el, 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, 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, ssk, teren1, fence, cifre6
surse trimise | ajutor