Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-11-27 19:29:43.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:scandura.in, scandura.outSursăAlgoritmiada 2009, Runda 1
AutorBogdan-Cristian TataroiuAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.25 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Scandura

G. Tamplaru' I vrea sa-si faca un birou nou. El cunoaste dimensiunile finale ale tuturor scandurilor de care are nevoie pentru a construi biroul si a cumparat o scandura de lungime L egala cu suma lungimilor tuturor scandurilor necesare. El are o masina speciala in care poate introduce o scandura de orice lungime si aceasta o taie in maxim M bucati diferite. Efortul depus de G. Tamplaru' I pentru a taia o scandura de lungime X este egal cu X.

Date de intrare

Fişierul de intrare scandura.in va contine pe prima linie doua numere naturle N si M. Pe a doua linie se vor afla, separate prin spatii, N numere naturale in ordine crescatoare.

Date de ieşire

În fişierul de ieşire scandura.out se va afisa pe prima linie efortul minim necesar.

Restricţii

  • 1 ≤ N ≤ 106
  • 2 ≤ M ≤ N
  • 1 ≤ lungimile scandurilor ≤ 109

Exemplu

scandura.inscandura.out
4 2
1 2 3 4
19

Explicaţie

Scandura initiala are lungime 10. G. Tamplaru' I efectueaza o taiere cu costul 10 si obtine 2 scanduri de lungime 4 si 6. Scandura de lungime 6 o taie apoi in 2 scanduri de lungme 3. In final, una din cele 2 scanduri de lungime 3 este taiata intr-o scandura de lungime 1 si una de lungime 2.

Efortul total este egal cu 10 + 6 + 3 = 19.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?