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

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


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

Gigel trebuie să cumpere n medicamente, numerotate de la 1 la n. Doctorul i-a dat m reţete de două tipuri, codificate cu numerele 1, 2 astfel:
1 - reţetă necompensată, adică preţul medicamentelor de pe reţetă se achită integral de către cumpărător;
2 - reţetă compensată 50%, adică preţul medicamentelor înscrise pe reţetă se înjumătăţeşte.
Se ştie că pe reţete nu există un alt medicament decât cele numerotate de la 1 la n şi o reţetă nu conţine două medicamente identice.
Dacă o reţetă este folosită atunci se vor cumpăra toate medicamentele înscrise pe ea.

Cerinţă

Scrieţi un program care să determine suma minimă de bani necesară pentru a cumpăra exact câte unul din fiecare dintre cele n medicamente, folosindu-se de reţetele avute la dispoziţie.

Date de intrare

Fişierul de intrare reteta2.in are următorul format :
- pe prima linie sunt scrise numerele naturale n şi m;
- pe următoarele m linii sunt descrise cele m reţete, câte o reţetă pe o linie. Linia care descrie o reţetă conţine tipul reţetei (1 necompensată sau 2 compensată), urmat de un număr natural q reprezentând numărul de medicamente de pe reţetă, apoi de q numere distincte din mulţimea {1, 2, ..., n} reprezentând medicamentele înscrise pe acea reţetă;
- pe ultima linie a fişierului de intrare sunt scrise n numere naturale separate prin câte un spaţiu, reprezentând în ordinea de la 1 la n, preţul medicamentelor.
Toate numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire reteta2.out va conţine o singură linie pe care va fi scris un număr real cu o singură zecimală, reprezentând suma minimă determinată.

Restricţii

1 <= N <= 20
1<= M <= 15
1 <=
preţul oricărui medicament <= 200
Pentru datele de test există întotdeauna soluţie.

Exemple

reteta2.inreteta2.outExplicaţii
4 5 2 1 3 2 2 2 3 1 1 1 1 3 4 1 2 1 1 3 8 20 2 16 45.0 Soluţia s-a obţinut prin folosirea primei şi celei de a patra reţete.
O altă soluţie, dar de cost mai mare, s-ar fi obţinut dacă se folosea reţeta a patra şi cea de a cincea.

autor: Prof. Dana Lica
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2008: ab2, iepuras, palind, auto, div, teatru, pm, submat, rezervatie, creioane, melci, mere2, felinare, joc3, 2numere, fi, tablou, borcane, mexc, tcast, dep, dist1, stiva, banda, pavare, poarta, aranjare, bile4, subgeom, albinuta1, curent, pviz, atac2, virus
De acelaşi autor: compus, taste, arce, balbe, drept, scor, sume3, spair, bitslang, police, tree, farfurii, caramele, apm, maraton, masina1, bomboane, soldati1, concurs1, puncte, pipe, camion, imax, litoral, dreptc, bal, prefix1, tablite, lanturi, loto, bila, popic, activ, game1, pitag, secv9, divk, taler, bdotcom, oak, ozn1, optim, puncte5, swap, tetris3, monede2, ssk
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, 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, 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, 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, plaja, 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
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, playlist, young, pizza1, 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, playlist, pizza1, 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
surse trimise | ajutor