Atenţie! Aceasta este ultima versiune a paginii, scrisă la 2018-03-18 08:30:29.
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

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.

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 pe 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.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?