Fişierul intrare/ieşire:zzid.in, zzid.outSursăad-hoc
AutorAdăugată destocarulCosmin-Mihai Tutunaru stocarul
Timp execuţie pe test2.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Zzid

Fie un zid perfect dreptunghiular de inaltime H si latime W, format din caramizi de inaltime 1 si latime variabila, lipite intre ele.

Cerinta

Sa se taie acest zid pe verticala astfel incat numarul de caramizi ce trebuie taiate sa fie minim. In cazul in care exista mai multe astfel de locuri unde poate fi taiat zidul, se doreste ca diferenta latimilor celor doua bucati obtinute sa fie cat mai mica.

Date de intrare

Fişierul de intrare zzid.in contine pe prima linie numerele H si W. Pe fiecare din urmatoarele H linii va fi descris un rand al zidului in felul urmator: un numar Ni, reprezentand numarul de caramizi de pe randul i, urmat de Ni numere, reprezentand latimea caramizilor de pe randul i, in ordinea in care apar. Suma latimilor caramizilor de pe fiecare rand este egala cu W. Toate numerele din fisierul de intrare sunt naturale.

Date de ieşire

Fişierul de ieşire zzid.out contine o singura linie cu doua numere naturale separate printr-un spatiu: numarul minim necesar de caramizi ce trebuie taiate astfel incat sa se taie zidul in doua bucati, respectiv diferenta minima dintre cele doua latimi ale zidurilor.

Restricţii

  • 2 ≤ W ≤ 10^9
  • 2 ≤ H ≤ 10^5
  • Sunt maxim 10^6 caramizi
  • Pentru 30% din teste H si W ≤ 1000
  • Pentru alte 20 din teste H ≤ 1000
  • Zidul nu poate fi rotit

Exemplu

zzid.inzzid.out
3 10
1 10
2 5 5
3 2 3 5
1 0

Explicaţie

Zidul se poate taia fix la jumatate, si doar caramida de pe primul rand trebuie taiata.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?