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

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

# 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