== include(page="template/taskheader" task_id="zzid") ==
Poveste şi cerinţă...
Fie un zid perfect dreptunghiular de inaltime $H$ si latime $W$, format din caramizi de inaltime $1$ si latime variabila, lipite intre ele.
h2. 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.
h2. Date de intrare
Fişierul de intrare $zzid.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $zzid.out$ ...
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.
h2. 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
h2. Exemplu
table(example). |_. zzid.in |_. zzid.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 10
1 10
2 5 5
3 2 3 5
| 1 0
|
h3. Explicaţie
...
Zidul se poate taia fix la jumatate, si doar caramida de pe primul rand trebuie taiata.
== include(page="template/taskfooter" task_id="zzid") ==
== include(page="template/taskfooter" task_id="zzid") ==
