Comprimir la imagen
La empresa para la que trabajas cuenta con un gran conjunto de imágenes en blanco y negro. Estas ocupan demasiado espacio, así que la compañía te solicita que implementes un algoritmo de compresión para optimizar el almacenamiento.
Dada una imagen de que contiene píxeles en blanco y negro (los píxeles negros se representan con 0 y los blancos con 1), se te pide realizar una compresión jerárquica usando
K%.Cuando se aplica la compresión jerárquica, el algoritmo comienza con la imagen completa, luego la divide en 4 partes iguales (superior-izquierda, superior-derecha, inferior-izquierda e inferior-derecha). Después divide cada una de esas partes nuevamente en 4 partes iguales, y así sucesivamente. Si la parte actual de la imagen está dominada por un solo color, el algoritmo llena toda la parte con ese color y detiene su proceso de división. Se considera que una parte está dominada por un solo color si ese color forma
≥ K% de la parte.Dada la imagen inicial, tu tarea es producir la versión comprimida.
Entrada
La primera línea de la entrada contiene dos enteros
N (1 ≤ N ≤ 64) y K (51 ≤ K ≤ 100). Se garantiza que N es una potencia de 2.Las siguientes
N líneas contienen N valores que pueden ser 0 o 1.Salida
El programa debe mostrar la imagen comprimida.
Ejemplos
Input
8 75
11111000
11110000
11000011
11000011
11000100
00000100
00010011
00010011Output
11110000
11110000
11110011
11110011
00000100
00000100
00000011
00000011Explicación
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB