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 |