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

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


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

renul despre care discutam este format dintr-o locomotiva si N vagoane (numerotate de la 1 la N, incepand de la locomotiva). In fiecare vagon se afla un numar cunoscut de pasageri (sa notam cu vi numarul de pasageri din vagonul i). Pasagerilor nu li se permite sa se deplaseze de la un vagon la altul.
Locomotiva s-a defectat si pentru a duce vagoanele la destinatie, pot fi utilizate 3 minilocomotive, aduse din statia de tren cea mai apropiata. O minilocomotiva poate trage un numar mic de vagoane (maxim M), iar in general cele 3 minilocomotive nu sunt suficiente pentru a trage toate vagoanele din care este format trenul.
O minilocomotiva poate trage o secventa de vagoane (vagoane consecutive ale trenului). Secventa de vagoane trasa de minilocomotiva 1 nu trebuie sa inceapa neaparat cu primul vagon (minilocomotiva 1 poate trage mai intai pe o linie moarta vagoanele de la inceputul trenului pe care nu le duce la destinatie si apoi sa preia secventa de maxim M vagoane pe care sa o duca la destinatie). Secventa de vagoane trasa de minilocomotiva 1 nu trebuie sa fie adiacenta cu secventa de vagoane trasa de minilocomotiva 2. Minilocomotiva 2 poate trage pe o linie moarta vagoanele situate intre ultimul vagon tras de locomotiva 1 si primul vagon pe care locomotiva 2 intentioneaza sa-l duca la destinatie.
In mod analog, secventa de vagoane trasa de minilocomotiva 2 nu trebuie sa fie adiacenta cu secventa de vagoane trasa de minilocomotiva 3.
De exemplu, sa presupunem ca trenul are N=7 vagoane, iar o minilocomotiva poate trage maxim M=2 vagoane. Sa consideram ca numarul de pasageri din fiecare vagon este:

1
2
3
4
5
6
7
35
40
50
10
30
45
60

Daca minilocomotiva 1 duce la destinatie vagoanele 1-2, minilocomotiva 2 duce vagoanele 3-4, iar minilocomotiva 3 duce vagoanele 6-7, numarul de pasageri care ajung la destinatie este 240 si acesta este maximul posibil.

Cerinta

Scrieti un program care sa determine numarul maxim de pasageri ce pot fi transportati la destinatie cu cele 3 minilocomotive.

Date de intrare


Fisierul de intrare tren1.in contine pe prima linie un numar natural N reprezentand numarul de vagoane. Cea de a doua linie contine N numere naturale separate prin cate un spatiu v1 v2 ... vN, reprezentand numarul de pasageri din fiecare vagon. Cea de a treia linie contine un numar natural M care reprezinta numarul maxim de vagoane care pot fi trase de o minilocomotiva.

Date de iesire

Fisierul de iesire tren1.out contine o singura linie pe care se afla numarul maxim de pasageri ce pot fi transportati cu 3 minilocomotive.

Restrictii

M<=N<=50000
vi<=100, pentru orice 1<=i<=N

Exemplu

tren1.in tren1.out
7
35 40 50 10 30 45 60
2
240

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi

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, 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, remi, m01, sir23, 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, remi, sir23, 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