Programozás‎ > ‎Feladatok‎ > ‎

Sütemények

Közeledik Tomi születésnapja, és egy hatalmas bulit szervez, amire rengeteg tortát kell sütnie. Kevés idő áll rendelkezésre, ezért ügyesen kell szerveznie a munkát. Mindegyik sütemény elkészítési ideje ismert, és összesen három sütőben tud Tomi párhuzamosan sütni. Egy sütőben egyszerre mindig csak egy sütemény sülhet.

Feladat

Írjunk programot, ami megadja, hogy legkevesebb mennyi idő szükséges az összes sütemény elkészítéséhez. Szorgalmi: adjunk meg egy olyan sütési tervet, ami minimális ideig tart.

Bemenet

A CAKES.IN minden sora egy-egy tesztesetet tartalmaz. Az első szám a sütemények száma: 1 <= n <= 40, majd a sütési idők következnek: 1 <= ti <= 30. A bemenetet egy 0-t tartalmazó sor zárja le.

Kimenet

Minden tesztesethez a minimális sütési időt tartalmazza. A szorgalmiban a sütési idő alá írjuk ki a három sütőben sütött dolgok idejét.

Példa

Bemenet  Kimenet
5 6 7 8 9 10
0
15
1: 6 9
2: 7 8
3: 10


Tesztadatok

Címkék

A feladat forrása: Stanford Local Programming Contest 2007
Algoritmusok: dinamikus programozás

megoldás