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

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


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

În ţara Nicăieri există N cuiburi. Cuiburile sunt reprezentate în plan fie prin cercuri, fie prin dreptunghiuri cu laturile paralele cu axele. Pentru două cuiburi A şi B spunem că A se cuibăreşte în B dacă orice punct din interiorul sau de pe marginea cuibului A se află în interiorul sau pe marginea cuibului B. Numim o cuibăreală o submulţime de cuiburi A1, A2, A3, ..., Ak, în care Ai este cuibărit în Ai+1, pentru fiecare 1 <= i < k.

Cerinţă

Pentru cele N cuiburi date, scrieţi un program care găseşte cardinalul maxim al unei cuibăreli. Cardinalul unei cuibăreli este egal cu numărul de cuiburi care alcătuiesc cuibăreala.

Date de intrare

Pe prima linie a fişierului de intrare cuiburi.in se găseşte numărul natural N, reprezentând numărul de cuiburi. Pe următoarele N linii vor fi descrise cele N cuiburi astfel: primul număr t de pe fiecare linie va fi 0 sau 1. Dacă t este 0, atunci pe linie se vor mai găsi 4 numere naturale lx ly rx ry, separate prin câte un spaţiu. Perechea (lx, ly) reprezintă colţul stânga-jos al dreptunghiului, iar perechea (rx, ry) colţul dreapta sus al dreptunghiului. Dacă t este 1, atunci pe linie se mai găsesc încă trei numere naturale x y r, unde (x, y) reprezintă centrul cercului, iar r raza cercului.

Date de ieşire

În fişierul de ieşire cuiburi.out va conţine un singur număr natural reprezentând cardinalul maxim al unei cuibăreli.

Restricţii

• Cuiburile se pot intersecta.
1 ≤ N ≤ 2000
lx ≤ rx
ly ≤ ry
• Pentru 20% din teste, N ≤ 20
• Pentru 30% din teste, toate cuiburile vor fi dreptunghiuri
• Pentru 30% din teste, toate cuiburile vor fi cercuri
• Coordonatele şi razele sunt numere naturale mai mici sau egale cu 30 000

Exemple

cuiburi.incuiburi.outExplicaţii
8 0 1 1 5 5 0 6 1 8 2 1 9 9 2 0 3 1 5 3 0 2 2 4 4 1 3 3 1 0 2 2 4 4 0 9 9 11 15 4 Cuibăreala de cardinal maxim este alcătuită din cuiburile cu indicii 6, 5, 7, 1.

autor: Marius Dumitran
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2010: diff, kmax, minuni, stalpi1, submatrix1, dreptunghiuri, gaz, xp, petrecere, triunghi2, cmmmc, simetric1, cern, pesti, plaja, tango, arb1, v2d, xor2, telefon, teroristi
De acelaşi autor: lcdr, jb
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre geometrie: forum, supertri, ozn, detinut, atac, afise, mere, ff, teren, volei, aven, patrate, robot, pahare, pendul, robot2, dragon, poligon, druid, laser, patrate3, ploaia, donald, lot, atac1, arcas, paralel, dotnet, aedaro, vectori, spirala, distanta, triunghi, center, harta1, seceta, antena, poligon1, benzina, zoo, texan, oypara, dreptc, mosia, sea, poligon3, poligon2, snipers, basm, cetati, placa, nori, cerc, smin, cern, acerc, select, proiect, poligon4, terenuri, monoton, acoperire, capra, testament, jb, sdmin, ozn1, parc1, gsm, triunghi5, puncte6, romb1, dreapta, grindina, tdrept
surse trimise | ajutor