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

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


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

Păcală a reuşit să ducă la bun sfârşit înţelegerea cu boierul căruia-i fusese slugă şi, conform învoielii, boierul trebuie să-l răsplătească dându-i o parte din livada sa cu pomi fructiferi. Boierul este un om foarte ordonat, aşa că livada sa este un pătrat cu latura de N metri unde, pe vremuri, fuseseră plantate N rânduri cu câte N pomi fiecare. Orice pom fructifer putea fi identificat cunoscând numărul rândului pe care se află şi poziţia sa în cadrul rândului respectiv. Cu timpul, unii pomi s-au uscat şi acum mai sunt doar P pomi. Păcală trebuie să-şi delimiteze în livadă o grădină pătrată cu latura de K metri.

Cerinţă

Cunoscând dimensiunile livezii şi grădinii, numărul pomilor din livadă şi poziţia fiecăruia, determinaţi numărul maxim de pomi dintr-o grădină pătrată de latură K şi numărul modurilor în care poate fi amplasată grădina cu numărul maxim de pomi.

Date de intrare

Fişierul gradina1.in conţine pe prima linie numerele naturale N P K, separate prin câte un spaţiu, cu semnificaţia din enunţ. Pe următoarele P linii se află câte 2 numere naturale Lin şi Col, separate printr-un spaţiu, reprezentând numărul rândului, respectiv poziţia în rând a fiecărui pom din livadă.

Date de ieşire

Fişierul gradina1.out va conţine pe prima linie numărul maxim de pomi fructiferi dintr-o grădină pătrată cu latura de K metri. Pe a doua linie va fi scris numărul de posibilităţi de a amplasa grădina astfel încât să conţină numărul maxim de pomi determinat.

Restricţii

• 2 ≤ N ≤ 1000
• 1 ≤ P ≤ N2
• 1 ≤ K ≤ N

Exemple

gradina1.ingradina1.outExplicaţii
12 10 5 4 3 5 5 6 8 7 3 7 7 8 8 9 3 9 6 10 10 11 5 5 5 Grădina lui Păcală poate avea maximum 5 pomi fructiferi.
Ea poate fi amplasată în 5 moduri, având colţul stânga-sus de coordonate:
(5, 3), (5, 4), (5, 5), (6, 6), (7, 3).

autor: Prof. Alin Burţa
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2013: split, momente, secvente2, flori2, romb1, cumpanit, spider, zone, taxa, ausoara, drumuri2, confuzie, xnumere, bemo, aranjare2, showroom, cntgcd
De acelaşi autor: picnic, expresie, origami, magic3, suma, race, balls, pcod, cat, cai1, cub1, cifru, cuburi2, cub2, adun, dir, atac2, comp, mxl, joc19, cifru5, joc21
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, 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, 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