Fişierul intrare/ieşire:stalpi2.in, stalpi2.outSursăONI 2010, clasele 11-12
AutorConstantin GalatanAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Stalpi2

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 stalpi2.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 stalpi2.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

Exemplu

stalpi2.instalpi2.out
4 10
10 30 50
17

Explicaţie

Se mută stâlpul 2 cu 7 metri spre dreapta şi stâlpul 3 cu 3 metri spre dreapta.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content