Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Compress the image

    The company you currently work for has a huge dataset of black-and-white images. They take up too much space, so the company asks you to implement a compression algorithm to save up space.
    Given an image that consists of black and white pixels (blacks are represented as 0s and whites are represented as 1s), you are asked to perform a hierarchical compression by K%.
    When applying a hierarchical compression, the algorithm starts from the whole image, then splits the image into 4 equal parts (top-left, top-right, bottom-left, and bottom-right), then splits each of the parts again into 4 equal parts, then does the same for the resulting parts, and so on. If the current part of the image is dominated by a single color, then the algorithm fills the whole part with that color and stops the splitting process there. We say the part is dominated by a single color if it forms ≥ K% of the part.
    Given the initial image, your task is to output the compressed one.

    Input

    The first line of the input contains two integers N (1 ≤ N ≤ 64) and K (51 ≤ K ≤ 100). N is guaranteed to be a power of 2.
    The next N lines contain N 0s or 1s.

    Output

    The program should output the compressed image.

    Examples

    Input
    8 75
    11111000
    11110000
    11000011
    11000011
    11000100
    00000100
    00010011
    00010011
    Output
    11110000
    11110000
    11110011
    11110011
    00000100
    00000100
    00000011
    00000011

    Explanation

    Input
    Input
     
    Output
    Output
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue