APCS Oct 2018 - f637 Q3 [Python]

Problem statement:

DF-express (depth-first image expression) is a quadtree representation with a high compression ratio. Although primarily designed for binary black-and-white images, it can also compress grayscale images through bit-plane or 3D representations. Here, every pixel is either black or white, with no gray levels. The image is n × n, where n is a power of 2: n = 2^k for a nonnegative integer k. Encode the image recursively: use 0 if all pixels are white and 1 if all are black. Otherwise, divide it into four equal squares of side n/2. Write 2, followed by the encodings of the top-left, top-right, bottom-left, and bottom-right squares, in that order.

The compressed image is a string S containing 0, 1, and 2. Given S and image size n, calculate how many pixels in the original image have value 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)

Key concepts:

NaN

[✔️] You may use the code directly if needed.
[✔️] Please credit the source when sharing.

Result

This article was translated from Traditional Chinese by AI. Meaning or wording may differ; please refer to the Traditional Chinese original as the authoritative version.

APCS Oct 2018 - f637 Q3 [Python]

Problem statement:

DF-express (depth-first image expression) is a quadtree representation with a high compression ratio. Although primarily designed for binary black-and-white images, it can also compress grayscale images through bit-plane or 3D representations. Here, every pixel is either black or white, with no gray levels. The image is n × n, where n is a power of 2: n = 2^k for a nonnegative integer k. Encode the image recursively: use 0 if all pixels are white and 1 if all are black. Otherwise, divide it into four equal squares of side n/2. Write 2, followed by the encodings of the top-left, top-right, bottom-left, and bottom-right squares, in that order.

The compressed image is a string S containing 0, 1, and 2. Given S and image size n, calculate how many pixels in the original image have value 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)

Key concepts:

NaN

[✔️] You may use the code directly if needed.
[✔️] Please credit the source when sharing.

Result

This article was translated from Traditional Chinese by AI. Meaning or wording may differ; please refer to the Traditional Chinese original as the authoritative version.