Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-09-12 00:32:43.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:mostenire.in, mostenire.outSursăAlgoritmiada 2015 Runda Finala
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu •eudanip
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Mostenire

Bunicul si Bunica au intampinat o problema fara precedent: problema mostenirii. Cei 2 au K mere foarte delicioase care trebuie distribuite copiilor si nepotilor lor. Dupa multe zile de chin, Bunicul a realizat in sfasit faptul ca el are N copii (nu mai stia exact) si fiecare copil i are Vi copii. Dupa o cearta puternica cu Bunica, cele 2 personaje au hotarat sa imparta cele K mere la cei N copii, urmand ca la randul lor copiii sa imparta merele primite copiilor lor (nepotii bunicului). Deoarece Bunicul si Bunica sunt batrani, ei va roaga pe voi sa aranjati impartirea merelor astfel incat diferenta maxima de mere pe care le primesc oricare 2 copii si oricare 2 nepoti sa fie cat mai mica. Mai exact, max( CopilMax - CopilMin, NepotMax - NepotMin) sa fie minim. CopilMax si CopilMin reprezinta numarul maxim respectiv minim de mere obtinute de un copil. NepotMax si NepotMin reprezinta numarul maxim respectiv minim de mere obtinute de un nepot.

Date de intrare

Fişierul de intrare mostenire.in va contine pe prima linie 2 numere naturale N si K. Pe urmatoarea linie vor fi N numere naturale: elementul i reprezentand valoarea Vi. Elementele de pe linia 2 sunt date in ordine crescatoare.

Date de ieşire

Fişierul de ieşire mostenire.out va contine pe prima linie un numar natural reprezentand diferenta minima ceruta (acel max( CopilMax - CopilMin, NepotMax - NepotMin)). Pe urmatoarea linie vor fi N numere naturale, elementul i reprezentand numarul de mere pe care i le atribuiti copilului i. Orice solutie corecta va fi punctata.

Restricţii

  • 1 ≤ N ≤ 1.000.000
  • 1 ≤ K ≤ 1018
  • Suma V-urilor este ≤ 2.000.000.000

Exemplu

mostenire.inmostenire.out
2 100
1 2
15
43 57
4 32
1 1 1 2
3
7 7 8 10
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?