2607 - Pentagon

În urma bombardamentelor din 11 septembrie 2001, clădirea Pentagonului a suferit daune la unul din pereții clădirii. Imaginea codificată a peretelui avariat se reprezintă sub forma unei matrice cu m linii și n coloane, ca în figura de mai jos:

1110000111

1100001111

1000000011

1111101111

1110000111

unde 1 reprezintă zid intact, iar 0 zid avariat. Sumele alocate pentru refacerea Pentagonului vor fi donate celor care vor ajuta americanii să refacă această clădire prin plasarea, pe verticală, a unor blocuri de înălțimi k, k=1, …, m, și lățime 1, în locurile avariate.

Cerința

Pentru o structură dată a unui perete din clădirea Pentagonului, determinaţi numărul minim al blocurilor, de înălţimi k=1, k=2, …, k=m, necesare refacerii clădirii.

Date de intrare

Fișierul de intrare pentagon.in conține pe prima linie dimensiunile m şi n ale peretelui clădirii, iar pe următoarele m linii câte o secvență de caractere 1 sau 0 de lungime n.

Date de ieșire

Fișierul de ieșire pentagon.out va conține pe câte o linie, ordonate crescător după k, perechi de forma k nr, unde k este înălțimea blocului, iar nr este numărul de blocuri de înălțime k, separate prin câte un spaţiu.

Restricții și precizări

• 1 ≤ m, n ≤ 200
• nu se vor afișa blocurile de înălțime k, a căror număr este zero (0).

Exemplu:

pentagon.in

5 10
1110000111
1100001111
1000000011
1111101111
1110000111

pentagon.out

1 7
2 1
3 2
5 1

<syntaxhighlight lang="python" line="1"> def min_blocks_to_repair(matrix):

   m = len(matrix)
   n = len(matrix[0])
   min_blocks = 0
   
   for col in range(n):
       row = 0
       while row < m:
           if matrix[row][col] == 0:
               height = 1
               while row + height < m and matrix[row + height][col] == 0:
                   height += 1
               min_blocks += 1
               row += height
           else:
               row += 1
               
   return min_blocks

1. Testare

matrix = [

   [1, 1, 1, 0, 0, 0, 1, 1, 1],
   [1, 1, 0, 0, 0, 0, 1, 1, 1],
   [1, 0, 0, 0, 0, 0, 0, 1, 1],
   [1, 1, 1, 1, 1, 0, 1, 1, 1],
   [1, 1, 1, 0, 0, 0, 1, 1, 1]

]

print(min_blocks_to_repair(matrix)) # Output: 8 </syntaxhighlight>