Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | greutati.in, greutati.out | Sursă | Algoritmiada 2018 Runda PreONI |
| Autor | Mihai Calancea | Adăugată de |  Radu Muntean •heracle |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/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 ^ 6
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 : MAXIM
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 ≤ 1.000.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.in | greutati.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
