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

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


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

Se consideră N intervale închise, având extremităţile numere naturale cuprinse între 1 şi L.
Fiecare număr natural i din intervalul [1, L] are asociată o pondere ci.
Numim acoperire o mulţime de numere naturale cuprinse între 1 şi L cu proprietatea că fiecare interval conţine cel puţin un element al mulţimii.
Costul unei acoperiri este egal cu suma ponderilor numerelor din acoperire.

Cerinţă

Pentru un set de intervale dat să se determine costul minim al unei acoperiri.

Date de intrare

Fişierul de intrare cover.in conţine pe prima linie cele două numere naturale N L separate printr-un spaţiu. Pe următoarea linie se află L numere naturale separate prin câte un spaţiu c1 c2 ... cL reprezentând ponderile numerelor naturale din intervalul [1, L]. Următoarele N linii conţin fiecare câte două numere naturale a b (1 ≤ a ≤ b ≤ L) reprezentând extremităţile intervalelor.

Date de ieşire

Fişierul de ieşire cover.out va conţine o singură linie pe care va fi scris un număr natural reprezentând costul minim al unei acoperiri.

Restricţii

1 ≤ N ≤ 60 000
1 ≤ L ≤ 1 000 000
0 ≤ ci ≤ 1024
, pentru orice 1 ≤ i ≤ L
Pentru 40% din teste N ≤ 1000 şi L ≤ 10000.

Exemple

cover.incover.outExplicaţii
2 5 100 5 9 6 90 1 3 3 5 9 Se construieşte acoperirea {3} care are costul 9. Elementul 3 aparţine ambelor intervale date în fişierul de intrare.
Există şi alte acoperiri posibile de exemplu {2, 4} dar costul acesteia este 11 care nu este minim.
4 10 1 3 6 4 5 1 0 1 3 2 1 3 3 5 6 9 4 4 5 Se construieşte acoperirea {1, 4, 7} care are costul 5.

autor: Adrian Vladu
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Probleme recomandate
De la ONI 2007: ceas, numere4, cifru, oua, turn, div3, jeton, politic, trecere, agitatie, lacuri, secv, sotron, triunghi, apel, castel, excursia, matricea, randuri, zidar, desc, felinar, joc6, log, maxq, tric, dist, munte1, promo, puncte1, role
De acelaşi autor: castel, zidar, centru
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, 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, cuiburi, 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 deque: platforma, compus, copaci, sirag, leaves, secvreg, drept1, stalpi1, gropi1
Despre recurenţă: nrbun2, nrbun, grupe, palind, siruri, vecini, net, pioni, sir2, perm, red, sume3, pavaj, div3, descfib, robot1, soldati1, expresii, agitatie, aparitii, apel, randuri, zidar, log, maxq, dist, munte1, sir1, vizibil, csir, puncte2, aranjari, numere5, anticip, bsir, evantai, sg1, zumzi, lant, perfect, cifru2, numere8, poarta, pviz, poli, desert, echitabil, patrate6, kperms, jump, petrecere, rege, triunghi3, sir9, arbore1, fibgcd, cds, wg, module, nr0, cover1, culori1, flori2, cntgcd, 2sah, matcnt, nmult
surse trimise | ajutor