Fişierul intrare/ieşire:bilute.in, bilute.outSursăStelele Informaticii 2007, clasele 9-10
AutorSilviu-Ionut GanceanuAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bilute

Fiind in apropierea Craciunului, Algorel si-a scos din cutiile din debara bilutele rosii de pus in pom. Datorita faptului ca bilutele au stat un an nefolosite si unele s-au decolorat, exista mai multe nuante de rosu printre ele. Mai precis, sunt N nuante de rosu pe care Algorel le-a numerotat de la 1 la N. Fiind constiincios el a numarat si cate bilute are din fiecare nuanta -- Ci pentru nuanta i.

Algorel vrea sa impodobeasca pomul cu bilute de aceeasi nuanta (nu conteaza care). Normal, pentru asta trebuie sa revopseasca unele bilute. Craciunul fiind aproape ar vrea sa termine cat mai rapid, sa nu-l prinda Mosul nepregatit.

Pentru a vopsi o biluta de nuanta i Algorel trebuie sa o lustruiasca timp de Li minute a se prinde vopseaua de ea. De asemenea, poate vopsi o biluta din nuanta i in nuanta j in |i - j| minute.

Ajuta-ti-l pe Algorel sa calculeze nuanta in care trebuie sa vopseasca bilutele astfel incat timpul de vopsire sa fie minim.

Date de intrare

Fisierul de intrare bilute.in contine pe prima linie un numar intreg N. Urmatoarele N linii contin cate doua numere Ci si Li, reprezentand numarul de bilute de nuanta i precum si timpul de lustruire inainte de vopsire pentru o biluta de nuanta i.

Date de iesire

In fisierul de iesire bilute.out se vor afisa doua numere intregi separate printr-un spatiu reprezentand numarul nuantei in care trebuie vopsite bilutele precum si timpul minim de vopsire exprimat in minute. Daca exista mai multe solutii alegeti nuanta cu cel mai mic indice posibil.

Restrictii

  • 1 ≤ N ≤ 30000
  • 0 ≤ Ci, Li ≤ 100
  • Pentru 50% din teste 1 ≤ N ≤ 1000

Exemplu

bilute.inbilute.out
4
1 3
2 2
3 1
1 3
2 15

Explicatie

Desi si pentru nuanta 3 se obtine acelasi timp de vopsire (15 minute) Algorel alege nuanta numarul 2 pentru ca are un indice mai mic.

Timpul pentru nuanta 2 este calculat astfel:

  • pentru a vopsi biluta de nuanta 1 este nevoie de 1 * 3 + 1 * |1 - 2| = 4 minute
  • cele trei bilute de nuanta 3 sunt vopsite in 3 * 1 + 3 * |3 - 2| = 6 minute
  • biluta de nuanta 4 este vopsita in 1 * 3 + 1 * |4 - 2| = 5 minute
  • in total este nevoie 4 + 6 + 5 = 15 minute pentru a vopsi toate bilutele in nuanta 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content