Diferente pentru problema/greutati intre reviziile #12 si #28
Nu exista diferente intre titluri.
Diferente intre continut:
== 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 subtask 1 10pct SUMA_FRECV <= 30 subtask 2 10pct POW_MAX <= 30 subtask 3 20pct POW_MAX <= 10^6 && SUMA_FRECV <= 10^6 #subtask 4 20pct POW_MAX <= 10^6 subtask 5 (grupat) 40pct MAXIME
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 intregiTsi P, undeTreprezinta numarul de puteri de 2 pentru care frecventa este diferita de 0si P reprezinta puterea maxima la care poate aparea 2. Pe urmatoareleTlinii se vor afla cate 2 numere intregipw[i]sif[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
|5 |
h3. Explicaţie sirul frecventelor este 0 0 4 3 1 2 4 3 0 0, respectiv 0 0 4 3 1 2 4 3 0 3
== include(page="template/taskfooter" task_id="greutati") ==