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
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 (FRi) ori. Numerele de tipul i sunt egale cu 2PWi. 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 (acest numar e prim).
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 PWi si FRi reprezentand o putere si o frecventa corespunzatoare acelei puteri.
Date de ieşire
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
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ P ≤ 1.000.000.000
- 0 ≤ PWi < P
- 1 ≤ FRi ≤ 1.000.000.000
- nu vor exista perechi i si j in input astfel incat PWi = PWj
- 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
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
