Comprimir a imagem
A empresa onde trabalhas atualmente tem um grande conjunto de imagens a preto e branco. Elas ocupam demasiado espaço, por isso a empresa pediu-te para implementar um algoritmo de compressão para reduzir o uso de armazenamento.
Dada uma imagem composta por pixeis a preto e branco (os pixeis pretos são representados por 0s e os pixeis brancos são representados por 1s), é-te solicitado que executes uma compressão hierárquica com
K%.Ao aplicar a compressão hierárquica, o algoritmo começa pela imagem inteira, depois divide a imagem em 4 partes iguais (superior-esquerda, superior-direita, inferior-esquerda e inferior-direita). Em seguida, cada uma das partes é novamente dividida em 4 partes iguais, e assim sucessivamente. Se a parte atual da imagem for dominada por uma única cor, então o algoritmo preenche toda essa parte com essa cor e não volta a dividi-la. Dizemos que uma parte é dominada por uma cor se essa cor constitui
≥ K% dessa parte.Dada a imagem inicial, a tua tarefa é produzir a imagem resultante após a compressão.
Entrada
A primeira linha da entrada contém dois inteiros
N (1 ≤ N ≤ 64) e K (51 ≤ K ≤ 100). Garante-se que N é uma potência de 2.As próximas
N linhas contêm N zeros ou uns.Saída
O programa deve apresentar a imagem comprimida.
Exemplos
Input
8 75
11111000
11110000
11000011
11000011
11000100
00000100
00010011
00010011Output
11110000
11110000
11110011
11110011
00000100
00000100
00000011
00000011Explicação
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB