# PBinfo #2974 – Zzid – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
Fie un zid perfect dreptunghiular de înălțime H și lățime W, format din cărămizi de înălțime 1 și lățime variabilă, lipite între ele.

Să se taie acest zid pe verticală astfel încât numărul de cărămizi ce trebuie tăiate să fie minim. În cazul în care există mai multe astfel de locuri unde poate fi tăiat zidul, se dorește ca diferența lățimilor celor două bucăți obținute să fie cât mai mică.

Date de intrare
Fișierul de intrare zzid.in conține pe prima linie numerele H și W. Pe fiecare din următoarele H linii va fi descris un rând al zidului în felul următor: un număr Ni, reprezentând numărul de cărămizi de pe rândul i, urmat de Ni numere, reprezentând lățimea cărămizilor de pe rândul i, în ordinea în care apar. Suma lățimilor cărămizilor de pe fiecare rând este egală cu W. Toate numerele din fișierul de intrare sunt naturale.

Date de ieșire
Fișierul de ieșire zzid.out conține o singură linie cu două numere naturale separate printr-un spațiu: numărul minim necesar de cărămizi ce trebuie tăiate astfel încât să se taie zidul în două bucăți, respectiv diferența minimă dintre cele două lățimi ale zidurilor.

Restricții și precizări

2 ≤ W ≤ 1.000.000.000
2 ≤ H ≤ 100.000
Sunt maximum 1.000.000 cărămizi
Pentru 30% din teste H si W sunt mai mici decât 1000
Pentru alte 20% din teste H ≤ 1000
Zidul nu poate fi rotit

Exemplu:
zzid.in

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

1 0
Explicație
Zidul se poate tăia fix la jumătate, și doar cărămida de pe primul rând trebuie tăiată.

## Cod sursă C++

```cpp
#include<bits/stdc++.h>
using namespace std;
ifstream in("zzid.in");
ofstream out("zzid.out");
map<int,int>v;
int main()
{
   	int s=0,a,b,n,m,maxim=0,taietura;
    in>>n>>m;
    for(int i=1;i<=n;i++)
    {
        in>>a;
        for(int j=1;j<=a;j++)
        {
            in>>b;
            s+=b;
            if (s==m)
                continue;
            v[s]++;
            if(v[s]>maxim)
            {
                maxim=v[s];
                taietura=s;
            }
            if(v[s]==maxim && abs(m-taietura-taietura)>abs(m-s-s)){
                taietura=s;
            }
        }
        s=0;
    }
     out<<n-maxim<<" "<<abs(taietura-m+taietura);
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2974)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2974/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2974/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)