Code Submission Evaluation System Login

IOI-leiri 2016

Automatka


Task | Statistics


CSES - AutomatkaCSES - Automatka

Time limit:2.50 s Memory limit:128 MB

Uolevi aikoo ajaa autolla Syrjälästä Perälään. Matka on $n$ kilometrin pituinen ja matkalla on kilometrin välein huoltoasema. Uolevi voi pysähtyä tankkaamaan valitsemillaan huoltoasemilla. Lisäksi Uolevin tapana on juoda kahvi aina kun hän pysähtyy huoltoasemalle.

Asemalla $i$ bensa maksaa $a_i$ euroa/litra ja kahvi maksaa $b_i$ euroa. Tehtävänä on valita huoltoasemat niin, että matkan kokonaishinta on mahdollisimman pieni.

Huoltoasemat on numeroitu $0 \ldots n-1$. Asema $i$ on $i$ kilometrin päässä Syrjälästä. Uolevin auto kuluttaa bensaa litran kilometrillä. Aluksi Uolevin tankki on tyhjä, eli hänen on pakko pysähtyä huoltoasemalla $0$.

Syöte

Ensimmäisellä rivillä on luku $n$, matkan pituus. Sitten tulee $n$ riviä, joilla on luvut $a_i$ ja $b_i$.

Tuloste

Tulosta ensimmäiselle riville kaksi lukua: optimaalinen matkan hinta ja kuinka monella huoltoasemalla pysähdytään. Tulosta toiselle riville järjestyksessä ensimmäisestä viimeiseen ne huoltoasemat joilla pysähdytään ja kolmannelle riville paljonko bensaa tankataan niillä huoltoasemilla joille pysähdytään. Jos optimaalisia vastauksia on useita, tulosta mikä tahansa niistä.

Rajat
Esimerkki

Syöte:
5
15 3
10 10
10 4
2 10
3 1


Tuloste:
61 3
0 2 3
2 1 2