Create Sauron.java

După ce Sauron a pierdut inelul puterii acesta a decis să se retragă pentru
o vreme în ascunzatoarea sa secretă pentru a plănui un nou atac. Fără inelul
puterii acesta trebuie acum să se bazeze doar pe cele 2  N perechi de orci
care au supraviețuit dezastrului. El are notat pe o piatră vulcanică (suficient
de mare) pentru fiecare membru al perechii câte victime a realizat în ultimul
război. În fiecare pereche, primul orc are rangul mai mare, deci el se numește
Stăpân, iar celălalt orc se numește Sclav. Pentru a le ridica moralul slujitorilor
săi, Sauron s-a gândit să își răsplătească supușii, plătind 2 N salarii, câte unul
pentru fiecare pereche. Valoarea unui salariu reprezintă numărul de victime ale
Stăpânului sau ale Sclavului dintr-o echipă. Pentru că Sauron este lacom din
fire el vrea să minimizeze pe cât posibil suma totală plătită, impunându-și însă
câteva reguli:
• Dintre cele 2  N perechi el trebuie să aleagă N Stăpâni și N Sclavi.
• Trebuie să plătească exact N salarii corespunzătoare Stăpânilor aleși și
exact N salarii corespunzătoare Sclavilor aleși
• din fiecare pereche trebuie plătit un singur orc - Stăpânul sau Sclavul
Dintre cei 2  N orci plătiți, Sauron va trebui să formeze N noi perechi astfel:
• se va grupa obligatoriu un Stăpân cu un Sclav
• pentru orice nouă pereche, indicele perechii inițiale din care este ales
• Sclavul trebuie să fie mai mic decât indicele perechii inițiale din care este
ales Stăpânul său. Indicii sunt dați de ordinea în care apar cele 2  N
perechi pe piatra vulcanică.
Cerințe:
Sauron și-a dat seama că nu este un bun strateg atunci când a pierdut inelul
puterii, iar acum își dă seama că nu e nici un bun programator. De aceea,
vă roagă pe voi să îl ajutați să rezolve această problemă. Fiind foarte lacom,
răsplata voastră va fi doar de 40 de puncte dacă reușiți să îi spuneți atât suma
minimă pe care o va plăti în total, cât și dacă îi dați o regrupare corectă a celor
N perechi de orci care se vor forma în final.
Date de intrare:
Pe prima linie a fișierului de intrare se va afla numărul de perechi de orci (2N),
în ordinea care apar pe piatra vulcanică. Pe următoarele 2  N linii se vor afla
câte două numere pe linie, reprezentând numărul de victime ale primului orc
(Stăpânului) și numarul de victime ale celui de-al doilea orc (Sclavul).
2
Proiectarea Algoritmilor 2014 Tema 1
Date de ieșire:
Pe prima linie din fișierul de ieșire veți afișa suma minimă pe care poate Sauron
să o plătească în total, iar pe următoarele N linii se vor afișa câte două valori:
Stăpânul care va rămâne și Sclavul cu care va fi împerecheat. Atenție: atât
Stăpânul, cât și Sclavul sunt identificați prin indicele perechii din care făceau
parte în datele de intrare.
Exemplu:
date.in:
6
3 0
7 1
2 0
5 1
6 0
4 2
date.out
12
3 1
4 2
6 5
Explicație: pt 2*N = 6
• id: stapân sclav
• 1: 3 0
• 2: 7 1
• 3: 2 0
• 4: 5 1
• 5: 6 0
• 6: 4 2
Suma minimă care respectă condițiile din enunț se obține plătind perechea
1 cu 0 galbeni, plătind perechea 2 cu 1 galben, plătind perechea 3 cu 2 galbeni,
plătind perechea 4 cu 5 galben, plătind perechea 5 cu 0 galbeni și plătind
perechea 6 cu 4 galbeni.
Restricții:
• 2  2  N  10000
• se garantează că rezultatul problemei va încăpea pe un tip de date pe 32
de biți cu semn.
3
Proiectarea Algoritmilor 2014 Tema 1
• dacă calculați doar salariul minim, trebuie să existe pentru acesta o grupare
validă (care să respecte și a doua cerință), chiar dacă nu afișați cele
N perechi.
• numărul de victime corespunzătoare Stapânului poate fi mai mic decât
numărul de victime corespunzătoare Sclavului

Limitele de timp pentru problema 1 sunt:
• C/C++ 0.5 secunde
• Java 0.6 secunde