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

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


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

FC Campion Romania se pregateste pentru finala Ligii Campionilor Europeni. Pentru aceasta, cei N jucatori ai sai se antreneaza zilnic. Pentru fiecare dintre ei se cunoaste intervalul [T1,T2) când este prezent la antrenament. Pentru ca antrenamentul sa fie mai eficient, jucatorii nu se antreneaza toti la un loc, ci sunt împartiti în K echipe. Fiecare jucator face parte din exact o echipa, dar este posibil ca din unele echipe sa nu faca parte nici un jucator. Deoarece munca în echipa este foarte importanta, antrenamentul fiecareia dintre cele K echipe se poate desfasura numai daca sunt prezenti toti jucatorii care fac parte din acea echipa. În aceste conditii, durata de antrenament a fiecarei echipe este egala cu lungimea intervalului de timp în care sunt prezenti la antrenament toti jucatorii din echipa respectiva. Întrucât finala se apropie, conducerea clubului doreste ca suma duratelor de antrenament ale fiecarei echipe sa fie maxima.

Cerinta
Determinati o împartire în K echipe a celor N jucatori, astfel încât suma duratelor de antrenament sa fie maxima.

Date de intrare
Pe prima linie a fisierului echipe.in se afla doua numere întregi, separate prin spatii: N si K. Pe urmatoarele N linii se afla câte doua numere întregi separate prin spatii, A si B, reprezentând intervalele de timp în care sunt prezenti jucatorii la antrenament.

Date de iesire
În fisierul echipe.out veti afisa suma maxima a duratelor de antrenament corespunzatoare unei împartiri pe echipe optime.

Restrictii si precizari
· 1 <= K <= N <= 250
· 0 <= A < B <= 1 000 000
· Daca o echipa contine 0 jucatori, durata ei de antrenament este 0.
· Daca nu exista nici un moment în care toti jucatorii unei echipe sa fie prezenti simultan la antrenament, atunci durata de pregatire a echipei respective este 0.

Exemplu

echipe.in echipe.out Explicatie

8 4
0 11
0 10
1 11
2 12
3 13
4 14
5 15
19 28

36

Din prima echipa fac parte jucatorii 1, 2 si 3. Din a doua echipa vor face parte jucatorii 4 si 5. Din a treia echipa fac parte jucatorii 6 si 7, iar a patra echipa îl va contine doar pe jucatorul 8. Intervalele de antrenament pentru fiecare din cele 4 echipe sunt: [1,10) , [3,12) , [5,14) , [19,28).

Andreica Mugurel Ionut
Universitatea Politehnica Bucuresti
Contact: mugurel_ionut at yahoo dot com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2004: cifre1, super, apm, bile1, factk, schimb, caini, secvreg, descfib, maraton, masina1, otilia, multiplu, tub, pasune, remi, m01, robot1, na, sir23, paralel, zaruri, bomboane, dotnet, divizor, tren1, joc5, tvshow, pachete, soldati1, omizi, suma1, aedaro, concurs1, windows, comb, renju, latime, vectori, ghici, subperm, puncte, mere1, spirala, distanta, piloti
De acelaşi autor: autobuze, bile, complex, balaur, vmem, kreg, ro, jobs, senzori, agitatie, center, algebra, tgraf, bcast, promo, asmax, sediu, granita, string, poligon1, csir, lsort, zoo, bombo, ab3, soc, rsp, tcast, tj, lanterna, base3, color, trans, ic, xp, v2d, ppcover, carray, asfalt1, module, gxor
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, 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, 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
surse trimise | ajutor