| Fişierul intrare/ieşire: | echipe2.in, echipe2.out | Sursă | Algoritmiada 2009, Runda Finala |
| Autor | Cosmin Gheorghe | Adăugată de |  Gheorghe Cosmin •gcosmin |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Echipe2
Julieta este antrenoare de un sport mai ciudat. In acest sport exista N functii pe care un jucator le poate indeplini. Fiecare jucator e expert la o anumita functie si nu poate ocupa decat acea functie. Julieta are cate 2 jucatori pentru fiecare functie si vrea sa formeze doua echipe cat mai echilibrate. Ea cunoaste pentru fiecare dintre cei 2 * N jucatori valoarea acestora (un numar natural). Se defineste dezechilibrul unei echipe ca fiind diferenta dintre cel mai valoros jucator din echipa si cel mai putin valoros. Julieta mai defineste dezechilibrul total ca fiind maximul dintre dezechilibrul primei echipe si dezechilibrul celei de a doua echipa. Pentru ca sunt foarte multi jucatori pe teren, Julieta va roaga pe voi sa aflati care este dezechilibrul total minim pe care il poate obtine.
Date de intrare
Fişierul de intrare echipe2.in va contine pe prima linie numarul N. Urmatoarele N linii vor contine fiecare cate doua numere naturale reprezentand valorile jucatorilor ce pot ocupa functia respectiva.
Date de ieşire
În fişierul de ieşire echipe2.out veti afisa dezechilibrul total minim ce se poate obtine.
Restricţii si precizari
- 1 ≤ N ≤ 105
- Valorile jucatorilor nu vor depasi 109
Exemplu
| echipe2.in | echipe2.out |
|---|---|
| 5 1 3 5 4 3 4 6 5 4 2 | 4 |
Explicaţie
O solutie posibila este (valorile ingrosate reprezinta o echipa iar cele neingrosate cealalta echipa):
- 1 3
- 5 4
- 3 4
- 6 5
- 4 2
Dezechilibrul echipei ingrosate este 4, iar dezechilibrul celeilalte echipe este 3. Dezechilibrul total este 4. Pot exista mai multe solutii de a forma echipele
