Taro finom kiwi szörpöt készített, majd N üvegbe öntötte szét (az üvegek 0-tól (N-1)-ig számozottak. Minden üvegbe C liter szörp fér, és kezdetben bottles[i] litert töltött az i. üvegbe. Taro el akarja adni a szörpöt, de előtte tetszőlegesen sokszor végrehajthatja az alábbi műveletet: két különböző üveget választva (A és B) A-ból B-be addig töltheti a szörpöt, amíg
(Amelyik előbb bekövetkezik, azt kell végrehajtani.) Ha egy üveg x lliter kiwi szörpöt tartalmaz (0 <= x <= C), akkor Taro prices[x] dollárért tudja eladni ezt az üveget. FeladatÍrjunk programot, ami kiszámolja, hogy Taro legfeljebb hány dollárt tud keresni.
BemenetA bemenet első sorában C található (1 <= C < 50). Ezután az üvegekbe kezdetben betöltött szörp mennyisége jön ( bottles[] ) egy sorban, szóközökkel elválasztva. Legfeljebb 15 üveg van.Végül a harmadik sorban a
prizes[] tömb elemei vannak megadva, pontosan C+1 egész, 0-tól C-ig indexelve értendő. Minden ár 0 és 1000000 közé esik, a határokat is megengedve.KimenetA maximálisan kereshető pénzérték.
Példa
CímkékA feladat forrása: Top Coder, http://community.topcoder.com/stat?c=problem_statement&pm=11019 Algoritmusok: dinamikus programozás
|
Programozás > Feladatok >