Nu aveti permisiuni pentru a descarca fisierul grader_test1.ok
Inverseaza reviziile

Diferente pentru problema/greutati intre reviziile #28 si #10

Diferente intre #9 si #10

Diferente intre titluri:

Greutati

greutati

Diferente intre continut:

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

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*$.

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

h2. Date de intrare

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.

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.

h2. Date de ieşire

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$*.

În fişierul de ieşire $greutati.out$ ...

h2. Restricţii

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

* $1 &le; T &le; 1.000.000$

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

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

* $0 &le; pw[i] &lt; P$
* $1 &le; f[i] &le; 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") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.