== include(page="template/taskheader" task_id="greutati") ==
Poveste şi cerinţă...
Se dau N tipuri de numere, din fiercare tip i de la 0 la N - 1 se stie ca sunt (FR[ i ]). Numerele de tipul i sunt egale cu 2 ^ i. Sa se partitioneze numerele in 2 multiseturi astfel incat sumele celor 2 sa fie cat mai apropiate. Aflati aceasta diferenta (in modul) minima modulo *1.000.004.249* (e prim) (dar testele sunt facute cu 1.000.000.009).
N <= 10 ^ 6
FR[ i ] <= 10 ^ 9
primele 10p: N, SumaFR <= 30
urmatoarele 10p: N <= 30
inca 40p: SumaFR <= 10 ^ 6
ultimele 40p: fara alte restrictii
Se dau $N$ tipuri de numere. Consideram un vector de elemente cu proprietatea ca pentru fiercare tip $i$ numerotat de la $0$ la $N - 1$ acesta apare de (FR{~i~}) ori. Numerele de tipul $i$ sunt egale cu $2^PW{~i~}^$. Sa se partitioneze elementele vectorului in $2$ multiseturi astfel incat sumele celor doua sa fie cat mai apropiate (diferenta in modul sa fie minima). Aflati aceasta diferenta minima *$modulo 1.000.000.007*$.
h2. Date de intrare
Fişierul de intrare $greutati.in$ se vor afla pe prima linie 2 numere intregi T si P, unde T reprezinta numarul de puteri de 2 pentru care frecventa este diferita de 0 si P reprezinta puterea maxima la care poate aparea 2. Pe urmatoarele T linii se vor afla cate 2 numere intregi pw[i] si f[i] reprezentand o putere si o frecventa corespunzatoare acelei puteri.
Fişierul de intrare $greutati.in$ se vor afla pe prima linie $2$ numere intregi $N$ si $P$, unde $N$ reprezinta numarul de puteri de $2$ pentru care frecventa este diferita de $0$, iar $P$ reprezinta puterea maxima la care poate aparea $2$. Pe urmatoarele $N$ linii se vor afla cate $2$ numere intregi $PW{~i~}$ si $FR{~i~}$ reprezentand o putere si o frecventa corespunzatoare acelei puteri.
h2. Date de ieşire
În fişierul de ieşire $greutati.out$ ...
Fişierul de ieşire $greutati.out$ va contine un singur numar natural reprezentand diferenta minima pe care o puteti obtine *$modulo 1.000.000.007$*.
h2. Restricţii
* $1 ≤ T ≤ 1.000.000$
* $1 ≤ N ≤ 100.000$
* $1 ≤ P ≤ 1.000.000.000$
* $0 ≤ pw[i] < P$
* $1 ≤ f[i] ≤ 1.000.000.000$
* $0 ≤ PW{~i~} ≤ P$
* $1 ≤ FR{~i~} ≤ 1.000.000.000$
* nu vor exista perechi $i$ si $j$ in input astfel incat $PW{~i~} = PW{~j~}$
* Pentru $15$ puncte: $P <= 20$, suma frecventelor $<= 20$
* Pentru $25$ de puncte: $P <= 50$, suma frecventelor $<= 2000$
* Pentru $35$ de puncte: $P <= 2000$, suma frecventelor $<= 2000$
* Pentru $50$ de puncte: $P <= 100.000$, suma frecventelor $<= 100.000$
* Pentru $70$ de puncte: $P <= 100.000$ si suma frecventelor $<= 1.000.000.000$
h2. Exemplu
table(example). |_. greutati.in |_. greutati.out |
| 6 10
|6 10
4 4
3 3
5 2
