Das Bild komprimieren
Das Unternehmen, für das du momentan arbeitest, besitzt einen riesigen Datensatz an Schwarz-Weiß-Bildern. Diese beanspruchen zu viel Speicherplatz, weshalb das Unternehmen dich bittet, einen Komprimierungsalgorithmus umzusetzen, um Speicher zu sparen.
Für ein Bild, das aus Schwarz-Weiß-Pixeln besteht (wobei Schwarz durch 0 und Weiß durch 1 dargestellt wird), sollst du eine hierarchische Komprimierung um
K% durchführen.Bei der hierarchischen Komprimierung beginnt der Algorithmus mit dem gesamten Bild und unterteilt es dann in vier gleich große Bereiche (oben links, oben rechts, unten links und unten rechts). Anschließend wird jeder dieser Bereiche erneut in vier gleich große Teile unterteilt, und so weiter. Wenn ein Bereich von einer einzigen Farbe dominiert wird, füllt der Algorithmus diesen gesamten Bereich mit dieser Farbe und beendet den Aufteilungsprozess an dieser Stelle. Wir sagen, ein Bereich wird von einer Farbe dominiert, wenn sie
≥ K% dieses Bereichs ausmacht.Ausgehend vom ursprünglichen Bild soll das komprimierte Bild ausgegeben werden.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
N (1 ≤ N ≤ 64) und K (51 ≤ K ≤ 100). Es ist garantiert, dass N eine Potenz von 2 ist.Die folgenden
N Zeilen enthalten jeweils N Nullen oder Einsen.Ausgabe
Das Programm soll das komprimierte Bild ausgeben.
Beispiele
Input
8 75
11111000
11110000
11000011
11000011
11000100
00000100
00010011
00010011Output
11110000
11110000
11110011
11110011
00000100
00000100
00000011
00000011Erklärung
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB