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.009 (e prim).
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
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
Exemplu
| greutati.in | greutati.out |
|---|---|
| 6 10 4 4 3 3 5 2 8 4 6 1 7 3 | 8 |
Explicaţie
sirul frecventelor este 0 0 4 3 1 2 4 3 0 0
