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.

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

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.

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

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

A feladat forrása: ???

Algoritmusok: geometriai algoritmusok, téglalap partíció, dinamikus programozás

megoldás