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

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


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

Se considera n gramezi de piese de remi, fiecare gramada continând un numar dat de piese. Gramezile sunt asezate pe masa în linie, una lânga cealalta, cu spatii între ele. Toate piesele trebuie asezate în k grupe egale, numarul total al pieselor permitând acest lucru.
Însa regula jocului spune ca o grupa va putea fi formata dintr-o gramada initiala sau prin punerea la un loc a doua sau mai multe gramezi vecine (succesive). Cum procedeul nu permite mutarea unor piese dintr-o gramada în alta, este posibil sa nu se poata obtine acelasi numar de piese în fiecare grupa, la sfârsit calculându-se o penalizare în felul urmator:
- pentru fiecare grupa penalizarea este data de numarul de piese suplimentare sau numarul de piese lipsa din grupa respectiva fata de numarul de piese dorit.
- penalizarea totala este suma penalizarilor pentru cele k grupe construite.
Astfel, daca se considera 7 gramezi cu 12, 9, 2, 11, 15, 5 si respectiv 2 pietre si daca se cere realizarea a 4 grupe, este de dorit sa obtinem 14 piese în fiecare grupa. Unind gramezile 1, 2 si 3 si gramezile 6 si 7 se obtin grupele de 23, 11, 15 si respectiv 7 piese. Penalizarile vor fi 9 ( 23-14 ), 3 ( 14-11 ), 1 ( 15-14 ) si 7 ( 14-7 ), iar penalizarea totala : 9 + 3 + 1 + 7 = 20.

Cerinta

Scrieti un program care sa determine o modalitate de grupare a gramezilor astfel încât penalizarea totala sa fie minima.

Date de intrare

Fisierul de intrare remi.in contine:
- pe prima linie valorile întregi n si k despartite printr-un spatiu;
- pe linia a doua n numere întregi (cu valori cuprinse între 0 si 255) reprezentând numarul de piese din fiecare gramada; numerele sunt despartite prin câte un spatiu si au proprietatea ca suma lor este divizibila cu k.

Date de iesire

Fisierul de iesire remi.out va contine pe prima linie penalizarea totala corespunzatoare gruparii alese.

Restrictii

n, k numere naturale, 1 <= k <= n <= 80

Exemple

remi.in remi.out remi.in remi.out
7 4
12 9 2 11 15 5 2
16 8 6
99 139 92 157 101 205 159 44

282

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi
Contact:ema at mail.dntis.ro

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, m01, robot1, na, sir23, paralel, zaruri, bomboane, dotnet, divizor, tren1, joc5, tvshow, pachete, soldati1, echipe, omizi, suma1, aedaro, concurs1, windows, comb, renju, latime, vectori, ghici, subperm, puncte, mere1, spirala, distanta, piloti
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, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, 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 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, 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, 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
Software recomandat
surse trimise | ajutor