SPOJ in Armenian

Մասնագետները սովորաբար սեղմում են երկչափ պատկերները՝ գտնելով նմանատիպ պատկերի մասեր: Այս խնդրում մենք կնկարագրենք մի մեթոդ՝ հիմնված պատկերի հիերարխիկ տրոհման վրա: Պարզության համար կդիտարկենք սև և սպիտակ պատկերներ. օրինակ`

Նկար 1

Պատկերը հնարավոր է կոդավորել որպես ծառ, որի արմատին համապատասխանում է ամբողջ պատկերը: Եթե պատկերը կամ պատկերի մի մասը միագույն է, ապա համապատասխան ծառի գագաթը կլինի 0 կամ 1՝ կախված գույնից (0-սպիտակ, 1-սև): Հակառակ դեպքում պատկերը կենտրոնով բաժանվում է 4 հավասար մասի, և նրանց համար կառուցվում են ենթածառեր: Ծառի ներքին գագաթները կունենան 4 զավակ՝ համապատասխանաբար վերևի-աջ, վերևի-ձախ, ներքևի-ձախ և ներքևի-աջ ենթապատկերների համար: Նկար 1-ի պատկերին համապատասխան ծառը հետևյալն է.

Նկար 2

Ամբողջ պատկերը միագույն չէ, հետևաբար այն բաժանել ենք 4 մասի: Վերևի-աջ մասը միագույն սպիտակ է, հետևաբար արմատի առաջին զավակը տերև է 0 արժեքով: Վերևի-ձախ մասը միագույն չէ, հետևաբար այն բաժանվում է 4 մասի, որոնցից յուրաքանչյուրը միագույն է, և նրանց կհամապատասխանեն ծառի գագաթներ 0,0,1,0 արժեքներով: Ներքևի ենթապատկերները միագույն են, և նրանց համապատասխանում են ծառի տերևներ 0, 1 արժեքներով:

Որպես ավելի մեծ օրինակ դիտարկենք հետևյալ 8x8 չափի պատկերը և համապատասխան ծառը`

Նկար 3

Նկար 4

Կառուցված ծառը կապ չունի պատկերի սեղմման հետ, բայց նկարագրված մեթոդը կարելի է ձևափոխել՝ ավելի կոմպակտ արդյունք ստանալու համար: Ծառի կառուցումը դադարեցնել ոչ թե միագույն պատկերի դեպքում, այլ օրինակ 75%-ով միագույն պատկերի դեպքում: Պատկերին համապատասխանող ծառի գագաթը կլինի տերև այն դեպքում, եթե պատկերում սև կամ սպիտակ գույնը 75%-ից մեծ է կամ հավասար: Վերը նշված 8x8 չափի պատկերի համար կստանանք հետևյալ ծառը 75%-ի դեպքում.

Նկար 5

Նկատենք, որ ամբողջ պատկերի վերևի-ձախ մասը 75%-ով սև է, և ծառի արմատի երկրորդ զավակը 1 է: Իսկ ներքևի-ձախ մասի 75%-ից ավելը սպիտակ է, հետևաբար երրորդ զավակը նույնպես տերև է 0 արժեքով: Վերևի-աջ մասում ոչ սպիտակ, ոչ սև գույնը 75%-ից մեծ կամ հավասար չեն, և հիերարխիկ կառուցումը շարունակվում է այդ մասի համար բաժանելով այն 4 մասի, որոցից յուրաքանչյուրը 75%-ից ավել միագույն է: Եթե սեղմված ծառից փորձենք վերականգնել պատկերը, կստանանք հետևյալ պատկերը.

Նկար 6

Ձեր նպատակն է սկզբնական պատկերից կառուցել սեղմված պատկերը՝ ունենալով սեղմման տոկոսը (օրինակում սեղմման տոկոսը ընտրված էր 75%):

Մուտք

Առաջին տողում գրված է երկու ամբողջ թիվ - N (1 ≤ N ≤ 64), K (51 ≤ K ≤ 100): N-ը քառակուսի պատկերի չափն է, որը հանդիսանում է 2-ի աստիճան, իսկ K-ն՝ հիերարխիկ ծառի կառուցման սեղմման տոկոսը: Հաջորդ N տողերից յուրաքանչյուրը պարունակում է N հատ 0 կամ 1 սիմվոլ:

Ելք

Ելքում պետք է արտածել սեղմված պատկերը. անհրաժեշտ է արտածել N տող՝ յուրաքանչյուրում N հատ 0 կամ 1 սիմվոլ:

Օրինակ

Մուտքը.
8 75
11111000
11110000
11000011
11000011
11000100
00000100
00010011
00010011

Ելքը.
11110000
11110000
11110011
11110011
00000100
00000100
00000011
00000011