Fişierul intrare/ieşire:echipe2.in, echipe2.outSursăAlgoritmiada 2009, Runda Finala
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inechipe2.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content