Compresser l’image
La société pour laquelle vous travaillez dispose d’une grande quantité d’images en noir et blanc. Elles occupent trop d’espace, et l’entreprise vous demande donc de mettre en œuvre un algorithme de compression pour en réduire la taille.
Étant donné une image composée de pixels noirs et blancs (les noirs sont représentés par 0 et les blancs par 1), vous devez effectuer une compression hiérarchique à hauteur de
K%.Lors de la compression hiérarchique, l’algorithme part de l’image complète, puis divise l’image en 4 parties égales (haut-gauche, haut-droit, bas-gauche et bas-droit). Ensuite, chacune de ces parties est de nouveau divisée en 4 parties égales, et ainsi de suite. Si la zone actuelle de l’image est dominée par une seule couleur, alors l’algorithme remplit toute cette zone avec cette couleur et s’arrête. On dit qu’une zone est dominée par une seule couleur si elle représente
≥ K% de la zone.À partir de l’image initiale, votre tâche est de produire l’image compressée.
Entrée
La première ligne de l’entrée contient deux entiers
N (1 ≤ N ≤ 64) et K (51 ≤ K ≤ 100). On vous garantit que N est une puissance de 2.Les
N lignes suivantes contiennent N valeurs 0 ou 1.Sortie
Le programme doit produire l’image compressée.
Exemples
Input
8 75
11111000
11110000
11000011
11000011
11000100
00000100
00010011
00010011Output
11110000
11110000
11110011
11110011
00000100
00000100
00000011
00000011Explication
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB