NézetNyomtat

A fáraó lépcsője (Megoldás)
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat

A fáraó lépcsője

A fáraó palotája messze földön híres volt pompájáról: gyöngyökből készült függönyök, borostyánkővel díszített falak, arany tányérok - nehéz lenne minden kincset felsorolni. Mégis, akiket beengedtek a trónterembe, leginkább a trónhoz vezető arany lépcsőt vésték emlékezetükbe.
A képen a lépcső keresztmetszete látható, a méreteket deciméterben tüntettük fel. A lépcső szélessége 10 dm. Az archeológusoknak nem tartott sokáig megérteni, miért indulnak ilyen alacsonyan a lépcsőfokok. Az öreg fáraó nem akarta, hogy alattvalói lássák, mennyire nehezére esik felmászni a trónig, hiszen esetleg csökkent volna bennük a fáraó iránt érzett tisztelet, ez pedig ki tudja, hova veztehetett volna. Ezért tervezték úgy az építészek a lépcsőt, hogy egyetlen lépcsőfok sem lehet magasabb, mint 1,5 dm.
Az idő azonban nem áll meg, az idős uralkodó meghalt, és fia örökölte a trónt.
A fiú már eddig és sokat hallgatta a szolgák gúnyos sugdolózását, apja hiúsága miatt, elhatározta hát, hogy átépítteti a lépcsőt, úgy, hogy összesen 4 lépcsőfok vezessen a trónig.
Az ábrán a szaggatott vonalak mutatnak egy lehetséges átalakítást.
Természetesen az új lépcsőfokokat is aranyból kellett építeni, ami nem esett jól a fáraó kincstárosának. Kiderült, hogy összesen 200 ${dm}^3$ arany áll rendelkezésre az átalakításhoz, az ábrán látható terv pedig $\left( 3\cdot 1.5+1\cdot 1+1.2\cdot (1+5)+1\cdot 3+0.8\cdot (3+4)+1.2\cdot 11\right) \cdot 10 = 345$ ${dm}^3$ aranyat igényel.
A kor szokásainak megfelelően, a fáraó kivégezteti kincstárnokát és építészeit, ha nem tudják megoldani a feladatot a rendelkezésre álló arany felhasználásával.

Feladat

Írjunk programot, ami megadja, legkevesebb mennyi arany kell az átépítéshez, és kiadja az optimális átalakítás tervét.

Bemenet

A FARAO.BE állomány első sorában a lépcsőfokok L száma, és az átépítés utáni A száma olvasható. (0 < A < L < 100) A következő L sorban az eredeti lépcsőfokok SZ szélessége és M magassága szerepel, szóközzel elválasztva. (Az utolsó lépcsőfok már a trón szintje, arra nem építünk, ezért az ábrán nem szerepel a szélessége.) (0<SZ<10, 0<M<5, SZ egész, M egy tizedes pontosságú)

Kimenet

Az FARAO.KI első sorába a minimálisan szükséges arany mennyiségét kell írni köbdeciméterben, a következő A sorba pedig az új lépcsőfokokat. Az új lépcsőfokokat a régi számozás szerint adjuk meg: a régi számozás szerinti első és utolsó lépcsőfok, amiből egy új lépcsőfok keletkezett.

Példa

FARAO.BEFARAO.KI
9 4 3 1.0 4 1.5 1 0.7 5 1.0 3 1.2 4 1.0 4 0.8 3 1.2 3 1.0 171 1 2 3 4 5 7 8 9

Tesztadatok