Editing 2974 - Z Zid

==Cerința==
Fie un zid perfect dreptunghiular de înălțime <code>H</code> și lățime <code>W</code>, format din cărămizi de înălțime <code>1</code> ș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 <code>zzid.in</code> conține pe prima linie numerele <code>H</code> și <code>W</code>. Pe fiecare din următoarele <code>H</code> linii va fi descris un rând al zidului în felul următor: un număr <code>Ni</code>, reprezentând numărul de cărămizi de pe rândul <code>i</code>, urmat de <code>Ni</code> numere, reprezentând lățimea cărămizilor de pe rândul <code>i</code>, în ordinea în care apar. Suma lățimilor cărămizilor de pe fiecare rând este egală cu <code>W</code>. Toate numerele din fișierul de intrare sunt naturale.
==Date de ieșire==
Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

Pe următorul rând se vor afișa 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.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

==Restricții și precizări==

* <code>2 ≤ W ≤ 1.000.000.000</code>
* <code>2 ≤ H ≤ 100.000</code>

* Sunt maximum <code>1.000.000</code> cărămizi
* Pentru <code>30%</code> din teste <code>H</code> si <code>W</code> sunt mai mici decât <code>1000</code>
* Pentru alte <code>20%</code> din teste <code>H ≤ 1000</code>
* Zidul nu poate fi rotit

==Exemplu 1==
;Intrare
:3 10
:1 10
:2 5 5
:3 2 3 5
;Ieșire
:Datele de intrare corespund restricțiilor impuse.
: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ă.

==Exemplu 2==
;Intrare
:3 10
:1 10
:2 5 0
:3 2 5 5
;Ieșire
:Datele de intrare nu corespund restricțiilor impuse.

==Rezolvare==
<syntaxhighlight lang="python" line="1">
#2974 Z Zid
def conditii(inaltime, latime, zid):
    if not 2 <= latime <= 1_000_000_000:
        return False

    if not 2 <= inaltime <= 100_000:
        return False

    for rand in range(len(zid)):
        if not sum(zid[rand]) == latime:
            return False

    return True


def zzid(inaltime, latime, zid):
    # Creeăm un dicționar pentru a stoca frecvența fiecărei sume de segmente de zid
    frecv_sume = {}
    maxim = 0
    taietura = 0
    suma_curenta = 0

    # Iterăm peste fiecare rând de segmente de zid
    for i in range(inaltime):
        lungime = len(zid[i])
        # Iterăm peste fiecare segment din rândul curent
        for j in range(lungime):
            # Adăugăm segmentul curent la suma curentă
            segment = zid[i][j]
            suma_curenta += segment
            # Dacă suma este egală cu lățimea zidului, trecem la următorul segment
            if suma_curenta == latime:
                continue
            # Dacă suma există deja în dicționar...
            if suma_curenta in frecv_sume:
                # ...incrementăm numărul de apariții
                frecv_sume[suma_curenta] += 1
            else:
                # ...altfel, adăugăm suma în dicționar cu numărul de apariții 1
                frecv_sume[suma_curenta] = 1
            # Dacă numărul de apariții al sumei curente din dicționar este mai mare decât numărul maxim de apariții,
            # actualizăm numărul maxim de apariții și tăietura corespunzătoare
            if frecv_sume[suma_curenta] > maxim:
                maxim = frecv_sume[suma_curenta]
                taietura = suma_curenta
            # Dacă numărul de apariții al sumei curente din dicționar este egal cu numărul maxim de apariții și
            # tăietura curentă este mai aproape de lățimea dorită a zidului decât tăietura anterioară, actualizăm
            # tăietura corespunzătoare
            if frecv_sume[suma_curenta] == maxim and abs(latime - taietura - taietura) > abs(latime - suma_curenta - suma_curenta):
                taietura = suma_curenta
        # Resetăm suma curentă pentru următorul rând
        suma_curenta = 0

    # Printăm numărul minim de rânduri care trebuie tăiate și tăietura corespunzătoare
    print(f"{inaltime-maxim} {abs(taietura-latime+taietura)}")


if __name__ == "__main__":
    inaltime, latime = [int(x) for x in input().split()]

    zid = []

    for i in range(inaltime):
        latimi = [int(x) for x in input().split()[1:]]
        zid.append(latimi)

    if not conditii(inaltime, latime, zid):
        print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        print("Datele de intrare corespund restricțiilor impuse.")
        zzid(inaltime, latime, zid)

</syntaxhighlight>