NézetNyomtat

Darabolás (Megoldás)
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat

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\le SZ, M, DB\le 20$)

Kimenet

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

Példa

DARABOL.BEDARABOL.KI
4 4 4 4 4 3 0 0 0 4 6

Tesztadatok