f637.
DF-expression
內容
DF-express (深度優先圖像表示式) 是一個具有高度資料壓縮能力的四元樹表示法。雖然主要為二階黑白圖片所設計，但是透過位元平面 (bit-plane) 或是 3D 表示法，亦可用來壓縮灰階圖片。
本題中所處理的圖片為二階的黑白圖片，也就是每個像素非黑即白，沒有中間的灰色。圖片大小為 𝑛×𝑛，𝑛 是 2 的冪次，也就是存在某個非負整數 𝑘 使得 𝑛 = 2𝑘。
一個 𝑛×𝑛 的黑白影像可以用下列遞迴方式編碼：
如果每一格像素都是白色，我們用0來表示； 如果每一格像素都是黑色，我們用1來表示； 否則，並非每一格像素都同色，先將影像均等劃分為四個邊長為 𝑛/2 的小正方形後，然後表示如下：先寫下2，之後依續接上左上、右上、左下、右下四塊的編碼。
一個壓縮後的影像會表示成一個由 0、1、2 組成的字串 𝑆。在這個問題中，根據字串 𝑆 以及影像尺寸 𝑛，請計算原始影像中有多少個像素是 1。
輸入說明
測試資料有兩行，第一行是影像的 DF-expression 𝑆，是由連續的 0、1、2 組成的字串，字串長度小於 1,100,000。第二行為正整數 𝑛，1 ≤ 𝑛 ≤ 1024，代表影像的大小為 𝑛 × 𝑛，其中 𝑛 必為 2 的冪次。
輸出說明
請輸出該影像中有多少像素是 1。
範例輸入
#1
2200101020110 4
範例輸出
#1
7
範例輸入
#2
2020020100010 8
範例輸出
#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
公開 測資點#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
提示 ：
對每一筆測試資料的執行時間限制均為 1 秒，，依正確通過測資筆數給分。其中：
第 1 子題組 10 分：𝑛 =2。
第 2 子題組 20 分：𝑛 = 4。
第 3 子題組 70 分：1 ≤ 𝑛 ≤ 1024。
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 38939 |
|
f637 | 175 | 2024-01-05 18:21 | |
| 26568 |
|
f637 | 1859 | 2021-08-13 21:45 | |
| 29951 |
|
f637 | 704 | 2022-04-15 12:42 | |
| 24242 |
|
f637 | 1564 | 2021-01-29 23:48 |