3679 - Consolidare

Cerinţa

După consolidarea structurii de rezistență, a venit vremea refacerii zidului cetății. Acesta avea lungimea de L unități și înălțimea de H unități. El deteriorându-se în timp, acum nu mai este dreptunghiular ci, pe fiecare din cele L unități de lungime mai există Vi

unități, de material, așezate una peste alta și sprijinite pe fundație, deci până la înălțimea Vi
unități. Se dorește, evident, acoperirea zonelor rămase așa încât zidul să ajungă dreptunghiular, cu înălțimea de H unități pe fiecare din cele L unități de lungime.

Se dispune de bucăți de material, dreptunghiulare, cu o dimensiune de o unitate. Așadar putem spune că bucățile sunt de dimensiuni 1 X B(1 ≤ B ≤ L) și pentru fiecare valoare B dispunem de oricâte bucăți(să le numim de tipul B). Pentru ca zidul să fie stabil, bucățile trebuie să fie dispuse orizontal, adică una de dimensiune 1 X B va ocupa B unități pe lungime și o unitate pe înălțime. Se mai cunoaște că bucățile de același tip B au aceeași culoare și diferită de culoarea bucăților de alte tipuri. Pentru a fi zidul frumos, trebuie ca la aceeași înălțime față de fundație, să se folosească bucăți de material de aceeași culoare. Determinați numărul minim de bucăți necesare refacerii zidului.

Date de intrare

Fișierul de intrare consolidare.in conține pe prima linie două numere naturale L și H, separate prin spațiu, reprezentând, conform descrierii de mai sus, lungimea respectiv înălțimea pe care trebuie să o aibă zidul refăcut. Pe linia a doua se află L numere naturale nenule, separate prin câte un spațiu indicând, în ordine, înălțimea în unități a părții existente, pentru fiecare unitate de lungime.

Date de ieșire

Fișierul de ieșire consolidare.out va conține pe primul rând o valoare naturală ce reprezintă numărul minim de bucăți folosite pentru a construi zidul conform restricțiilor.

Restricţii şi precizări

• 1 ≤ L ≤ 100.000
• 1 ≤ H ≤ 10
• 0≤Vi≤H
• Nu este permis ca o bucată de material să iasă în afara celor L unități de lungime.

Exemplul 1

consolidare.in

 10 4
 0 0 1 3 0 1 1 2 2 2

consolidare.out

 9

Rezolvare

<syntaxhighlight lang="python" line> def minimum_pieces_needed(L, H, heights):

   pieces_needed = 0
   current_height = [0] * (H + 1)
   
   for i in range(L):
       for j in range(heights[i], H):
           if current_height[j] == 0:
               pieces_needed += 1
               current_height[j] = 1
       current_height[heights[i]] += 1
   
   return pieces_needed

def read_input(file_name):

   with open(file_name, 'r') as file:
       L, H = map(int, file.readline().split())
       heights = list(map(int, file.readline().split()))
   return L, H, heights

def write_output(file_name, result):

   with open(file_name, 'w') as file:
       file.write(str(result))

def main():

   L, H, heights = read_input("consolidare.in")
   result = minimum_pieces_needed(L, H, heights)
   write_output("consolidare.out", result)

if __name__ == "__main__":

   main()

</syntaxhighlight>