छवि को संपीड़ित करें
जिस कंपनी में आप अभी काम कर रहे हैं, उसके पास काले और सफेद छवियों का एक बहुत बड़ा डेटासेट मौजूद है। ये छवियाँ बहुत अधिक जगह घेरती हैं, इसलिए कंपनी चाहती है कि आप एक संपीड़न एल्गोरिथ्म (compression algorithm) लागू करें ताकि डिस्क में स्थान की बचत की जा सके।
आपको आकार की एक छवि दी गई है, जो काले (0 द्वारा दर्शाए गए) और सफेद (1 द्वारा दर्शाए गए) पिक्सेल से बनी होती है। आपका कार्य है इस छवि पर
K% की हाइरार्किकल संपीड़न (hierarchical compression) लागू करना।हाइरार्किकल संपीड़न लागू करने पर एल्गोरिथ्म पूरी छवि से शुरू होता है, फिर उसे चार बराबर भागों (ऊपरी-बायाँ, ऊपरी-दायाँ, निचला-बायाँ, और निचला-दायाँ) में विभाजित करता है। इसके बाद, प्रत्येक भाग को फिर से चार बराबर भागों में विभाजित किया जाता है, और यह प्रक्रिया इसी तरह आगे चलती रहती है। यदि किसी भाग में एक रंग का प्रभुत्व है, तो एल्गोरिथ्म उस भाग में पूरे क्षेत्र को उसी रंग से भर देता है और उस भाग का आगे विभाजन रोक देता है। किसी भाग को एक रंग से प्रभुत्वशाली माना जाता है यदि वह रंग उस भाग के
≥ K% पिक्सेल में मौजूद हो।शुरुआती छवि मिलने पर, आपको संपीड़ित छवि को आउटपुट में देना है।
इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
N (1 ≤ N ≤ 64) और K (51 ≤ K ≤ 100) दिए जाते हैं। यह सुनिश्चित है कि N दो का कोई घात (power of 2) होता है।अगली
N पंक्तियों में N बार 0 या 1 दिए जाते हैं।आउटपुट
प्रोग्राम को संपीड़ित छवि को आउटपुट में दिखाना होगा।
उदाहरण
Input
8 75
11111000
11110000
11000011
11000011
11000100
00000100
00010011
00010011Output
11110000
11110000
11110011
11110011
00000100
00000100
00000011
00000011स्पष्टीकरण
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB