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

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


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

Vasile şi-a cumpărat un teren de formă dreptunghiulară pe care vrea să-şi construiască o casă.  Din păcate, unele zone din teren sunt fie ocupate cu pomi, fie improprii unei construcţii, astfel încât el doreşte să determine o zonă cât mai mare din teren pe care să poată să-şi construiască casa. Fiecare zonă pe care nu se poate construi are exact dimensiunea 1 x 1. Şi mai are un necaz: arhitectul i-a proiectat casa … pătrată. În figura alăturată se vede un exemplu de astfel de teren: are dimensiunile de 6 x 9 şi trei zone pe care nu se poate construi (zonele de coordonate (2, 6), (3, 2) şi (5, 7)). În figură se observă faptul că cea mai mare zonă pătrată este zona indicată (de la (3, 3) la (6, 6)), deşi există zone dreptunghiulare de arie mai mare.

Cerinţă

Determinaţi latura celei mai mari zone de forma unui pătrat existente în terenul lui Vasile, zona pe care se poate construi.

Date de intrare

Fişierul de intrare cladire.in conţine pe prima linie dimensiunile m n ale terenului, două numere naturale separate printr-un spaţiu. Linia a doua a fişierului de intrare conţine un număr natural k, reprezentând numărul de zone pe care nu se poate construi. Următoarele k linii ale fişierului conţin fiecare câte două numere naturale x y, separate printr-un spaţiu, reprezentând fiecare coordonatele unei astfel de zone.

Date de ieşire

Fişierul de ieşire cladire.out conţine pe prima linie un singur număr natural L, reprezentând lungimea laturii celei mai mari zone de formă pătrată pe care se poate construi care se găseşte pe terenul lui Vasile.

Restricţii

  • 0 < m, n < 1001
  • 0 <= k < m*n
  • Numerotarea liniilor şi coloanelor se face de la 1.

Exemple

cladire.in cladire.out
6 9
3
2 6
3 2
5 7
4

 

prof. Marinel Şerban
Colegiul Naţional „Emil Racoviţă” Iaşi
marinel_serban@yahoo.com
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, ssmax, parcela, pion, subs, universitate, el, mahjong, rotund, sirmax, bdotcom, pack
De acelaşi autor: premii, finala, fractii, trei, manevre, nrcuv, an, vopsea, opmat, tramvai, bipal, kpal, sarpe, replace, factori, barca, perechi, grupe, cod, reactii, factura, decript, trenuri, holo, cifre, firma, tribile, mesaj, tricouri, pajura, monede, programs, fry, repeat, red, pavaj, bacan, nrbinar, invest, cutie2, loc, depou, nr3, zid, felinare, sir3, sqr, carte, labirint, stea, count, evaluare, super, schimb, zaruri, vectori, spirala, desen1, rima, ceas1, romane, sms, bac, excursia, joc7, furnici, munte1, cezar, marcare, excursie1, culmi, sume1, schi, nr4, fractie, cod3, medii, tren3, top, sant1, imagine, ocr, perfect, pluton, reforma, alee, ceas2, paritate, borcane, aranjare, comoara1, culmi1, reactivi, submult, sablon1, sir8, sume2, dansatori, smith, tom, matriosca, asociativ, control1, calorii, immortal, concat, mat, cubinvers, mine, divizori, cheie, stelar, joct, minmax, adunscad, razboi, ore, oras1, sumprod, prisme, operatii1, lgdrum, unupatru, chibrituri, extraprime, prieten, rebus1, grindina, opmult, betisoare, antitero, clase, pagini, ornament, ordine, spioni1
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, 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