Programozó versenyek

DEIK Regionális Programozó Csapatverseny, egyetemi/főiskolai kategória, 2015. november 29.

2015. november 29. 10:40 – 2015. november 29. 15:40

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 (p1p2, …, pm), é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 = b0 < b1 < b2 < … < bk – 1 < bk = m számok egy növekvő sorozata úgy, hogy az i-edik írnok a bi – 1 + 1 és bi 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 p1p2, …, pm 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 p1p2, …, pm 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
Debreceni Egyetem, Informatikai Kar, v. 2019.03.01.