Comprimi l'immagine
L'azienda per cui lavori attualmente possiede un vastissimo dataset di immagini in bianco e nero. Occupano troppo spazio, quindi l'azienda ti chiede di realizzare un algoritmo di compressione per ridurre l'utilizzo di memoria.
Data un'immagine composta da pixel in bianco e nero (i pixel neri sono rappresentati da 0, mentre quelli bianchi da 1), ti viene richiesto di eseguire una compressione gerarchica pari a K%.
Quando si applica la compressione gerarchica, l'algoritmo parte dall'intera immagine, la suddivide in 4 parti uguali (in alto a sinistra, in alto a destra, in basso a sinistra e in basso a destra), quindi suddivide nuovamente ciascuna parte in altre 4 parti uguali e prosegue in questo modo. Se la parte corrente dell'immagine è dominata da un singolo colore, l'algoritmo riempie completamente quella porzione con quel colore e interrompe il processo di suddivisione. Diciamo che una parte è “dominata” da un singolo colore se esso rappresenta almeno ≥ K% di quella parte.
Data l'immagine iniziale, il tuo compito è di produrre la versione compressa.
Dati in ingresso
La prima riga dei dati in ingresso contiene due interi N (1 ≤ N ≤ 64) e K (51 ≤ K ≤ 100). È garantito che N sia una potenza di 2.
Le successive N righe contengono N valori 0 o 1.
Dati in uscita
Il programma deve produrre l'immagine compressa.
Esempi
Input
8 75
11111000
11110000
11000011
11000011
11000100
00000100
00010011
00010011Output
11110000
11110000
11110011
11110011
00000100
00000100
00000011
00000011Spiegazione
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB