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==
Fișierul de ieșire <code>zzid.out</code> 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==

* <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
: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
:Date de intrare gresite!

==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 taierie_diferenta(inaltime, latime, zid):
    frecv_sume = {}
    maxim = 0
    suma_curenta = 0
    taietura = 0

    for i in range(inaltime):
        n = len(zid[i])

        for j in range(n):
            b = zid[i][j]
            suma_curenta += b
            if suma_curenta == latime:
                continue
            if suma_curenta in frecv_sume:
                frecv_sume[suma_curenta] += 1
            else:
                frecv_sume[suma_curenta] = 1
            if frecv_sume[suma_curenta] > maxim:
                maxim = frecv_sume[suma_curenta]
                taietura = suma_curenta
            if frecv_sume[suma_curenta] == maxim and abs(latime - taietura - taietura) > abs(latime - suma_curenta - suma_curenta):
                taietura = suma_curenta
        suma_curenta = 0

    return f"{inaltime-maxim} {abs(taietura-latime+taietura)}"


def 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):
        return print("Date de intrare gresite!")

    print(taierie_diferenta(inaltime, latime, zid))


if __name__ == "__main__":
    main()

</syntaxhighlight>