[Baekjoon] Z

https://www.acmicpc.net/problem/1074

Solution 1

I tried creating a minimal unit array, but it was too hard. Approaching this as an implementation problem doesn’t work. It needs to be solved with recursion, using the idea of summing up elements considered as previously visited all at once.

| 1 | 2 | | 3 | 4 |

Divide the array regions in the order shown above.

Reference coordinate for dividing regions: top-left corner
size: length of one side of the current search area
Count of elements considered previously visited: size*size
- Since array elements are sorted sequentially, accumulate the counts as you go

Whether to accumulate the count:

In the current search area:
- If (r, c) is present: divide the area into 4 and search again
- If (r, c) is absent: count the elements in the area and accumulate

I implemented the counting decision with recursion.

1
import sys
2
input = sys.stdin.readline
3

4
n, r, c = list(map(int, input().split()))
5
ans = 0
6

7
def Z(y, x, size):
8
    """
9
    Unit function that divides the area into 4.
10
    The reference point of the area is its top-left corner.
11
    y: r
12
    x: c
13
    """
14
    global ans
15

16
    # If the search area exactly matches (r, c), return
17
    if y == r and x == c:
18
        print(ans)
19
        return
20

21
    # If (r, c) is in the current quadrant
22
    if r < y + size and r >= y and c < x + size and c >= x:
23
        # Search quadrant 1
24
        Z(y, x, size // 2)
25
        # Search quadrant 2
26
        Z(y, x + size // 2, size // 2)
27
        # Search quadrant 3
28
        Z(y + size // 2, x, size // 2)
29
        # Search quadrant 4
30
        Z(y + size // 2, x + size // 2, size // 2)
31
    # Accumulate all elements in the current area as visited
32
    else:
33
        ans += size * size
34

35
# Start from (0, 0), size=N^2 and narrow down the search area
36
Z(0, 0, (1 << n))

Solution 2

The idea of accumulating element counts is the same. The difference is that it decreases n while searching for (r, c), making it slightly faster than recursion.

1
import sys
2
input = sys.stdin.readline
3

4
n, r, c = map(int, input().split())
5
cnt = 0
6
while n > 0:
7
    n -= 1
8
    # First quadrant
9
    if r < 2**n and c < 2**n:
10
        continue
11
    elif r < 2**n and c >= 2**n:
12
        cnt += (2**n)*(2**n)*1
13
        c -= 2**n
14
    elif r >= 2**n and c < 2**n:
15
        cnt += (2**n)*(2**n)*2
16
        r -= 2**n
17
    else:
18
        cnt += (2**n)*(2**n)*3
19
        r -= 2**n
20
        c -= 2**n
21

22
print(cnt)