DF-expression (APCS 2018-10 Advanced)

2.0s 256M

A square binary image of side \(n\) is encoded recursively. 0 represents an entirely white square, 1 an entirely black square, and 2 precedes four equal quadrants in top-left, top-right, bottom-left, bottom-right order. Given a valid encoding and side length, count black pixels.

Input

Read the encoding on the first line and \(n\) on the second.

Constraints

\(n\) is a power of two, \(1\le n\le1024\). Encoding length is less than \(1100000\). A single pixel is never split.

Output

Print the black pixel count.

Scoring

Each scored test independently awards 5 points, totaling 100. Samples award no points.

  • 1: 10% — \(n=2\)
  • 2: 20% — \(n=4\)
  • 3: 70% — No additional restrictions.

Sample Input 1

2200101020110
4

Sample Output 1

7

Sample Input 2

2020020100010
8

Sample Output 2

17

Source

f637 · 2018-10 APCS.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.