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

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


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

Într-o grădină botanică zonele în care se găsesc plante aparţinând aceleaşi specii sunt înconjurate de gard viu, de grosime neglijabilă. O specie ocupă o singură zonă. Suprafaţa grădinii, de formă dreptunghiulară, este împărţită în porţiuni de 1x1. Fiecare porţiune poate avea (sau nu) pe fiecare din laturile dinspre V, N, E sau S gard viu.

Cerinţă

Cunoscând planul codificat al grădinii determinaţi:
– numărul speciilor de plante ce se găsesc în grădină;
– suprafaţa maximă ocupată de o singură specie;
– suprafaţă de arie maximă ce se poate obţine prin unirea a două zone, precum şi poziţia porţiunii de gard (de dimensiune 1) prin a cărei îndepărtare se obţine această suprafaţă.

Date de intrare

Fişierul de intrare gradina.in are structura:
n m
a11 a12 ... a1m
a21 a22 ... a2m
...
an1 an2 ... anm


unde

n, m - lungimea respectiv lăţimea grădinii exprimate în metri
a11 a12 ... a1m - descriere linia 1 pentru planul grădinii
a21 a22 ... a2m - descriere linia 2 pentru planul grădinii
...
an1 an2 ... anm - descriere linia n pentru planul grădinii
unde aij reprezintă codificările porţiunilor din suprafaţa grădinii, astfel:
- 0 daca nu are gard viu pe nici una din laturile V,N,E,S
- la codificare se adaugă:
1 dacă există gard viu spre V
2 dacă există gard viu spre N
4 dacă există gard viu spre E
8 dacă există gard viu spre S

Date de ieşire

Fişierul de ieşire gradina.out are structura:
Ns
Amax
aria lmax cmax dmax


unde

Ns - numărul speciilor de plante
Amax - aria maximă
aria lmax cmax dmax - aria ce se obţine prin unirea a două zone, linia, coloana şi latura (N, E, S, V) porţiunii de gard ce trebuie eliminată, separate prin câte un spaţiu.

Restricţii

1 <= N, M <= 20
- în cazul în care există mai multe soluţii de obţinere a ariei maxime se va indica cea pentru care numărul liniei zonei eliminate este minim, iar dacă există mai multe soluţii cu numărul de linie minim, cea care are numărul coloanei minim

Exemple

gradina.ingradina.outExplicaţii
4 5 3 6 15 3 6 1 0 14 1 4 9 12 7 9 12 11 10 12 11 14 5 7 13 2 3 E Configuraţia iniţială a grădinii (pentru exemplul dat) şi după unirea celor două zone detectate:



propunător: Prof. Marinel Şerban
Liceul de Informatica
marinel.serban@gmail.com
Articole recomandate
Probleme recomandate
De la OMI Iaşi 2002: cofetar, coment, matrice4, numere9, sume2
Despre backtracking: acop, bipal, magic2, vagoane, friends, tricouri, festival, numar, pento, ro, jobs, onu2, sir3, cai1, labirint, dans, ham, sudoku, caramele, linie, puncte, castel, excursia, joc7, pattern, avere, paianjen, medii, monkey, scara1, numere8, banda1, spirala1, cofetar, placa, smin, jucarii, immortal, concat, cubinvers, codif, izvor, avioane, jb, prisme, triburi1, genab, dineu, antitero, ornament, virgule
Despre recursivitate: tren, mere, chimie, sarpe, soldati, formule, infinit, compress, ploaia, cartoane, sub, metro, windows, lacuri, apel, maxq, pav, joc11, paianjen, suma2, monkey, csir, lsort, imagine, dir, desert, echitabil, rez, logic, links, dreptunghiuri, expresie1, cumpanit, reziston, antitero, sablon3
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, 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, ssdj, cript, ssk, teren1, fence, cifre6
Despre fill: rebus, sarpe, insule, lacuri, zuzu, joc11, dreptunghiuri, drenaj, fillmat, parcela, acces, tsunami, betasah, zona, zone, taxa, foto, ferma1, antitero, robotzi
Despre operaţii pe biţi: barfa, cod, gray, cartonase, plimbare, excursie, xor, vector, ro, nrbinar, radio, chimie2, dans, metro, caini, newcomp, viteza, bcast, aritma, pereti, morse, paritate, xor2, game1, efect, gxor, lgdrum, qtri, patrate7, panda, cript
surse trimise | ajutor