APCS Oct 2018 - f637 Q3 [Python]

問題文:

DF-express（深さ優先画像表現）は、高い圧縮率を持つ四分木の表現方法です。主に白黒の二値画像向けですが、ビットプレーンや3D表現によってグレースケール画像も圧縮できます。この問題では、各画素は黒か白で、中間の灰色はありません。画像は n × n で、n は2のべき乗、つまり非負整数 k に対して n = 2^k です。再帰的に、全画素が白なら0、黒なら1と符号化します。それ以外は、一辺が n/2 の正方形4個に等分し、最初に2を書いた後、左上、右上、左下、右下の順に各領域の符号を連結します。

圧縮画像は0、1、2からなる文字列 S で表されます。S と画像の一辺 n が与えられたとき、元の画像で値が1の画素数を求めてください。

expression = input()
pixel = int(input())

index = [0]
pre_pixel = [pixel]

total = 0

for i in range(len(expression)):
    while index[-1] == 4:
        index.pop()
        pre_pixel.pop()
        index[-1] += 1

    if expression[i] == "0":
        index[-1] += 1
    elif expression[i] == "1":
        total += pre_pixel[-1] * pre_pixel[-1]
        index[-1] += 1
    elif expression[i] == "2":
        index.append(0)
        pre_pixel.append(pre_pixel[-1] // 2)

print(total)

この問題で使う知識：

• NaN

---

• [✔️] 必要であればコードをそのまま使用できます。
• [✔️] 共有する際は出典を明記してください。

この記事は繁体字中国語の原文をAIで翻訳したものです。意味や表現に違いがある可能性があります。正確な内容は繁体字中国語の原文をご確認ください。