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

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


Timp maxim de executie/test:
0.3 secunde
Memorie totala disponibila/stiva:
2 MB/1 MB

Zaharel are N copaci in gradina din spatele casei sale, asezati in linie, numerotati convenabil de la stanga la dreapta cu numere de la 1 la N. Dorind ca gradina lui sa arate cat mai frumos si uniform el si-a propus sa minimize diferenta maxima intre inaltimile copacilor adiacenti. Copacii nu pot fi mutati din loc, dar inaltimile lor pot fi micsorate sau marite (folosind tehnici moderne de gradinarit). Fiecare copac are o inaltime Hi si un cost Ci pentru a ii mari sau micsora inaltimea cu o unitate. 

Cerinta

Stiind ca are la dispozitie un buget de valoare K determinati valoarea minima pentru diferenta maxima intre inaltimile copacilor adiacenti.

Date de intrare

Pe prima linie a fisierului de intrare copaci.in sunt scrise cele doua numere naturale N, K, separate prin spatii. Pe urmatoarele N linii se vor scrie cate doua numere naturale Hi, Ci, separate prin spatii.

Date de iesire

Prima linie a fisierului copaci.out va contine un singur numar natural reprezentand valoarea minima pentru diferenta maxima intre inaltimile copacilor adiacenti.

Restrictii

  • 1 ≤ N ≤ 1.000
  • 1 ≤ K ≤ 109
  • 1 ≤ Hi, Ci ≤ 1.000
  • Un copac poate fi micsorat pana la inaltimea 0

Exemplu

copaci.in

copaci.out

Explicatie

6 9
8 3
9 2
4 3
7 6
4 2
3 4

2

Se micsoreaza inaltimea copacului 2 cu 2 unitati si se mareste inaltimea copacilor 3 si 5 cu o unitate. Noile inaltimi vor fi 8, 7, 5, 7, 5, 3 si diferenta maxima intre inaltimile copacilor adiacenti este 2. Costul total este 2*2 + 1*3 + 1*2 = 9.

Mircea Paşoi
Universitatea Bucuresti, Facultatea de Matematica si Informatica
mircea.pasoi@gmail.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2007: perechi, teanc, index, light, teren, pizza, grupe, cod, ecran, drum, soldati, factura, palma, decript, lbd, aven, cs, h, trenuri, sort, spam, complex, parent, holo, tren2, gray, siruri, arce, pasi, cifre, mgo, firma, joc, cartonase, vikingi, anagrame, balbe, vecini, balaur, tribile, conflicte, criptmat, mesaj, maxim, magic3, desen, plimbare, cutie, patrate, party, vagoane, robot, astre, trains, numere2, friends, tricouri, furtuna, net, baby, scaune, 3d, axa, bile2, vmem, pahare, termen, sablon, zapada, cuvinte, excursie, hd, pajura, pc, sir, cadere, pioni
De acelaşi autor: ab2, plimbare, cuvinte, pioni, reinvent, numere3, perm, criptare, sume, gramezi, nr2, rev, paintball, matricea, emax, turism, puncte1, casute, dep
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, 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, 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 căutare binară: gropi, pod, uscat, checkin, aven, br, furtuna, livada, numar, matrice, sume, bacan, toys, chimie2, trafic, ants, multiplu, ghici, sirag1, tabara, puncte1, centru, harta1, salvare, spion, poze, dist1, patrate5, resturi, lanterna, sea2, vot, standard, cantor, medalii, binperm, mobil, stalpi1, expo, miere, conferinta, subs, pack, obstacole, dag, acoperire, verigi, bradut2, triburi, intervale, mijloc, patru, eliminare, vectori1, calcule, secvp, dreapta, colina, ssk, robotics, cabana
Despre deque: platforma, compus, sirag, leaves, secvreg, cover, drept1, stalpi1, gropi1
surse trimise | ajutor