Könyvmásolás

A könyvnyomtatás feltalálása előtt nagyon nehéz volt lemásolni egy könyvet. A teljes tartalmat kézzel kellett újraírniuk az írnokoknak. Az írnoknak adtak egy könyvet, és csak hónapokkal később fejezte be a másolást. Az egyik leghíresebb írnok a 15. században élt, úgy hívták: Xaverius Endricus Remius Ontius Xendrianus (Xerox). Akárhogyan is, a munka meglehetősen bosszantó és unalmas volt. Az egyetlen módja a felgyorsításának további írnokok felbérlése volt.

Egyszer régen volt egy színházi társulat, amely híres ókori tragédiákat akart játszani. A színdarabok szövegkönyvei sok-sok könyvben voltak elosztva, a színészeknek pedig természetesen több példányra volt belőlük szüksége. Felbéreltek hát néhány írnokot, hogy másolják le a könyveket. Tegyük fel, hogy van m könyvünk (1-től m-ig sorszámozva), különböző oldalszámokkal (p₁, p₂, …, p_m), és szeretnénk mindegyikből készíttetni egy másolatot. A feladatod, hogy feloszd ezeket a könyveket k írnok között (k ≤ m). Minden könyvet csak egy írnokhoz rendelhetünk, és minden írnoknak a könyvek egy folytonos sorozatát kell megkapnia. Ez azt jelenti, hogy létezik a 0 = b₀ < b₁ < b₂ < … < b_k – 1 < b_k = m számok egy növekvő sorozata úgy, hogy az i-edik írnok a b_i – 1 + 1 és b_i közé eső sorszámú könyvek sorozatát kapja meg. Az összes könyv lemásolásához szükséges időt az az írnok határozza meg, akinek a legtöbb munkát adtuk. A célunk tehát az, hogy minimalizáljuk az egy írnokhoz rendelt oldalak számának a maximumát. A feladatod, hogy megtaláld az optimális felosztást.

A bemenet specifikációja

A bemenet N tesztesetet tartalmaz. A bemenet első sorában csak az N pozitív egész szám szerepel. Ezt követik a tesztesetek. Minden teszteset pontosan két sorból áll. Az első sor két egész számot tartalmaz, m-et és k-t (1 ≤ k ≤ m ≤ 500). A második sorban a p₁, p₂, …, p_m egész számok szerepelnek egy-egy szóközzel elválasztva. A fenti értékek mind pozitívak és kisebbek 10 000 000-nál.

A kimenet specifikációja

Minden tesztesetre pontosan egy sort kell a kimenetre írni, amelynek a bemeneten megadott p₁, p₂, …, p_m számsorozatot kell tartalmaznia pontosan k részre felosztva úgy, hogy az egy részhez tartozó maximális összeg a lehető legkisebb legyen. Használd a perjelet („/”) az egyes részek elválasztásához! Bármely két egymást követő szám között, valamint egy szám és a perjel között is pontosan egy szóköznek kell állnia.

Ha egynél több megoldás létezik, akkor azt kell a kimenetre írni, amelyikben az első írnokhoz rendelt munka minimális. Ha ilyenből is több van, akkor a második írnokhoz rendelt munkát kell minimalizálni, és így tovább. Fontos azonban, hogy minden írnokhoz legalább egy könyvet hozzá kell rendelni.

Példa bemenet

1. 2
2. 9 3
3. 100 200 300 400 500 600 700 800 900
4. 5 4
5. 100 100 100 100 100

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 100 200 300 400 500 / 600 700 / 800 900
2. 100 / 100 / 100 / 100 100

letöltés szöveges állományként