Knygų kopijavimas

Pradinių duomenų failas:

knygos.in  

Rezultatų failas:

knygos.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Prieš atsirandant knygų spausdinimui, knygų kopijavimas buvo labai varginantis ir ilgas darbas. Visas knygos turinys turėjo būti perrašomas ranka. Dažnai šiuo darbu užsiimdavo vienuoliai. O vienintelis būdas pagreitinti darbą buvo samdyti daugiau perrašinėtojų.

Vieną kartą, seniai seniai, viena teatro trupė norėjo atlikti garsiąsias Antikos Tragedijas. Šios pjesės scenarijus buvo padalintas daugelyje knygų, o aktoriai norėjo padaryti daugiau jų kopijų. Taigi jie samdė perrašinėtojus, kad šie galėtų nukopijuoti knygas.

Įsivaizduokite, kad jūs turite m knygų (sunumeruotų 1, 2, …, m), kurių kiekviena gali turėti skirtingą puslapių skaičių (\(p_{1}\), \(p_{2}\), …, \(p_{m}\)), ir norite padaryti kiekvienos knygos kopiją. Jūs turite paskirstyti knygas k perrašinėtojų. Kiekviena knyga gali būti skiriama tik vienam perrašinėtojui, o kiekvienas perrašinėtojas gali gauti tik grupę knygų su iš eilės einančiais numeriais. Kitaip tariant, egzistuoja didėjanti skaičių seka 0 = \(b_{0}\) < \(b_{1}\) < … < \(b_{k}\) = m, tokia, kad i-asis perrašinėtojas gaus perrašinėti knygas su numeriais nuo \(b_{i-1}\)+1 iki \(b_{i}\). Laikas, reikalingas visoms knygoms nukopijuoti, priklauso nuo perrašinėtojo, kuriam skiriama daugiausiai darbo. Todėl mūsų tikslas yra minimizuoti didžiausią bendrą puslapių, tenkančių vienam perrašinėtojui, skaičių. Jūs turite rasti optimalų paskirstymą šia prasme.

Pradiniai duomenys

Pirmoje pradinių duomenų eilutėje įrašyti du sveikieji skaičiai m ir k (1 ≤ k ≤ m ≤ 100 000). Antroje eilutėje pateikti sveikieji skaičiai \(p_{1}\), \(p_{2}\), …, \(p_{m}\), atskirti tarpais (1 ≤ \(p_{i}\) ≤ 10 000).

Rezultatai

Į rezultatų failą jūsų programa turi išvesti skaičius \(p_{1}\), \(p_{2}\), …, \(p_{m}\), padalintus į k grupių taip, kad atskiros grupės puslapių suma būtų kuo mažesnė. Grupes vieną nuo kitos atskirkite pasviro brūkšnio (/) simboliu. Tarp gretimų skaičių bei tarp skaičiaus ir pasviro brūkšnio simbolių turi būti lygiai vienas tarpas. Eilutė turi baigtis eilutės pabaigos simboliu. Daugiau jokių simbolių neturi būti.

Jei yra daugiau negu vienas sprendinys, jūsų programa turi atspausdinti tą, kuriame minimizuojamas pirmajam perrašinėtojui skiriamas darbas, tada antrajam ir t.t. Kiekvienam perrašinėtojui turi būti skiriama bent viena knyga.

Pavyzdžiai

9 3
100 200 300 400 500 600 700 800 900

100 200 300 400 500 / 600 700 / 800 900

5 4
100 100 100 100 100

100 / 100 / 100 / 100 100