Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2018-03-17 21:38:24.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:greutati.in, greutati.outSursăAlgoritmiada 2018 Runda PreONI
AutorMihai CalanceaAdăugată deheracleRadu Muntean heracle
Timp execuţie pe test0.5 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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

Date de ieşire

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

Restricţii

  • 1 ≤ T ≤ 100.000
  • 1 ≤ P ≤ 1.000.000.000
  • 0 ≤ pw[i] < P
  • 1 ≤ f[i] ≤ 1.000.000.000
  • nu vor exista perechi i si j in input astfel incat pw[i] = pw[j]

Exemplu

greutati.ingreutati.out
6 10
4 4
3 3
5 2
8 4
6 1
7 3
8
7 10
4 4
3 3
5 2
8 4
6 1
7 3
0 3
5

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?