2974 - Z Zid

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

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

• 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 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

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line="1">

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):

   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

   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>