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

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


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

Primăria oraşului Constanţa reamenajează plaja din staţiunea Mamaia. Aceasta este reprezentată ca o zonă dreptunghiulară cu lăţimea de a unităţi şi lungimea de b unităţi. Pe plajă sunt trasate linii paralele cu laturile dreptunghiului astfel încât să formeze pătrate cu latura de o unitate, numite zone.
Pe plajă se vor pune obiecte: umbrele şi prosoape. Se consideră că dacă un obiect intră în interiorul unei zone, o ocupă în întregime.
Se poziţionează u umbrele de soare. Într-o zonă se poate aşeza cel mult o umbrelă.
N turişti vin şi îşi aşează prosoapele pe plajă. Un prosop are formă dreptunghiulară şi va fi aşezat paralel cu laturile dreptunghiului. Turiştii îşi pot aşeza prosoapele pe zone libere sau peste prosoape deja aşezate. Un turist nu îşi poate aşeza însă prosopul pe plajă dacă suprafaţa acoperită de acesta include cel puţin o zonă în care se află o umbrelă.
M localnici au suprafeţe favorite pentru aşezarea prosoapelor. O suprafaţă favorită are forma unui dreptunghi cu laturile paralele cu laturile dreptunghiului care marchează plaja. După ce turiştii termină aşezarea prosoapelor, localnicii verifică dacă zonele din suprafaţa favorită sunt libere (neacoperite de prosoape aşezate de turişti sau de umbrele).

Cerinţă

Scrieţi un program care să determine:
• numărul de turişti care au reuşit să îşi aşeze prosoapele pe plajă;
• numărul de localnici ale căror zone favorite sunt libere.

Date de intrare

Fişierul de intrare plaja.in conţine pe prima linie trei numere naturale, separate prin câte un spaţiu, a, b şi u, având semnificaţia din enunţ. Fiecare dintre următoarele u linii conţine o pereche de numere naturale x y, reprezentând o zonă în care se găseşte o umbrelă. Următoarea linie din fişier conţine un număr natural N, reprezentând numărul de turişti. Următoarele N linii descriu prosoapele turiştilor. Fiecare linie conţine 4 numere naturale x1 y1 x2 y2, ce reprezintă colţurile unui prosop. Linia următoare conţine o singură valoare, M, reprezentând numărul de localnici. Pe următoarele M linii se află câte 4 numere, separate prin câte un spaţiu, x’1 y’1 x’2 y’2, ce reprezintă colţurile unei suprafeţe favorite.

Date de ieşire

Fişierul de ieşire plaja.out conţine pe prima linie două numere naturale separate printr-un spaţiu. Primul număr reprezintă numărul de turişti care şi-au aşezat prosoapele pe plajă, iar cel de-al doilea număr reprezintă numărul de localnici ale căror zone favorite sunt libere.

Restricţii

Colţul din stânga sus al zonei dreptunghiulare are coordonatele (1,1)
3 ≤ a, b ≤ 2 000
0 ≤ u ≤ 100
3 ≤ m, n ≤ 100 000

Un prosop descris de (x1,y1,x2,y2) va avea 1 ≤ x1 ≤ x2 ≤ a şi 1 ≤ y1 ≤ y2 ≤ b
O suprafaţă favorită descrisă de (x’1,y’1,x’2,y’2) va avea 1 ≤ x’1 ≤ x’2 ≤ a şi 1 ≤ y’1 ≤ y’2 ≤ b

Exemple

plaja.inplaja.outExplicaţii
12 13 1 6 11 4 3 4 7 7 5 6 8 8 9 2 10 3 5 10 8 12 3 1 8 3 13 10 3 12 4 2 10 5 12 3 2 Ultimul turist nu îşi poate aşeza prosopul. Zona favorită al celui de-al doilea localnic nu este liberă.



autor: Prof. Cristina Sichim
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2010: diff, kmax, minuni, stalpi1, submatrix1, dreptunghiuri, gaz, xp, petrecere, triunghi2, cmmmc, simetric1, cern, pesti, tango, arb1, v2d, xor2, cuiburi, telefon, teroristi
De acelaşi autor: ruleta2, tetris, oua, tren4, pesti, carte1, xy, porumb1, plus, sudoku1, covor1
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, 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 vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
surse trimise | ajutor