Inverseaza reviziile

Diferente pentru problema/greutati intre reviziile #17 si #18

Diferente intre #18 si #19
Diferente intre #16 si #17

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="greutati") ==

Poveste şi cerinţă...

Se dau $N$ tipuri de numere. Pentru fiercare tip $i$ numerotat 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 doua sa fie cat mai apropiate (diferenta in modul sa fie minima). Aflati aceasta diferenta minima, *$modulo 1.000.000.007*$ (acest numar e prim).

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.000.007* (e prim).
N <= 10 ^ 5
FR[ i ] <= 10 ^ 9
 
#subtask 1  15 puncte: pow_max <= 20, SUMA_FRECV <= 20
#subtask 2  25 puncte: pow_max <= 50, SUMA_FRECV <= 2000
#subtask 3 	35 puncte: pow_max <= 2000, SUMA_FRECV <= 2000
#subtask 4 50 puncte: pow_max <= 100.000, SUMA_FRECV <= 100.000
#subtask 5 70 puncte: pow_max <= 100.000 si SUMA_FRECV <= 1e9
#subtask 6 100 puncte :  T <= 100.000 pow_max <= 1e9 SUMA_FRECV <= 1e9

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 pen care o puteti obtine *$modulo 1.000.000.007$*

h2. Restricţii

* $1 &le; T &le; 100.000$

* $1 &le; N &le; 100.000$

* $1 &le; P &le; 1.000.000.000$

* $0 &le; pw[i] &lt; P$
* $1 &le; f[i] &le; 1.000.000.000$
* nu vor exista perechi i si j in input astfel incat pw[i] = pw[j]

* $0 &le; PW{~i~} &lt; P$
* $1 &le; FR{~i~} &le; 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

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.