- Time limit: 2.00 s
- Memory limit: 512 MB
Uolevin aita muodostuu laudasta, joista jokaisella on tietty korkeus. Uolevi haluaa maalauttaa aidan niin, että mitkään kaksi vierekkäistä lautaa eivät ole samanväriset.
Maalausta varten Uolevi palkkaa joukon maalareita. Jokainen maalari maalaa yhden tai useamman laudan omalla värillään. Kunkin maalarin palkkio on suurin hänen maalaamansa laudan korkeus.
Tehtäväsi on etsiä tapa maalata aita niin, että maalarien yhteispalkkio on mahdollisimman pieni. Saat päättää itse, montako maalaria palkkaat.
Syöte
Syötteen ensimmäisellä rivillä on luku : lautojen määrä.
Seuraavalla rivillä on kokonaislukua : lautojen korkeudet.
Tuloste
Tulosta ensin kokonaisluvut ja : maalauksen pienin mahdollinen kustannus ja montako maalaria palkataan ().
Tulosta sitten rivi, joka kertoo, kuka maalari maalaa minkäkin laudan. Rivillä tulee olla kokonaislukua väliltä .
Voit tulostaa minkä tahansa kelvollisen ratkaisun, jossa yhteispalkkio on pienin mahdollinen.
Esimerkki
Syöte:
6 5 8 3 2 7 2
Tuloste:
15 3 1 2 1 3 2 3
Selitys: Maalarin palkkio on , maalarin palkkio on ja maalarin palkkio on . Niinpä yhteispalkkio on , joka on pienin mahdollinen.
Maalattu aita näyttää tältä: