piloti
Vasile are o companie
de transport aerian. Pentru a se mentine pe piata, el trebuie sa reduca cheltuielile
cât mai mult posibil.
La compania sa exista N piloti
(N par). Pilotii sunt numerotati
de la 1 la N
în ordinea crescatoare a vârstei (pilotul 1
este cel mai tânar, pilotul N
cel mai batrân).
Vasile trebuie sa constituie N/2
echipaje. Un echipaj este format din 2 piloti (capitanul si asistentul sau).
Capitanul trebuie sa fie mai în vârsta decât asistentul sau.
În contractul fiecarui pilot sunt prevazute doua salarii: unul pentru
cazul în care el este capitan al echipajului, celalalt pentru cazul în
care el este asistent. Evident, pentru orice pilot salariul sau de capitan este
mai mare decât salariul sau de asistent.
Salariile pot sa difere de la un pilot la altul. Chiar se poate întâmpla
ca salariul capitanului sa fie mai mic decât salariul asistentului sau.
Pentru a cheltui cât mai putini bani pe salariile pilotilor, Vasile trebuie
sa determine o distribuire optimala a pilotilor pe echipaje.
Cerinta
Scrieti un program care sa determine suma minima necesara pentru a plati salariile pilotilor.
Date de intrare
Fisierul de intrare piloti.in
contine pe prima linie un numar natural N
reprezentând numarul de piloti.
Pe urmatoarele N linii sunt informatii
despre salariile pilotilor. Pe linia i+1
se afla doua numere naturale c a
separate printr-un spatiu (c
reprezinta salariul pilotului i
pe post de capitan, iar a reprezinta
salariul pilotului i pe post
de asistent).
Date de iesire
Fisierul de iesire piloti.out
va contine o singura linie pe care va fi afisata suma minima necesara pentru
a plati salariile celor N piloti.
Restrictii
2 <= N <= 10000;
N par;
Pentru orice pilot, 1 <= a < c
<= 100 000
Exemple
| piloti.in | piloti.out | piloti.in | piloti.out |
| 6 10000 7000 9000 3000 6000 4000 5000 1000 9000 3000 8000 6000 |
32000 | 6 5000 3000 4000 1000 9000 7000 11000 5000 7000 3000 8000 6000 |
33000 |
Timp maxim de executie/test: 0.1 secunda
Limite
de memorie: total memorie disponibila 15 Mb, din care pentru stiva maxim:
1 Mb prof. Emanuela
Cerchez Liceul de
Informatica "Grigore Moisil" Iasi Contact:ema
at mail.dntis.ro