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

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


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

Veronel doreşte să-şi repare gardul care-i separă curtea de cea a vecinului său. Gardul este susţinut de n stâlpi, amplasaţi coliniar, numerotaţi în ordine de la stânga la dreapta: 1, 2, .. , n. Aceştia se găsesc la distanţele di metri (i=2, 3, ..., n) faţă de primul stâlp. Stâlpii 2, 3, ... n-1 pot fi mutaţi spre stânga sau spre dreapta. Stâlpul 1 şi stâlpul n nu se pot muta. Pentru simplitate, Veronel calculează efortul deplasării unui stâlp ca fiind egal cu distanţa de deplasare. Fie D cea mai mare distanţă dintre doi stâlpi consecutivi, după efectuarea tuturor mutărilor.

Cerinţă

Cunoscând efortul total maxim E pe care Veronel este dispus să-l facă pentru deplasarea stâlpilor să se determine cea mai mică valoare posibilă pentru D, care se poate obţine conform condiţiilor din enunţ, astfel încât să nu se depăşească efortul E. Efortul total este definit ca suma eforturilor pe care Veronel le face pentru deplasarea stâlpilor.

Date de intrare

Pe prima linie a fişierului de intrare stalpi1.in se află două numere naturale n şi E separate printr-un singur spaţiu, cu semnificaţia din enunţ. Pe linia următoare se află n–1 numere naturale d2 d3 ... dn, separate prin câte un singur spaţiu, reprezentând distanţele iniţiale ale stâlpilor 2, 3, ... n faţă de stâlpul 1.

Date de ieşire

Fişierul de ieşire stalpi1.out va conţine o singură linie pe care se va scrie un număr natural D, cu semnificaţia din enunţ.

Restricţii

• Stâlpii pot fi mutaţi doar pe poziţii a căror distanţă faţă de stâlpul 1 este exprimată prin valori naturale.
0 ≤ d2 ≤ d3 ... ≤ dn ≤ 10 000
3 ≤ n ≤ 50
1 ≤ E ≤ 400 000
• Pentru 20% din teste n = 3 şi dn ≤ 100
• Pentru 40% din teste n ≤ 15 şi dn ≤ 200
• Pentru 70% din teste n ≤ 15 şi dn ≤ 1000
• Pentru 100% din teste n ≤ 50 şi dn ≤ 10 000

Exemple

stalpi1.instalpi1.outExplicaţii
4 10 10 30 50 17 Se mută stâlpul 2 cu 7 metri spre dreapta şi stâlpul 3 cu 3 metri spre dreapta.

autor: Prof. Constantin Gălăţan
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2010: diff, kmax, minuni, submatrix1, dreptunghiuri, gaz, xp, petrecere, triunghi2, cmmmc, simetric1, cern, pesti, plaja, tango, arb1, v2d, xor2, cuiburi, telefon, teroristi
De acelaşi autor: ozn, pod, numere, vikingi, furtuna, livada, teatru, iepuras2, kimberley, novel, friends2, stalpi, tabara, sport, randuri, panouri, powerpuff, cartele, joc15, autostrazi, telecab, pseudobil, harta2
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, 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, 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, copaci, 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, 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, copaci, sirag, leaves, secvreg, cover, drept1, gropi1
surse trimise | ajutor