| Fişierul intrare/ieşire: | zzid.in, zzid.out | Sursă | ad-hoc |
| Autor | Adăugată de |  Cosmin-Mihai Tutunaru •stocarul | |
| Timp execuţie pe test | 1.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | zzid.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.
