János gazda földjén N domb van (1 <= N <= 1000), mindegyik magassága 0 és 100 közé eső egész. Télen hó fedi a dombokat, ezért János sítáborokat szervez. Sajnos kiderült, hogy jövőre megadóztatják a sítábort üzemeltetőket. A törvény alapos átolvasása után kiderült, hogy csak akkor számít sítábornak egy telek, ha a legmagasabb és legalacsonyabb domb magasságának különbsége több, mint 17. Adott tehát a terv: az alacsony dombokat meg kell magasítani, a magasakat alacsonyabbá kell tenni úgy, hogy ne legyen több a maximum és a minimum különbsége 17-nél. Egy domb magasságának x egységgel való megváltoztatása x2 pénzbe kerül. Legkevesebb hány pénzből oldható meg, hogy János elkerülje a jövőre bevezetendő sítábor-adót. A dombok magassága csak egész értékkel változtatható meg. Feladat
Írjunk programot, ami megadja, hogy legkevesebb mennyi pénz kell az adó elkerüléséhez.
Bemenet
A bemenet első sorában N értéke van, ezután N sorban egy-egy domb magassága, mindegyik egész.
Kimenet
Az egyetlen sorba a minimális költséget kell írni.
Példa
Bemenet |
Kimenet |
5 20 4 1 24 21 | 18
|
A példa magyarázata: János megtartja a 4, 20, és 21 magas dombokat. az 1 -> 4 és 24 -> 21 változtatások költsége 9+9=18 .
Tesztadatok
Címkék
A feladat forrása: USACO training material, Ski Course Design
Algoritmusok:
megoldás |