| Fişierul intrare/ieşire: | bilute.in, bilute.out | Sursă | Stelele Informaticii 2007, clasele 9-10 |
| Autor | Silviu-Ionut Ganceanu | Adăugată de |  Andrei Grigorean •wefgef |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | bilute.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
