Problem:


Score : 600 points

Problem Statement

For a non-negative integer K, we define a fractal of level K as follows:

A fractal of level 0 is a grid with just one white square.

When K > 0, a fractal of level K is a 3^K \times 3^K grid. If we divide this grid into nine 3^{K-1} \times 3^{K-1} subgrids:

The central subgrid consists of only black squares.

Each of the other eight subgrids is a fractal of level K-1.

For example, a fractal of level 2 is as follows:

In a fractal of level 30, let (r, c) denote the square at the r-th row from the top and the c-th column from the left.

You are given Q quadruples of integers (a_i, b_i, c_i, d_i).
For each quadruple, find the distance from (a_i, b_i) to (c_i, d_i).

Here the distance from (a, b) to (c, d) is the minimum integer n that satisfies the following condition:

There exists a sequence of white squares (x_0, y_0), \ldots, (x_n, y_n) satisfying the following conditions:

(x_0, y_0) = (a, b)

(x_n, y_n) = (c, d)

For every i (0 \leq i \leq n-1), (x_i, y_i) and (x_{i+1}, y_{i+1}) share a side.

Constraints

1 \leq Q \leq 10000

1 \leq a_i, b_i, c_i, d_i \leq 3^{30}

(a_i, b_i) \neq (c_i, d_i)

(a_i, b_i) and (c_i, d_i) are white squares.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

Q
a_1 \ b_1 \ c_1 \ d_1
:
a_Q \ b_Q \ c_Q \ d_Q

Output

Print Q lines.
The i-th line should contain the distance from (a_i, b_i) to (c_i, d_i).

Sample Input 1

2
4 2 7 4
9 9 1 9

Sample Output 1

5
8



Sample input:
2
4 2 7 4
9 9 1 9


Sample output:
5
8

Submission status: Wrong Answer

Solution code:
for i in range(int(input())):
    a,b,c,d=map(int,input().split())
    print(abs(a-c)+abs(b-d))

Submission status: Wrong Answer

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def get_block(X1, Y1, X2, Y2):
    # x1 から x2 の間にある、y方向の両端が y1 と y2 より大きいブロック
    if X1 > X2:
        X1, X2 = X2, X1
    size = pow(3, 30)
    for level in reversed(range(31)):
        x1 = X1 // size
        x2 = X2 // size
        y1 = Y1 // size
        y2 = Y2 // size
        if y1 != y2:
            return None
        # x1 と x2 の間に 1, 4, 7, ... があればそれ
        if x2 - x1 >= 2:
            while x1 % 3 != 1:
                x1 += 1
            return x1 * size, y1 * size, size
        size //= 3
    return None


def dist(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)


def solve(X1, Y1, X2, Y2):
    # 一番大きい障害物を知りたい
    block = get_block(X1, Y1, X2, Y2)
    ret = INF
    if block:
        x, y, size = block
        for x, y in itertools.product((x - 1, x + size), (y - 1, y + size)):
            ret = min(ret, dist(X1, Y1, x, y) + dist(X2, Y2, x, y))
    else:
        ret = min(ret, dist(X1, Y1, X2, Y2))

    block = get_block(Y1, X1, Y2, X2)
    if block:
        x, y, size = block
        for x, y in itertools.product((x - 1, x + size), (y - 1, y + size)):
            ret = min(ret, dist(X1, Y1, x, y) + dist(X2, Y2, x, y))
    else:
        ret = min(ret, dist(X1, Y1, X2, Y2))
    return ret


Q = int(sys.stdin.buffer.readline())
ABCD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]
for a, b, c, d in ABCD:
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    ans = solve(a, b, c, d)
    print(ans)

Submission status: Wrong Answer

Solution code:
def solve(a,b,c,d):
  x1,y1,x2,y2=a,b,c,d
  mx=my=0
  if x1==x2 and x1%3==2 and abs(y1-y2)>=2:mx=1
  if y1==y2 and y1%3==2 and abs(x1-x2)>=2:my=1
  for i in range(29):
    x1=0--x1//3
    y1=0--y1//3
    x2=0--x2//3
    y2=0--y2//3
    if x1==x2 and x1%3==2 and abs(y1-y2)>=2:mx=i+2
    if y1==y2 and y1%3==2 and abs(x1-x2)>=2:my=i+2
  ans=abs(a-c)+abs(b-d)
  if mx<my:
    mi=3**(my-1)
    ma=2*3**(my-1)+1
    bd=(3**my)*((0--b//(3**my))-1)
    b-=bd
    d-=bd
    ans+=min(abs(mi-b)+abs(mi-d),abs(ma-b)+abs(ma-d))
    return ans+abs(a-c)
  if mx>my:
    mi=3**(mx-1)
    ma=2*3**(mx-1)+1
    ac=(3**mx)*((0--a//(3**mx))-1)
    a-=ac
    c-=ac
    ans+=min(abs(mi-a)+abs(mi-c),abs(ma-a)+abs(ma-c))
    return ans+abs(b-d)
  if mx==my==0:return abs(a-c)+abs(b-d)
  ans=1/0#正しければ実行されないはず
q=int(input())
for _ in range(q):
  a,b,c,d=map(int,input().split())
  print(solve(a,b,c,d))

Submission status: Wrong Answer

Solution code:
def solve(a,b,c,d):
  x1,y1,x2,y2=a,b,c,d
  mx=my=0
  if x1==x2 and x1%3==2:mx=1
  if y1==y2 and y1%3==2:my=1
  for i in range(29):
    x1=0--x1//3
    y1=0--y1//3
    x2=0--x2//3
    y2=0--y2//3
    if x1==x2 and x1%3==2 and abs(y1-y2)>=2:mx=i+2
    if y1==y2 and y1%3==2 and abs(x1-x2)>=2:my=i+2
  ans=abs(a-c)+abs(b-d)
  if mx<my:
    mi=3**(my-1)
    ma=2*3**(my-1)+1
    bd=(3**my)*((0--b//(3**my))-1)
    b-=bd
    d-=bd
    ans+=min(abs(mi-b)+abs(mi-d),abs(ma-b)+abs(ma-d))
    return ans+abs(a-c)
  if mx>my:
    mi=3**(mx-1)
    ma=2*3**(mx-1)+1
    ac=(3**mx)*((0--a//(3**mx))-1)
    a-=ac
    c-=ac
    ans+=min(abs(mi-a)+abs(mi-c),abs(ma-a)+abs(ma-c))
    return ans+abs(b-d)
  if mx==my==0:return abs(a-c)+abs(b-d)
  ans=1/0#正しければ実行されないはず
q=int(input())
for _ in range(q):
  a,b,c,d=map(int,input().split())
  print(solve(a,b,c,d))

Submission status: Wrong Answer

Solution code:
def solve(a,b,c,d):
  x1,y1,x2,y2=a,b,c,d
  mx=my=0
  if x1==x2 and x1%3==2:mx=1
  if y1==y2 and y1%3==2:my=1
  for i in range(29):
    x1=0--x1//3
    y1=0--y1//3
    x2=0--x2//3
    y2=0--y2//3
    if x1==x2 and x1%3==2 and abs(y1-y2)>=2:mx=i+2
    if y1==y2 and y1%3==2 and abs(x1-x2)>=2:my=i+2
  ans=abs(a-c)+abs(b-d)
  if mx<my:
    mi=3**(my-1)
    ma=2*3**(my-1)+1
    ans+=min(abs(mi-b)+abs(mi-d),abs(ma-b)+abs(ma-d))
    return ans
  if mx>my:
    mi=3**(mx-1)
    ma=2*3**(mx-1)+1
    ans+=min(abs(mi-a)+abs(mi-c),abs(ma-a)+abs(ma-c))
    return ans
  if mx==my==0:return ans
  ans=1/0#正しければ実行されないはず
q=int(input())
for _ in range(q):
  a,b,c,d=map(int,input().split())
  print(solve(a,b,c,d))

Submission status: Wrong Answer

Solution code:
s=lambda t,i:0--t//3**i
for _ in range(int(input())):
  a,b,c,d=map(int,input().split());mx=max([i for i in range(30) if s(a,i)==s(c,i)and s(a,i)%3==2and abs(s(b,i)-s(d,i))>=2]+[-1])+1;my=max([i for i in range(30) if s(b,i)==s(d,i)and s(b,i)%3==2and abs(s(a,i)-s(c,i))>=2]+[-1])+1
  if mx<my:mx,a,b,c,d=my,b,a,d,c
  mi=3**(mx-1);ma=2*mi+1;ac=(3*mi)*((0--a//(3*mi))-1);a-=ac;c-=ac;print(abs(b-d)+min(abs(mi-a)+abs(mi-c),abs(ma-a)+abs(ma-c)))

Submission status: Wrong Answer

Solution code:
def solve(a,b,c,d):
  x1,y1,x2,y2=a,b,c,d
  mx=my=0
  if x1==x2 and x1%3==2:mx=1
  if y1==y2 and y1%3==2:my=1
  for i in range(29):
    x1=0--x1//3
    y1=0--y1//3
    x2=0--x2//3
    y2=0--y2//3
    if x1==x2 and x1%3==2:mx=i+2
    if y1==y2 and y1%3==2:my=i+2
  if mx<my:
    ans=abs(a-c)
    mi=3**(my-1)
    ma=2*3**(my-1)+1
    l=3**my
    ll=l*((0--b//l)-1)
    b-=ll
    d-=ll
    ans+=min(abs(mi-b)+abs(mi-d),abs(ma-b)+abs(ma-d))
    return ans
  if mx>my:
    ans=abs(b-d)
    mi=3**(mx-1)
    ma=2*3**(mx-1)+1
    l=3**mx
    ll=l*((0--a//l)-1)
    a-=ll
    c-=ll
    ans+=min(abs(mi-a)+abs(mi-c),abs(ma-a)+abs(ma-c))
    return ans
  if mx==my==0:return abs(a-c)+abs(b-d)
  ans=1/0#正しければ実行されないはず
q=int(input())
for _ in range(q):
  a,b,c,d=map(int,input().split())
  print(solve(a,b,c,d))

Submission status: Wrong Answer

Solution code:
def solve2(aa,bb,cc,dd):
  a,b,c,d=aa,bb,cc,dd
  mx=my=0
  if a==c and a%3==2:my=1
  if b==d and b%3==2:mx=1
  for i in range(29):
    a=0--a//3
    b=0--b//3
    c=0--c//3
    d=0--d//3
    if a==c and a%3==2:my=i+2
    if b==d and b%3==2:mx=i+2
  return [mx,my]
def solve(aa,bb,cc,dd):
  a,b,c,d=aa,bb,cc,dd
  mx,my=solve2(aa,bb,cc,dd)
  if mx<my:
    ans=abs(b-d)
    mi=3**(my-1)
    ma=mi*2+1
    h=mi*3
    x=h*((0--a//h)-1)
    a-=x
    c-=x
    ans+=min(abs(mi-a)+abs(mi-c),abs(ma-a)+abs(ma-c))
    return ans
  if mx>my:
    ans=abs(a-c)
    mi=3**(mx-1)
    ma=mi*2+1
    h=mi*3
    y=h*((0--b//h)-1)
    b-=y
    d-=y
    ans+=min(abs(mi-b)+abs(mi-d),abs(ma-b)+abs(ma-d))
    return ans
  return abs(a-c)+abs(b-d)
q=int(input())
for _ in range(q):
  a,b,c,d=map(int,input().split())
  print(solve(a,b,c,d))

Submission status: Wrong Answer

Solution code:
grid_lens = [3 ** i for i in range(30)]


def calc_position(x1, x2):
    for block_lv in range(29, -1, -1):
        x1_block, child_x1 = divmod(x1, grid_lens[block_lv])
        x2_block, child_x2 = divmod(x2, grid_lens[block_lv])

        if block_lv == 0 or x1_block != x2_block or x1_block == 1:
            return x1, x2, x1_block, x2_block, block_lv

        x1 %= grid_lens[block_lv]
        x2 %= grid_lens[block_lv]
    else:
        return 0, 0, 0, 0, 0


def main():
    q = int(input())

    for _ in range(q):
        r1, c1, r2, c2 = map(lambda x: int(x) - 1, input().split())

        r1, r2, r1_block, r2_block, r_block_lv = calc_position(r1, r2)
        c1, c2, c1_block, c2_block, c_block_lv = calc_position(c1, c2)

        if r1_block == r2_block == 1 and {c1_block, c2_block} == {0, 2}:
            dist = abs(c1 - c2) + min(r1 + r2 + 2 - (grid_lens[r_block_lv] << 1),
                                      (grid_lens[r_block_lv] << 2) - (r1 + r2))
        elif c1_block == c2_block == 1 and {r1_block, r2_block} == {0, 2}:
            dist = abs(r1 - r2) + min(c1 + c2 + 2 - (grid_lens[c_block_lv] << 1),
                                      (grid_lens[c_block_lv] << 2) - (c1 + c2))
        else:
            dist = abs(r1 - r2) + abs(c1 - c2)

        print(dist)


main()

Submission status: Wrong Answer

Solution code:
# PANA2020
q = int(input())
query = [tuple(map(int, input().split())) for _ in range(q)]

def man(a, b, c, d):
    return abs(a - c) + abs(b - d)

def solve(a, b, c, d, i, carry):
    if (a, b) == (c, d):
        return carry
    if i == 29:
        if (a, c) == (1, 1) or (b, d) == (1, 1):
            return 4 + carry
        else:
            return man(a,b,c,d) + carry
    k = 3 ** (30 - 1 - i)
    ga = a // k
    gb = b // k
    gc = c // k
    gd = d // k
    if (ga, gb) == (gc, gd):
        a %= k
        b %= k
        c %= k
        d %= k
        return solve(a,b,c,d,i+1,carry)
    if ga != gc and gb != gd:
        return man(a,b,c,d) + carry
    if gb == gd:
        a,b,c,d = b,a,d,c
        ga = a // k
        gb = b // k
        gc = c // k
        gd = d // k
    if ga == 1:
        return carry + abs(b - d) + min(a+c - 2*(k-1), 4*k - a - c)
    if b > d:
        a,b,c,d = c,d,a,b
        ga = a // k
        gb = b // k
        gc = c // k
        gd = d // k
    # ga == gc != 1 and gb < gd
    a %= k
    c %= k
    kk = k // 3
    gga = a // kk
    ggb = b // kk
    ggc = c // kk
    ggd = d // kk
    if ggd - ggb == 1:
        return solve(a % kk, b % kk, c % kk, d % kk + kk, i+1, carry)
    else:
        nb = b % kk
        nd = d % kk + 2 * kk
        carry += (d - b) - (nd - nb)
        return solve(a,nb,c,nd,i+1,carry)

for a, b, c, d in query:
    print(solve(a-1,b-1,c-1,d-1,0,0))

Submission status: Wrong Answer

Solution code:
q = int(input())
query = [tuple(map(int, input().split())) for _ in range(q)]

def man(a, b, c, d):
    return abs(a - c) + abs(b - d)

def solve(a, b, c, d, i, carry):
    if (a, b) == (c, d):
        return carry
    if i == 29:
        if (a, c) == (1, 1) or (b, d) == (1, 1):
            return 4 + carry
        else:
            return man(a,b,c,d) + carry
    k = 3 ** (30 - 1 - i)
    ga = a // k
    gb = b // k
    gc = c // k
    gd = d // k
    if (ga, gb) == (gc, gd):
        a %= k
        b %= k
        c %= k
        d %= k
        return solve(a,b,c,d,i+1,carry)
    if ga != gc and gb != gd:
        return man(a,b,c,d) + carry
    if gb == gd:
        a,b,c,d = b,a,d,c
        ga = a // k
        gb = b // k
        gc = c // k
        gd = d // k
    if ga == 1:
        return 2 * min(min(a, c) - k + 1, 2 * k - max(a, c)) + man(a,b,c,d) + carry
    if b > d:
        a,b,c,d = c,d,a,b
        ga = a // k
        gb = b // k
        gc = c // k
        gd = d // k
    # ga == gc != 1 and gb < gd
    kk = k // 3
    gga = (a % k) // kk
    ggb = b // kk
    ggc = (c % k) // kk
    ggd = d // kk
    if (gga, ggc) == (1, 1):
        if ggd - ggb == 1:
            return solve(a % kk, b % kk, c % kk, d % kk + kk, i+1, carry)
        else:
            a %= k
            c %= k
            return carry + d - b + min(a + c - 2*(kk-1), 4*k - a - c)
    else:
        a %= k
        c %= k
        nb = b % kk
        nd = d % kk
        carry += (d - b) - (nd - nb)
        return solve(a,nb,c,nd,i+1,carry)

for a, b, c, d in query:
    print(solve(a-1,b-1,c-1,d-1,0,0))

Submission status: Wrong Answer

Solution code:
import numpy as np
Q = int(input())
ans = []
for loop1 in range(Q):
    a, b, c, d = map(int,input().split())
    a, b, c, d = a-1, b-1, c-1, d-1
    a1, b1, c1, d1 = a, b, c, d
    A, B, C, D = [], [], [], []
    for loop2 in range(30):
        A.append(a1 % 3)
        B.append(b1 % 3)
        C.append(c1 % 3)
        D.append(d1 % 3)
        a1 //= 3
        b1 //= 3
        c1 //= 3
        d1 //= 3
        if a1 + b1 + c1 + d1 == 0:
            break
    k = len(A)
    A = np.array(A)
    B = np.array(B)
    C = np.array(C)
    D = np.array(D)
    if a > c:
        A = 2 - A
        a = 3 ** k - 1 - a
        C = 2 - C
        c = 3 ** k - 1 - c
    if b > d:
        B = 2 - B
        b = 3 ** k - 1 - b
        D = 2 - D
        d = 3 ** k - 1 - d
    R = [0, 0]
    end = False
    for i in range(1, k + 1):
        if end:
            break
        R[0] = R[0] * 3 + A[-i]
        R[1] = R[1] * 3 + B[-i]
        if A[-i] == C[-i] and B[-i] == D[-i]:
            if i == k:
                ans.append(0)
            continue
        if A[-i] != C[-i] and B[-i] != D[-i]:
            ans.append((c - a) + (d - b))
            break
        else:
            if B[-i] == D[-i]:
                a, b, c, d = b, a, d, c
                A, B, C, D = B[0:], A[0:], D[0:], C[0:]
                R = R[::-1]
            if A[-i] == 1:
                mid1 = R[0] * (3 ** (k - i)) - 1
                mid2 = (R[0] + 1) * (3 ** (k - i))
                route1 = (a - mid1) + (d - b) + (c - mid1)
                route2 = (mid2 - a) + (d - b) + (mid2 - c)
                ans.append(min(route1, route2))
                break
            else:
                if i == k:
                    ans.append(d - b)
                    break
                bt = B[-i]
                dt = D[-i]
                for j in range(i + 1, k + 1):
                    R[0] = R[0] * 3 + A[-j]
                    bt = bt * 3 + B[-j]
                    dt = dt * 3 + D[-j]
                    dis = dt - bt
                    if A[-j] != C[-j]:
                        ans.append((c - a) + (d - b))
                        break
                    else:
                        if A[-j] == 1:
                            if dis > 1:
                                mid1 = R[0] * (3 ** (k - j)) - 1
                                mid2 = (R[0] + 1) * (3 ** (k - j))
                                route1 = (a - mid1) + (d - b) + (c - mid1)
                                route2 = (mid2 - a) + (d - b) + (mid2 - c)
                                ans.append(min(route1, route2))
                                end = True
                                break
                            else:
                                if j == k:
                                    ans.append(d - b)
                                    end = True
                                continue
                        else:
                            if j == k:
                                ans.append(d - b)
                                end = True
                            continue
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
import numpy as np
Q = int(input())
ans = []
for loop1 in range(Q):
    a, b, c, d = map(int,input().split())
    a, b, c, d = a-1, b-1, c-1, d-1
    a1, b1, c1, d1 = a, b, c, d
    A, B, C, D = [], [], [], []
    for loop2 in range(30):
        A.append(a1 % 3)
        B.append(b1 % 3)
        C.append(c1 % 3)
        D.append(d1 % 3)
        a1 //= 3
        b1 //= 3
        c1 //= 3
        d1 //= 3
        if a1 + b1 + c1 + d1 == 0:
            break
    k = len(A)
    A = np.array(A)
    B = np.array(B)
    C = np.array(C)
    D = np.array(D)
    if a > c:
        A = 2 - A
        C = 2 - C
    if b > d:
        B = 2 - B
        D = 2 - D
    R = [0, 0]
    end = False
    for i in range(1, k + 1):
        if end:
            break
        R[0] = R[0] * 3 + A[-i]
        R[1] = R[1] * 3 + B[-i]
        if A[-i] == C[-i] and B[-i] == D[-i]:
            if i == k:
                ans.append(0)
            continue
        if A[-i] != C[-i] and B[-i] != D[-i]:
            ans.append((c - a) + (d - b))
            break
        else:
            if B[-i] == D[-i]:
                a, b, c, d = b, a, d, c
                A, B, C, D = B[0:], A[0:], D[0:], C[0:]
                R = R[::-1]
            if A[-i] == 1:
                mid1 = R[0] * (3 ** (k - i)) - 1
                mid2 = (R[0] + 1) * (3 ** (k - i))
                route1 = (a - mid1) + (d - b) + (c - mid1)
                route2 = (mid2 - a) + (d - b) + (mid2 - c)
                ans.append(min(route1, route2))
                break
            else:
                if i == k:
                    ans.append(d - b)
                    break
                bt = B[-i]
                dt = D[-i]
                for j in range(i + 1, k + 1):
                    R[0] = R[0] * 3 + A[-j]
                    bt = bt * 3 + B[-j]
                    dt = dt * 3 + D[-j]
                    dis = dt - bt
                    if A[-j] != C[-j]:
                        ans.append((c - a) + (d - b))
                        break
                    else:
                        if A[-j] == 1:
                            if dis > 1:
                                mid1 = R[0] * (3 ** (k - j)) - 1
                                mid2 = (R[0] + 1) * (3 ** (k - j))
                                route1 = (a - mid1) + (d - b) + (c - mid1)
                                route2 = (mid2 - a) + (d - b) + (mid2 - c)
                                ans.append(min(route1, route2))
                                end = True
                                break
                            else:
                                if j == k:
                                    ans.append(d - b)
                                    end = True
                                continue
                        else:
                            if j == k:
                                ans.append(d - b)
                                end = True
                            continue
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
import numpy as np
Q = int(input())
ans = []
for loop1 in range(Q):
    a, b, c, d = map(int,input().split())
    a, b, c, d = a-1, b-1, c-1, d-1
    a1, b1, c1, d1 = a, b, c, d
    A, B, C, D = [], [], [], []
    for loop2 in range(30):
        A.append(a1 % 3)
        B.append(b1 % 3)
        C.append(c1 % 3)
        D.append(d1 % 3)
        a1 //= 3
        b1 //= 3
        c1 //= 3
        d1 //= 3
        if a1 + b1 + c1 + d1 == 0:
            break
    k = len(A)
    A = np.array(A)
    B = np.array(B)
    C = np.array(C)
    D = np.array(D)
    if a > c:
        A = 2 - A
        C = 2 - C
    if b > d:
        B = 2 - B
        D = 2 - D
    R = [0, 0]
    end = False
    for i in range(1, k + 1):
        if end:
            break
        R[0] = R[0] * 3 + A[-i]
        R[1] = R[1] * 3 + B[-i]
        if A[-i] == C[-i] and B[-i] == D[-i]:
            if i == k:
                ans.append(0)
            continue
        if A[-i] != C[-i] and B[-i] != D[-i]:
            ans.append((c - a) + (d - b))
            break
        else:
            if B[-i] == D[-i]:
                a, b, c, d = b, a, d, c
                A, B, C, D = B[0:], A[0:], D[0:], C[0:]
                R = R[::-1]
            if A[-i] == 1:
                mid1 = R[0] * (3 ** (k - i)) - 1
                mid2 = (R[0] + 1) * (3 ** (k - i))
                route1 = (a - mid1) + (d - b) + (c - mid1)
                route2 = (mid2 - a) + (d - b) + (mid2 - c)
                ans.append(min(route1, route2))
                break
            else:
                if i == k:
                    ans.append(d - b)
                    break
                bt = B[-i]
                dt = D[-i]
                for j in range(i + 1, k + 1):
                    R[0] = R[0] * 3 + A[-j]
                    bt = bt * 3 + B[-j]
                    dt = dt * 3 + D[-j]
                    dis = dt - bt
                    if A[-j] != C[-j]:
                        ans.append((c - a) + (d - b))
                        break
                    else:
                        if A[-j] == 1:
                            if dis > 1:
                                mid1 = R[0] * (3 ** (k - j)) - 1
                                mid2 = (R[0] + 1) * (3 ** (k - j))
                                route1 = (a - mid1) + (d - b) + (c - mid1)
                                route2 = (mid2 - a) + (d - b) + (mid2 - c)
                                ans.append(min(route1, route2))
                                end = True
                                break
                            else:
                                if j == k:
                                    ans.append(1)
                                    end = True
                                continue
                        else:
                            if j == k:
                                ans.append(d - b)
                                end = True
                            continue
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
import numpy as np
Q = int(input())
ans = []
for loop1 in range(Q):
    a, b, c, d = map(int,input().split())
    a, b, c, d = a-1, b-1, c-1, d-1
    a1, b1, c1, d1 = a, b, c, d
    A, B, C, D = [], [], [], []
    for loop2 in range(30):
        A.append(a1 % 3)
        B.append(b1 % 3)
        C.append(c1 % 3)
        D.append(d1 % 3)
        a1 //= 3
        b1 //= 3
        c1 //= 3
        d1 //= 3
        if a1 + b1 + c1 + d1 == 0:
            break
    k = len(A)
    A = np.array(A)
    B = np.array(B)
    C = np.array(C)
    D = np.array(D)
    if a > c:
        A = 2 - A
        C = 2 - C
    if b > d:
        B = 2 - B
        D = 2 - D
    R = [0, 0]
    end = False
    for i in range(1, k + 1):
        if end:
            break
        R[0] = R[0] * 3 + A[-i]
        R[1] = R[1] * 3 + B[-i]
        if A[-i] == C[-i] and B[-i] == D[-i]:
            if i == k:
                ans.append(0)
            continue
        if A[-i] != C[-i] and B[-i] != D[-i]:
            ans.append((c - a) + (d - b))
            break
        else:
            if B[-i] == D[-i]:
                a, b, c, d = b, a, d, c
                A, B, C, D = B[0:], A[0:], D[0:], C[0:]
                R = R[::-1]
            if A[-i] == 1:
                mid1 = R[0] * (3 ** (k - i)) - 1
                mid2 = (R[0] + 1) * (3 ** (k - i))
                route1 = (a - mid1) + (d - b) + (c - mid1)
                route2 = (mid2 - a) + (d - b) + (mid2 - c)
                ans.append(min(route1, route2))
                break
            else:
                if i == k:
                    ans.append(d - b)
                    break
                bt = B[-i]
                dt = D[-i]
                for j in range(i + 1, k + 1):
                    R[0] = R[0] * 3 + A[-j]
                    bt = bt * 3 + B[-j]
                    dt = dt * 3 + D[-j]
                    dis = dt - bt
                    if A[-j] != C[-j]:
                        ans.append((c - a) + (d - b))
                        break
                    else:
                        if A[-j] == 1:
                            if dis > 1:
                                mid1 = R[0] * (3 ** (k - j)) - 1
                                mid2 = (R[0] + 1) * (3 ** (k - j))
                                route1 = (a - mid1) + (d - b) + (c - mid1)
                                route2 = (mid2 - a) + (d - b) + (mid2 - c)
                                ans.append(min(route1, route2))
                                end = True
                                break
                            else:
                                if j == k:
                                    ans.append(1)
                                    end = True
                                continue
                        else:
                            if j == k:
                                ans.append(dis)
                                end = True
                            continue
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:

def solve2(aa,bb,cc,dd,lv):
  a,b,c,d=aa,bb,cc,dd
  m=3**(lv-1)
  mm=2*m+1
  ab=3*((0--b//m)-1)+(0--a//m)
  cd=3*((0--d//m)-1)+(0--c//m)
  if ab>cd:
    ab,cd=cd,ab
    a,b,c,d=c,d,a,b
  if ab==cd:
    mx=m*((0--a//m)-1)
    my=m*((0--b//m)-1)
    a-=mx
    b-=my
    c-=mx
    d-=my
    return [2,[a,b,c,d]]
  if ab==2 and cd==8:
    ans=abs(b-d)+min(abs(a-m)+abs(c-m),abs(a-mm)+abs(c-mm))
    return [0,ans]
  if ab==4 and cd==6:
    ans=abs(a-c)+min(abs(b-m)+abs(d-m),abs(b-mm)+abs(d-mm))
    return [0,ans]
  if ab==1:
    if cd==4 or cd==7:
      ans=abs(m-d)
      d=m
      return [1,ans,[a,b,c,d]]
    if cd==2 or cd==3:
      ans=abs(m-c)
      c=m
      return [1,ans,[a,b,c,d]]
  if ab==2 and cd==3:
    a-=m
    c-=m
    ans=abs(m-c)
    c=m
    return [1,ans,[a,b,c,d]]
  if ab==3 and (cd==6 or cd==9):
    a-=2*m
    c-=2*m
    ans=abs(m-d)
    d=m
    return [1,ans,[a,b,c,d]]
  if ab==4 and cd==7:
    b-=m
    d-=m
    ans=abs(m-d)
    d=m
    return [1,ans,[a,b,c,d]]
  if ab==6 and cd==9:
    a-=2*m
    c-=2*m
    b-=m
    d-=m
    ans=abs(m-d)
    d=m
    return [1,ans,[a,b,c,d]]
  if ab==7 and (cd==8 or cd==9):
    b-=2*m
    d-=2*m
    ans=abs(m-c)
    c=m
    return [1,ans,[a,b,c,d]]
  if ab==8 and cd==9:
    a-=m
    c-=m
    b-=2*m
    d-=2*m
    ans=abs(m-c)
    c=m
    return [1,ans,[a,b,c,d]]
  ans=abs(a-c)+abs(b-d)
  return [0,ans]

def solve(aa,bb,cc,dd):
  a,b,c,d=aa,bb,cc,dd
  ans=0
  for lv in range(30,0,-1):
    re=solve2(a,b,c,d,lv)
    if re[0]==2:
      a,b,c,d=re[1]
    if re[0]==1:
      ans+=re[1]
      a,b,c,d=re[2]
    if re[0]==0:
      return ans+re[1]
  return ans+abs(a-c)+abs(b-d)

q=int(input())
for _ in range(q):
  a,b,c,d=map(int,input().split())
  print(solve(a,b,c,d))

Submission status: Wrong Answer

Solution code:

def solve2(aa,bb,cc,dd,lv):
  a,b,c,d=aa,bb,cc,dd
  m=3**(lv-1)
  mm=2*m+1
  ab=3*((0--b//m)-1)+(0--a//m)
  cd=3*((0--d//m)-1)+(0--c//m)
  if ab==5 or cd==5:a=1/0
  if ab>cd:
    ab,cd=cd,ab
    a,b,c,d=c,d,a,b
  if ab==cd:
    mx=m*((0--a//m)-1)
    my=m*((0--b//m)-1)
    a-=mx
    b-=my
    c-=mx
    d-=my
    return [2,[a,b,c,d]]
  if ab==2 and cd==8:
    ans=abs(b-d)+min(abs(a-m)+abs(c-m),abs(a-(mm+1))+abs(c-(mm+1)))
    return [0,ans]
  if ab==4 and cd==6:
    ans=abs(a-c)+min(abs(b-m)+abs(d-m),abs(b-(mm+1))+abs(d-(mm+1)))
    return [0,ans]
  if ab==1:
    if cd==4 or cd==7:
      ans=abs(m-d)
      d=m
      return [1,ans,[a,b,c,d]]
    if cd==2 or cd==3:
      ans=abs(m-c)
      c=m
      return [1,ans,[a,b,c,d]]
  if ab==2 and cd==3:
    a-=m
    c-=m
    ans=abs(m-c)
    c=m
    return [1,ans,[a,b,c,d]]
  if ab==3 and (cd==6 or cd==9):
    a-=2*m
    c-=2*m
    ans=abs(m-d)
    d=m
    return [1,ans,[a,b,c,d]]
  if ab==4 and cd==7:
    b-=m
    d-=m
    ans=abs(m-d)
    d=m
    return [1,ans,[a,b,c,d]]
  if ab==6 and cd==9:
    a-=2*m
    c-=2*m
    b-=m
    d-=m
    ans=abs(m-d)
    d=m
    return [1,ans,[a,b,c,d]]
  if ab==7 and (cd==8 or cd==9):
    b-=2*m
    d-=2*m
    ans=abs(m-c)
    c=m
    return [1,ans,[a,b,c,d]]
  if ab==8 and cd==9:
    a-=m
    c-=m
    b-=2*m
    d-=2*m
    ans=abs(m-c)
    c=m
    return [1,ans,[a,b,c,d]]
  ans=abs(a-c)+abs(b-d)
  return [0,ans]

def solve(aa,bb,cc,dd):
  a,b,c,d=aa,bb,cc,dd
  ans=0
  for lv in range(30,0,-1):
    re=solve2(a,b,c,d,lv)
    if re[0]==2:
      a,b,c,d=re[1]
    if re[0]==1:
      ans+=re[1]
      a,b,c,d=re[2]
    if re[0]==0:
      return ans+re[1]
  return ans+abs(a-c)+abs(b-d)

q=int(input())
for _ in range(q):
  a,b,c,d=map(int,input().split())
  print(solve(a,b,c,d))

Submission status: Wrong Answer

Solution code:

def solve2(aa,bb,cc,dd,lv):
  a,b,c,d=aa,bb,cc,dd
  m=3**(lv-1)
  mm=2*m
  ab=3*((0--b//m)-1)+(0--a//m)
  cd=3*((0--d//m)-1)+(0--c//m)
  if ab>cd:
    ab,cd=cd,ab
    a,b,c,d=c,d,a,b
  if ab==cd:
    mx=m*((0--a//m)-1)
    my=m*((0--b//m)-1)
    a-=mx
    b-=my
    c-=mx
    d-=my
    return [2,[a,b,c,d]]
  if ab==2 and cd==8:
    ans=abs(b-d)+min(abs(a-m)+abs(c-m),abs(a-(mm+1))+abs(c-(mm+1)))
    return [0,ans]
  if ab==4 and cd==6:
    ans=abs(a-c)+min(abs(b-m)+abs(d-m),abs(b-(mm+1))+abs(d-(mm+1)))
    return [0,ans]
  if ab==1:
    if cd==4 or cd==7:
      ans=abs(m-d)
      d=m
      return [1,ans,[a,b,c,d]]
    if cd==2 or cd==3:
      ans=abs(m-c)
      c=m
      return [1,ans,[a,b,c,d]]
  if ab==2 and cd==3:
    a-=m
    c-=m
    ans=abs(m-c)
    c=m
    return [1,ans,[a,b,c,d]]
  if ab==3 and (cd==6 or cd==9):
    a-=mm
    c-=mm
    ans=abs(m-d)
    d=m
    return [1,ans,[a,b,c,d]]
  if ab==4 and cd==7:
    b-=m
    d-=m
    ans=abs(m-d)
    d=m
    return [1,ans,[a,b,c,d]]
  if ab==6 and cd==9:
    a-=mm
    c-=mm
    b-=m
    d-=m
    ans=abs(m-d)
    d=m
    return [1,ans,[a,b,c,d]]
  if ab==7 and (cd==8 or cd==9):
    b-=mm
    d-=mm
    ans=abs(m-c)
    c=m
    return [1,ans,[a,b,c,d]]
  if ab==8 and cd==9:
    a-=m
    c-=m
    b-=mm
    d-=mm
    ans=abs(m-c)
    c=m
    return [1,ans,[a,b,c,d]]
  ans=abs(a-c)+abs(b-d)
  return [0,ans]

def solve(aa,bb,cc,dd):
  a,b,c,d=aa,bb,cc,dd
  ans=0
  for lv in range(30,0,-1):
    re=solve2(a,b,c,d,lv)
    if re[0]==2:
      a,b,c,d=re[1]
    if re[0]==1:
      ans+=re[1]
      a,b,c,d=re[2]
    if re[0]==0:
      return ans+re[1]
  return ans+abs(a-c)+abs(b-d)

q=int(input())
for _ in range(q):
  a,b,c,d=map(int,input().split())
  print(solve(a,b,c,d))