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

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


Timp maxim de executie/test:
1.2 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Amicul nostru Vasile a devenit foarte bogat si doreste sa deschida un lantisor de K pizzerii, care sa primeasca si comenzi pentru acasa.
Vasile are în vedere M potentiale locatii pentru pizzeriile sale. O pizzerie poate onora toate comenzile din raza sa de actiune (o zona circulara de raza R, cu centrul în locatia restaurantului).
Se stie ca studentii sunt mari consumatori de pizza, asa ca Vasile îi considera clienti siguri. Din acest motiv Vasile a identificat locatiile a N camine studentesti, precum si numarul de studenti din fiecare camin.
Vasile vrea sa aleaga K dintre cele M locatii posibile pentru pizzeriile sale, astfel încât numarul total de clienti siguri sa fie cât mai mare posibil.

Cerinta

Scrieti un program care sa determine numarul maxim de clienti siguri pe care Vasile se poate baza.

Date de intrare

Prima linie a fisierului de intrare pizza1.in contine doua numere întregi K si R, separate printr-un spatiu, reprezentând numarul de pizzerii pe care vrea sa le deschida Vasile si respectiv raza de actiune a fiecarei pizzerii.
Pe cea de a doua linie se afla un numar natural M, reprezentând numarul de locatii posibile pentru pizzerii.
Fiecare dintre urmatoarele M linii contine doua numere întregi X si Y, separate printr-un spatiu, reprezentând coordonatele unei locatii (in ordinea abscisa ordonata).
Pe urmatoarea linie se afla un numar natural N, reprezentând numarul de camine studentesti.
Pe fiecare dintre urmatoarele N linii se afla informatii despre câte un camin sub forma a trei numere întregi separate prin câte un spatiu X Y S cu semnificatia "în punctul de coordonate X, Y exista un camin studentesc în care locuiesc S studenti".

Date de iesire

Fisierul de iesire pizza1.out va contine o singura linie pe care va fi scris numarul maxim de clienti siguri pe care Vasile se poate baza.

Restrictii

1 <= K <= 10
1 <= R <= 500

K <= M <= 20
Toate coordonatele sunt numere întrregi, -1000 <= X,Y <= 1000
1 <= N <= 100
1 <= S <=100
Spunem ca un camin este în raza de actiune a unei pizzerii daca distanta de la camin la pizzerie este mai mica sau egala cu R.
Nu exista doua locatii cu aceleasi coordonate.

Exemple

pizza1.in pizza1.out pizza1.in pizza1.out
2 2
3
1 0
4 0
7 0
4
0 0 1
3 0 7
5 0 9
8 0 1
18 2 2
3
-2 0
0 1
3 0
8
-3 1 1
-3 0 1
-3 -1 1
-2 -1 1
0 0 3
0 2 1
2 1 3
4 0 2
12

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2005: cuc, prime, radio, text2, honest, police, comori, patrate3, fisc, ref, pcod, zmeu, loc, nr01, scor2, judete, strict, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, jobs, leaves, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, program, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, carte, set, barbie, labirint, firma1, vile, game, donald, ambigram, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, jokes, albine, lot, atac1, monede1, count, exam, herbert, sudoku, bio, metro
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre combinatorică: manevre, carti, bonuri, test, cub, nspecial, circuit, numere, cs, pluricex, parent, gray, siruri, anagrame, party, net, scaune, sir, monede, aztec, nrcuv2, perm, race, hanoig, red, grup, hperm, depou, grazing, pm, reteta2, playlist, young, albine, caramele, teatru1, tub, robot1, sir23, soldati1, concurs1, comb, expresii, arbnr, cod1, munte, shgraf, desc, lex, munte1, maxperm, role, avere, vizibil, prime1, hexa, patrat, carti2, puncte2, pact, aranjari, numere5, borg, acolor, sg1, perfect, cifru2, bile4, pviz, culmi1, piramida1, trapez, frunze, sir7, logic, coduri, jetoane, kperms, tablite, secvpar, lego, permutari, binperm, multiplu1, operatii, fotbal, kbiti, jucarii, bradut, expozitie, parbit, kmax, petrecere, tango, rege, cd1, cifru3, kcons, bubblesort, hawaii, randomizare, kdist, reuniune, echipa, ghinion, cavaleri, camera616, covor, subm, grupuri, pavari, asfalt, adunscad, rotund, sport2, arbore1, lant1, module, nrperm, oneton, nrpomi, cover1, nrpal, probleme, optim, poly, vot1, sudoku1, flori2, xnumere, showroom, cntgcd, subsets, nkd, nrgraf, spion1, puteri, stiva1, permtr, relatii, 2sah, matcnt, magic7, nmult, roua
Despre generare: taste, pluricex, balbe, magic3, formule, grup, zmeu, nr01, reteta2, playlist, caramele, caini, tvshow, adevar, prime1, hexa, premii1, carti2, bile4, hof, matrx, cubinvers, arctir, guess, minmax, stele, tablou1, adunscad, sumprod, prisme, operatii1, expeval, triburi1, optim, patru, genab, dineu, cumpanit, nkd, relatii, wb
Software recomandat
surse trimise | ajutor