[Baekjoon] Z

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

Soluzione 1

Ho provato a creare un array di unita minime, ma era troppo difficile. Affrontarlo come problema di implementazione non funziona. Va risolto con la ricorsione, usando l’idea di sommare in blocco gli elementi considerati come gia visitati.

| 1 | 2 | | 3 | 4 |

Dividere le regioni dell’array nell’ordine mostrato sopra.

Coordinata di riferimento per dividere le regioni: angolo in alto a sinistra
size: lunghezza di un lato dell’area di ricerca corrente
Conteggio degli elementi considerati visitati: size*size
- Dato che gli elementi dell’array sono ordinati sequenzialmente, si accumulano i conteggi man mano

Se accumulare il conteggio:

Nell’area di ricerca corrente:
- Se (r, c) e presente: dividere l’area in 4 e cercare di nuovo
- Se (r, c) e assente: contare gli elementi nell’area e accumulare

Ho implementato la decisione di conteggio con la ricorsione.

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
    Funzione unità che divide l'area in 4.
10
    Il punto di riferimento dell'area è l'angolo in alto a sinistra.
11
    y: r
12
    x: c
13
    """
14
    global ans
15

16
    # Se l'area di ricerca corrisponde esattamente a (r, c), restituire
17
    if y == r and x == c:
18
        print(ans)
19
        return
20

21
    # Se (r, c) è nel quadrante corrente
22
    if r < y + size and r >= y and c < x + size and c >= x:
23
        # Cercare nel quadrante 1
24
        Z(y, x, size // 2)
25
        # Cercare nel quadrante 2
26
        Z(y, x + size // 2, size // 2)
27
        # Cercare nel quadrante 3
28
        Z(y + size // 2, x, size // 2)
29
        # Cercare nel quadrante 4
30
        Z(y + size // 2, x + size // 2, size // 2)
31
    # Accumulare tutti gli elementi nell'area corrente come visitati
32
    else:
33
        ans += size * size
34

35
# Partire da (0, 0), size=N^2 e restringere l'area di ricerca
36
Z(0, 0, (1 << n))

Soluzione 2

L’idea di accumulare i conteggi degli elementi e la stessa. La differenza e che diminuisce n mentre cerca (r, c), rendendolo leggermente piu veloce della ricorsione.

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
    # Primo quadrante
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)