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

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

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>