NézetNyomtat

Sütemények (Megoldás)
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat

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\le n \le 40$, majd a sütési idők következnek: $1\le t_i \le 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

CAKES.INCAKES.OUT
5 6 7 8 9 10 0 15 1: 6 9 2: 7 8 3: 10

Tesztadatok