Programozás‎ > ‎Feladatok‎ > ‎

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 vezethetett 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 éis 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 dm3 arany áll rendelkezésre az átalakításhoz, az ábrán látható terv pedig (3⋅1,5+1⋅1+1,2⋅(1+5)+1⋅3+0,8⋅(3+4)+1,2⋅11)⋅10=345 dm3 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, hogy legkevesebb mennyi arany kell az átépítéshez, és kiadja az optimális átalakítás tervét.

Bemenet

A bemenet 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 < 1,5  / SZ egész, M egy tizedes pontosságú /) 

Kimenet

A kimenet 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

Bemenet  Kimenet
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

Címkék

A feladat forrása: Quantum, The Pharaoh’s Golden Staircase, M. Reytman, 1994 Mar/Apr 
Algoritmusok: dinamikus programozás

megoldás