Programozás‎ > ‎Feladatok‎ > ‎

Darabolás

Van egy téglalap alakú lemezünk, amit úgy kell n darabra vágnunk, hogy a legnagyobb területű rész területe minimális legyen. Minden vágás az eredeti téglalap valamelyik oldalával párhuzamosan haladó egyenes, és minden vágás egy meglévő darabot vág két részre.

Feladat

Írjunk programot, ami kiszámítja a legnagyobb darab minimális területét!

Bemenet

A DARABOL.BE állomány minden sora egy tesztesetet tartalmaz. A tesztesetek három számból állnak, az eredeti téglalap szélességéből, magasságából és a kívánt darabszámból. (1 <= SZ,M,DB <= 20) A bemenet végét három nulla jelzi.

Kimenet

A DARABOL.KI minden tesztesethez a legnagyobb darab minimális területét tartalmazza.

Példa

Bemenet  Kimenet
4 4 4
4 4 3
0 0 0
4
6


Tesztadatok

Címkék

A feladat forrása: ???
Algoritmusok: geometriai algoritmusok, téglalap partíció, dinamikus programozás

megoldás