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

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


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

Firma Petrom are n benzinării amplasate de-a lungul autostrăzii Soarelui. Benzinăriile sunt numerotate de la 1 la n în ordinea amplasării pe autostradă.
Poziţiile benzinăriilor sunt cunoscute, fiind specificate prin distanţele d1, d2, …, dn (di reprezintă distanţa de la sediul firmei Petrom până la benzinăria i). Sediul firmei Petrom este amplasat la intrarea pe autostrada Soarelui.
În k dintre aceste benzinării firma doreşte să amenajeze depozite de combustibil, care să alimenteze benzinăria respectivă, dar şi alte benzinării învecinate. Fiecare benzinărie va fi alimentată de la depozitul cel mai apropiat.
Costul de transport pentru o amplasare a depozitelor dată va fi egal cu suma distanţelor de la fiecare benzinărie la depozitul de la care se alimentează.

Cerinţă

Scrieţi un program care să determine benzinăriile în care trebuie să construite depozite, astfel încât costul de transport să fie minim.

Date de intrare

Fişierul de intrare petrom.in conţine pe prima linie două numere naturale separate prin spaţiu n şi k, reprezentând numărul de benzinării şi respectiv numărul de depozite care trebuie construite.
Pe următoarele n linii sunt scrise n numere naturale d1, d2, …, dn, câte un număr pe o linie, reprezentând distanţele de la sediul Petrom la cele n benzinării.

Date de ieşire

Fişierul de ieşire petrom.out va conţine pe prima linie costul de transport (minim posibil).
Pe următoarele k linii sunt scrise benzinăriile în care vor fi construite depozite pentru a obţine costul minim, câte o benzinărie pe o linie.

Restricţii

1 ≤ n ≤ 400
1 ≤ k ≤ 300
k ≤ n
0 < d1 < d2 < … < dn ≤ 30000

Dacă există mai multe soluţii puteţi determina oricare dintre acestea.
Pentru fiecare test, se acordă 40% din punctaj pentru determinarea costului minim şi 100% pentru rezolvarea integrală.

Exemple

petrom.inpetrom.outExplicaţii
6 3 5 6 12 19 20 27 8 2 4 6 Depozitul 1 va fi construit în benzinăria 2 şi alimentează benzinăriile 1, 2, 3. (Cost: 1+0+6=7)
Depozitul 2 va fi construit în benzinăria 4 şi alimentează benzinăriile 4, 5. (Cost: 0+1=1)
Depozitul 3 va fi construit în benzinăria 6 şi alimentează benzinăria 6.
(Cost: 0)

autor: Prof. Emanuela Cerchez
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2006: borg, diamant, matrice1, ratina, vitale, acolor, cifru1, evo, part, trasee, bombo, cub2, prieteni2, sg1, fact, limbaj, panouri, pereti, sant1, zumzi, adun, sport1, baschet1, mere3, roboti, tzigla, morse, powerpuff
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, 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, 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, remi, 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, 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