f637: DF-expression
Tags :
Accepted rate : 72人/80人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-02-19 17:23

Content

DF-express (深度優先圖像表示式) 是一個具有高度資料壓縮能力的四元樹表示法。雖然主要為二階黑白圖片所設計,但是透過位元平面 (bit-plane) 或是 3D 表示法,亦可用來壓縮灰階圖片。

本題中所處理的圖片為二階的黑白圖片,也就是每個像素非黑即白,沒有中間的灰色。圖片大小為 n×n,n 是 2 的冪次,也就是存在某個非負整數 k 使得 n = 2k

一個 n×n 的黑白影像可以用下列遞迴方式編碼:

如果每一格像素都是白色,我們用0來表示; 如果每一格像素都是黑色,我們用1來表示; 否則,並非每一格像素都同色,先將影像均等劃分為四個邊長為 n/2 的小正方形後,然後表示如下:先寫下2,之後依續接上左上、右上、左下、右下四塊的編碼。


一個壓縮後的影像會表示成一個由 0、1、2 組成的字串 S。在這個問題中,根據字串 S 以及影像尺寸 n,請計算原始影像中有多少個像素是 1。

Input

測試資料有兩行,第一行是影像的 DF-expression S,是由連續的 0、1、2 組成的字串,字串長度小於 1,100,000。第二行為正整數 n,1 ≤ n ≤ 1024,代表影像的大小為 n × n,其中 n 必為 2 的冪次。

Output

 請輸出該影像中有多少像素是 1。

Sample Input #1
2200101020110
4
Sample Output #1
7
Sample Input #2
2020020100010
8
Sample Output #2
17
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 0.5s , <1K
公開 測資點#1 (5%): 0.5s , <1K
公開 測資點#2 (5%): 0.5s , <1K
公開 測資點#3 (5%): 0.5s , <1K
公開 測資點#4 (5%): 0.5s , <1K
公開 測資點#5 (5%): 0.5s , <1K
公開 測資點#6 (5%): 0.5s , <1K
公開 測資點#7 (5%): 0.5s , <1K
公開 測資點#8 (5%): 0.5s , <1K
公開 測資點#9 (5%): 0.5s , <1K
公開 測資點#10 (5%): 0.5s , <1M
公開 測資點#11 (5%): 0.5s , <1M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 0.5s , <1K
公開 測資點#14 (5%): 0.5s , <1K
公開 測資點#15 (5%): 0.5s , <1K
公開 測資點#16 (5%): 0.5s , <1K
公開 測資點#17 (5%): 0.5s , <1K
公開 測資點#18 (5%): 0.5s , <1K
公開 測資點#19 (5%): 0.5s , <1K
Hint :

對每一筆測試資料的執行時間限制均為 1 秒,,依正確通過測資筆數給分。其中:
第 1 子題組 10 分:n =2。
第 2 子題組 20 分:n = 4。
第 3 子題組 70 分:1 ≤ n ≤ 1024。

Tags:
出處:
APCS201810程式實作題3 [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
24242
yes51851823@... (wseds)
f637
123 2021-01-29 23:48