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

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


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

În satul vecin există un teren agricol de formă dreptunghiulară împărţit în N*M pătrate elementare identice, dispuse alăturat câte M pe fiecare rând şi câte N pe fiecare coloană. Rândurile sunt numerotate de la 1 la N, iar coloanele de la 1 la M. Un pătrat elementar situat în teren pe rândul R şi coloana C este identificat prin coordonatele (R,C).
Suprafeţe dreptunghiulare din teren (formate fiecare din unul sau mai multe pătrate elementare alăturate) sunt revendicate de T fermieri din sat, în calitate de moştenitori, pe baza actelor primite de la strămoşii lor. Pentru că au apărut şi acte false, s-a constat că pot exista mai mulţi fermieri care revendică aceleaşi pătrate elementare.
În cele T acte ale fermierilor, suprafeţele dreptunghiulare sunt precizate fiecare prin câte două perechi de numere (X,Y) şi (Z,U), reprezentând coordonatele primului pătrat elementar din colţul stânga-sus al suprafeţei (rândul X şi coloana Y), respectiv coordonatele ultimului pătrat elementar situat în colţul dreapta-jos al suprafeţei (rândul Z şi coloana U).

Cerinţă

Scrieţi un program care să citească numerele naturale N,M,T,R,C apoi cele T perechi de coordonate (X,Y) şi (Z,U) precizate în acte (corespunzătoare suprafeţelor dreptunghiulare revendicate) şi care să determine:
1. numărul fermierilor care revendică pătratul elementar identificat prin coordonatele (R,C);
2. numărul maxim de fermieri care revendică acelaşi pătrat elementar;
3. numărul maxim de pătrate elementare ce formează o suprafaţă pătratică nerevendicată de niciun fermier.

Date de intrare

Fişierul teren1.in conţine pe prima linie un număr natural P care poate avea doar valoarea 1, valoarea 2 sau valoarea 3. Pe a doua linie a fişierului sunt scrise cinci numere naturale N, M, T, R, C, separate prin câte un spaţiu, cu semnificaţia din enunţ. Pe fiecare dintre următoarele T linii ale fişierului sunt câte patru numere naturale nenule XK YK ZK UK, separate prin câte un spaţiu, reprezentând perechile de coordonate (XK,YK) şi (ZK,UK) corespunzătoare terenurilor revendicate de cei T fermieri (1 ≤ K ≤ T).

Date de ieşire

Fişierul de ieşire teren1.out va conţine pe prima linie un număr natural reprezentând numărul fermierilor care revendică pătratul elementar identificat prin coordonatele (R,C) dacă cerinţa a fost 1, un număr natural reprezentând numărul maxim de fermieri ce revendică acelaşi pătrat elementar dacă cerinţa a fost 2, respectiv un număr natural reprezentând numărul maxim de pătrate elementare ce formează o suprafaţă pătratică nerevendicată de niciun fermier dacă cerinţa a fost 3.

Restricţii

3 ≤ N, M ≤ 180
3 ≤ T ≤ 100
1 ≤ R ≤ N
1 ≤ C ≤ M
1 ≤ XK ≤ ZK ≤ N şi 1 ≤ YK ≤ UK ≤ M pentru K=1,2,3,...,T
• Pentru rezolvare corectă a cerinţei 1 se acordă 20% din punctaj, pentru rezolvarea corectă a cerinţei 2 se acordă 20% din punctaj, iar pentru rezolvarea corectă a cerinţei 3 se acordă 60% din punctaj.

Exemple

teren1.interen1.outExplicaţii
1 3 5 3 2 2 2 3 2 3 1 2 3 3 2 1 2 3 2 Pătratul elementar cu coordonatele R=2 şi C=2 este revendicat de 2 fermieri.


2 3 5 3 2 2 2 3 2 3 1 2 3 3 2 1 2 3 3 Pătratul elementar cu coordonatele (2,3) este revendicat de 3 fermieri (numărul maxim de revendicări).
3 3 5 3 2 2 2 3 2 3 1 2 3 3 2 1 2 3 4 Sunt două suprafeţe pătratice nerevendicate de niciun fermier, formate fiecare din numărul maxim de patru pătrate elementare. Acestea au coordonatele: (1,4) şi (2,5) respectiv (2,4) şi (3,5).

autor: Prof. Carmen Mincă
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONIG 2015: cript, scadere, tv1, nebuni, spioni1, ssk, magic7, restaurare, sort2dist, echer, lightbot, iepuras1, inventie
De acelaşi autor: cri, suma4, joc16, alice, culegere, betasah, eoliene, piramide, traseu3
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, 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, fence, cifre6
surse trimise | ajutor