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:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


q = int(input())
def _sub(a):
    v = []
    for i in range(35):
        a,val = divmod(a,3)
        v.append(val)
    return v
def sub(a,b,c,d):
    va,vb,vc,vd = _sub(a), _sub(b), _sub(c), _sub(d)
    ans = 0
    m1 = True
    m2 = True
    for i in reversed(range(35)):
        aa,bb,cc,dd = va[i],vb[i],vc[i],vd[i]
#         print(aa,bb,cc,dd,m1,m2,i)
        if aa==cc==1 and m1 and ((m2 and bb!=dd) or (not m2 and abs(b-d)>pow(3,i))):
            ta = a % pow(3,i)
            tc = c % pow(3,i)
            ans = abs(b-d) + min(ta+tc+2, 2*pow(3,i)-(ta+tc))
            break
        elif bb==dd==1 and m2 and ((m1 and aa!=cc) or (not m1 and abs(a-c)>pow(3,i))):
            tb = b % pow(3,i)
            td = d % pow(3,i)
            ans = abs(a-c) + min(tb+td+2, 2*pow(3,i)-(tb+td))
            break
        else:
            if aa!=cc:
                m1 = False
            if bb!=dd:
                m2 = False
    else:
        ans = abs(a-c) + abs(b-d)
    return ans
ans = [None]*q
for i in range(q):
    a,b,c,d = list(map(lambda x: int(x)-1, input().split()))
    ans[i] = sub(a,b,c,d)
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


q = int(input())
def _sub(a):
    v = []
    for i in range(35):
        a,val = divmod(a,3)
        v.append(val)
    return v
def sub(a,b,c,d):
    va,vb,vc,vd = _sub(a), _sub(b), _sub(c), _sub(d)
    ans = 0
    m1 = True
    m2 = True
    for i in reversed(range(35)):
        aa,bb,cc,dd = va[i],vb[i],vc[i],vd[i]
        if aa==cc==1 and (bb!=dd or not m2) and m1:
            ta = a % pow(3,i)
            tc = c % pow(3,i)
            ans = abs(b-d) + min(ta+tc+2, 2*pow(3,i)-(ta+tc))
            break
        elif bb==dd==1 and (aa!=cc or not m1) and m2:
            tb = b % pow(3,i)
            td = d % pow(3,i)
            ans = abs(a-c) + min(tb+td+2, 2*pow(3,i)-(tb+td))
            break
        else:
            if aa!=cc:
                m1 = False
            if bb!=dd:
                m2 = False
    else:
        ans = abs(a-c) + abs(b-d)
    return ans
ans = [None]*q
for i in range(q):
    a,b,c,d = list(map(lambda x: int(x)-1, input().split()))
    ans[i] = sub(a,b,c,d)
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


q = int(input())
def _sub(a):
    v = []
    for i in range(35):
        a,val = divmod(a,3)
        v.append(val)
    return v
def sub(a,b,c,d):
    va,vb,vc,vd = _sub(a), _sub(b), _sub(c), _sub(d)
    ans = 0
    m1 = True
    m2 = True
    for i in reversed(range(35)):
        aa,bb,cc,dd = va[i],vb[i],vc[i],vd[i]
        if aa==cc==1 and bb!=dd and m1:
            ta = a % pow(3,i)
            tc = c % pow(3,i)
            ans = abs(b-d) + min(ta+tc+2, 2*pow(3,i)-(ta+tc))
            break
        elif bb==dd==1 and aa!=cc and m2:
            tb = b % pow(3,i)
            td = d % pow(3,i)
            ans = abs(a-c) + min(tb+td+2, 2*pow(3,i)-(tb+td))
            break
        else:
            if aa!=cc:
                m1 = False
            if bb!=dd:
                m2 = False
    else:
        ans = abs(a-c) + abs(b-d)
    return ans
ans = [None]*q
for i in range(q):
    a,b,c,d = list(map(lambda x: int(x)-1, input().split()))
    ans[i] = sub(a,b,c,d)
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


q = int(input())
def _sub(a):
    v = []
    for i in range(35):
        a,val = divmod(a,3)
        v.append(val)
    return v
def sub(a,b,c,d):
    va,vb,vc,vd = _sub(a), _sub(b), _sub(c), _sub(d)
    ans = 0
    m1 = True
    m2 = True
    for i in reversed(range(35)):
        aa,bb,cc,dd = va[i],vb[i],vc[i],vd[i]
        if aa==cc==1 and m1:
            ta = a % pow(3,i)
            tc = c % pow(3,i)
            ans = abs(b-d) + min(ta+tc+2, 2*pow(3,i)-(ta+tc))
            break
        elif bb==dd==1 and m2:
            tb = b % pow(3,i)
            td = d % pow(3,i)
            ans = abs(a-c) + min(tb+td+2, 2*pow(3,i)-(tb+td))
            break
        else:
            if aa!=cc:
                m1 = False
            if bb!=dd:
                m2 = False
    else:
        ans = abs(a-c) + abs(b-d)
    return ans
ans = [None]*q
for i in range(q):
    a,b,c,d = list(map(lambda x: int(x)-1, input().split()))
    ans[i] = sub(a,b,c,d)
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


q = int(input())
def _sub(a):
    v = []
    for i in range(30):
        a,val = divmod(a,3)
        v.append(val)
    return v
def sub(a,b,c,d):
    va,vb,vc,vd = _sub(a), _sub(b), _sub(c), _sub(d)
    ans = 0
    m1 = True
    m2 = True
    for i in reversed(range(30)):
        aa,bb,cc,dd = va[i],vb[i],vc[i],vd[i]
        if aa==cc==1 and m1:
            ta = a % pow(3,i)
            tc = c % pow(3,i)
            ans = abs(b-d) + min(ta+tc+2, 2*pow(3,i)-(ta+tc))
            break
        elif bb==dd==1 and m2:
            tb = b % pow(3,i)
            td = d % pow(3,i)
            ans = abs(a-c) + min(tb+td+2, 2*pow(3,i)-(tb+td))
            break
        else:
            if aa!=cc:
                m1 = False
            if bb!=dd:
                m2 = False
    else:
        ans = abs(a-c) + abs(b-d)
    return ans
ans = [None]*q
for i in range(q):
    a,b,c,d = list(map(lambda x: int(x)-1, input().split()))
    ans[i] = sub(a,b,c,d)
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


q = int(input())
def _sub(a):
    v = []
    for i in range(30):
        a,val = divmod(a,3)
        v.append(val)
    return v
def sub(a,b,c,d):
    va,vb,vc,vd = _sub(a), _sub(b), _sub(c), _sub(d)
    ans = 0
    for i in reversed(range(30)):
        aa,bb,cc,dd = va[i],vb[i],vc[i],vd[i]
        if aa==cc==1:
            ta = a % pow(3,i)
            tc = c % pow(3,i)
            ans = abs(b-d) + min(ta+tc+2, 2*pow(3,i)-(ta+tc))
            break
        elif bb==dd==1:
            tb = b % pow(3,i)
            td = d % pow(3,i)
            ans = abs(a-c) + min(tb+td+2, 2*pow(3,i)-(tb+td))
            break
    else:
        ans = abs(a-c) + abs(b-d)
    return ans
ans = [None]*q
for i in range(q):
    a,b,c,d = list(map(lambda x: int(x)-1, input().split()))
    ans[i] = sub(a,b,c,d)
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


q = int(input())
def sub(a,b,c,d,level=30):
    base = pow(3, level-1)
    aa,bb,cc,dd = a//base, b//base, c//base, d//base
#     print((aa,bb), (cc,dd), base)
    if (aa,bb)==(cc,dd):
        return sub(a%base, b%base, c%base, d%base, level=level-1)
    else:
        if ((aa,bb)==(0,1) and (cc,dd)==(2,1)) or ((aa,bb)==(2,1) and (cc,dd)==(0,1)):
            ans = min(b%base+d%base+2, base*2-(b%base+d%base)) + abs(a-c)
        elif ((aa,bb)==(1,0) and (cc,dd)==(1,2)) or ((aa,bb)==(1,2) and (cc,dd)==(1,0)):
            ans = min(a%base+c%base+2, base*2-(a%base+c%base)) + abs(b-d)
        else:
            ans =  abs(a-c) + abs(b-d)
        return ans
ans = [None]*q
for i in range(q):
    a,b,c,d = list(map(lambda x: int(x)-1, input().split()))
    ans[i] = sub(a,b,c,d)
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math
Q = int(input())
A = [list(map(int, input().split())) for _ in range(Q)]



def measure(A):
    a,b,c,d = A
    if abs(a-c) < abs(b-d):
        s1, s2 = min([a,c]), max([a,c])
        l1, l2 = min([b,d]), max([b,d])
    else:
        l1, l2 = min([a,c]), max([a,c])
        s1, s2 = min([b,d]), max([b,d])
    min_K = int(math.log(s2-s1+1, 3) + 1)
    max_K = int(math.log(l2-l1+1, 3) + 1)
    for k in list(range(min_K, max_K+1))[::-1]:
        v = 3 ** k
        _l = 3 ** (k-1) + 1
        _h = (3 ** (k-1)) * 2
        c1 = s1//v == s2//v
        c2 = (s1 % v <= _h) & (_l <= s1 % v)
        c3 = (s2 % v <= _h) & (_l <= s2 % v)
        c4 = True
        if ((l1 // v) + 1) == (l2 // v):
            if ((l2 % v < _l) & (l1 % v > _h)):
                c4 = False
        if c1 & c2 & c3 & c4:
            val1 = (s1 % v - _l + 1) + (s2 % v - _l + 1) + (l2 - l1)
            val2 = (_h - s1 % v + 1) + (_h - s2 % v + 1) + (l2 - l1)
            print(min([val1, val2]))
            return None
    print(l2-l1+s2-s1)

if __name__ == '__main__':
    for val in A:
        measure(val)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math
Q = int(input())
A = [list(map(int, input().split())) for _ in range(Q)]



def measure(A):
    a,b,c,d = A
    if abs(a-c) < abs(b-d):
        s1, s2 = min([a,c]), max([a,c])
        l1, l2 = min([b,d]), max([b,d])
    else:
        l1, l2 = min([a,c]), max([a,c])
        s1, s2 = min([b,d]), max([b,d])
    min_K = int(math.log(s2-s1+1, 3) + 1)
    max_K = int(math.log(l2-l1+1, 3) + 1)
    for k in list(range(min_K, max_K+1))[::-1]:
        v = 3 ** k
        _l = 3 ** (k-1) + 1
        _h = (3 ** (k-1)) * 2
        c1 = s1//v == s2//v
        c2 = (s1 % v <= _h) & (_l <= s1 % v)
        c3 = (s2 % v <= _h) & (_l <= s2 % v)
        c4 = True
        if ((l1-1 // v) + 1) == (l2-1 // v):
            if ((l2 % v < _l) & (l1 % v > _h)):
                c4 = False
        if c1 & c2 & c3 & c4:
            val1 = (s1 % v - _l + 1) + (s2 % v - _l + 1) + (l2 - l1)
            val2 = (_h - s1 % v + 1) + (_h - s2 % v + 1) + (l2 - l1)
            print(min([val1, val2]))
            return None
    print(l2-l1+s2-s1)

if __name__ == '__main__':
    for val in A:
        measure(val)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math
Q = int(input())
A = [list(map(int, input().split())) for _ in range(Q)]



def measure(A):
    a,b,c,d = A
    if abs(a-c) < abs(b-d):
        s1, s2 = min([a,c]), max([a,c])
        l1, l2 = min([b,d]), max([b,d])
    else:
        l1, l2 = min([a,c]), max([a,c])
        s1, s2 = min([b,d]), max([b,d])
    min_K = int(math.log(s2-s1+1, 3) + 1)
    max_K = int(math.log(l2-l1+1, 3) + 1)
    for k in list(range(min_K, max_K+1))[::-1]:
        v = 3 ** k
        _l = 3 ** (k-1) + 1
        _h = (3 ** (k-1)) * 2
        c1 = s1//v == s2//v
        c2 = (s1 % v <= _h) & (_l <= s1 % v)
        c3 = (s2 % v <= _h) & (_l <= s2 % v)
        c4 = True
        if ((l1 // v) + 1) == (l2-1 // v):
            c4 = not ((l2 % v < _l) & (l1 % v > _h))
        if c1 & c2 & c3 & c4:
            val1 = (s1 % v - _l + 1) + (s2 % v - _l + 1) + (l2 - l1)
            val2 = (_h - s1 % v + 1) + (_h - s2 % v + 1) + (l2 - l1)
            print(min([val1, val2]))
            return None
    print(l2-l1+s2-s1)

if __name__ == '__main__':
    for val in A:
        measure(val)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math
Q = int(input())
A = [list(map(int, input().split())) for _ in range(Q)]



def measure(A):
    a,b,c,d = A
    if abs(a-c) < abs(b-d):
        s1, s2 = min([a,c]), max([a,c])
        l1, l2 = min([b,d]), max([b,d])
    else:
        l1, l2 = min([a,c]), max([a,c])
        s1, s2 = min([b,d]), max([b,d])
    min_K = int(math.log(s2-s1+1, 3) + 1)
    max_K = int(math.log(l2-l1+1, 3) + 1)
    for k in list(range(min_K, max_K+1))[::-1]:
        v = 3 ** k
        _l = 3 ** (k-1) + 1
        _h = (3 ** (k-1)) * 2
        c1 = s1//v == s2//v
        c2 = (s1 % v <= _h) & (_l <= s1 % v)
        c3 = (s2 % v <= _h) & (_l <= s2 % v)
        c4 = True
        if ((l1 // v) + 1) == (l2 // v):
            c4 = not ((l2 % v > _h) & (l1 % v < _l))
        if c1 & c2 & c3 & c4:
            val1 = (s1 % v - _l + 1) + (s2 % v - _l + 1) + (l2 - l1)
            val2 = (_h - s1 % v + 1) + (_h - s2 % v + 1) + (l2 - l1)
            print(min([val1, val2]))
            return None
    print(l2-l1+s2-s1)

if __name__ == '__main__':
    for val in A:
        measure(val)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math
Q = int(input())
A = [list(map(int, input().split())) for _ in range(Q)]



def measure(A):
    a,b,c,d = A
    if abs(a-c) < abs(b-d):
        s1, s2 = min([a,c]), max([a,c])
        l1, l2 = min([b,d]), max([b,d])
    else:
        l1, l2 = min([a,c]), max([a,c])
        s1, s2 = min([b,d]), max([b,d])
    min_K = int(math.log(s2-s1+1, 3) + 1)
    max_K = int(math.log(l2-l1+1, 3) + 1)
    for k in list(range(min_K, max_K+1))[::-1]:
        v = 3 ** k
        _l = 3 ** (k-1) + 1
        _h = (3 ** (k-1)) * 2
        c1 = s1//v == s2//v
        c2 = (s1 % v <= _h) & (_l <= s1 % v)
        c3 = (s2 % v <= _h) & (_l <= s2 % v)
        if c1 & c2 & c3:
            val1 = (s1 % v - _l + 1) + (s2 % v - _l + 1) + (l2 - l1)
            val2 = (_h - s1 % v + 1) + (_h - s2 % v + 1) + (l2 - l1)
            print(min([val1, val2]))
            return None
    print(l2-l1+s2-s1)

if __name__ == '__main__':
    for val in A:
        measure(val)

Submission status: Wrong Answer

Solution code:
Q=int(input())
Query=[tuple(map(int,input().split())) for i in range(Q)]

B=[(3,2)]
for i in range(2,31):
    B.append((3**i,B[-1][1]+3**(i-1)))

for a,b,c,d in Query:
    MINX=min(a,c)
    MAXX=max(a,c)
    MINY=min(b,d)
    MAXY=max(b,d)
    flag=0
    
    for i in range(2,-1,-1):
        r,q=B[i]
        l=3**i

        xq=-(-(MINX-q)//r)*r+q
        yq=-(-(MINY-q)//r)*r+q

        #print(xq,yq,MINX,xq-l//2,xq+l//2,MAXX,MINY,yq-l//2,yq+l//2,MAXY)

        if (MINX<xq-l//2 and xq+l//2<MAXX) and (yq-l//2<=MINY and MAXY<=yq+l//2):
            #print(xq,yq,l)
            flag=1
            break
        
        if (xq-l//2<=MINX and MAXX<=xq+l//2) and (MINY<yq-l//2 and yq+l//2<MAXY):
            #print(xq,yq,l)
            flag=2
            break

    if flag==0:
        print(MAXX-MINX+MAXY-MINY)

    elif flag==1:
        ANS=MAXX-MINX
        y1=yq+l//2+1
        y2=yq-l//2-1

        ANS+=min(abs(y1-b)+abs(y1-d),abs(y2-b)+abs(y2-d))

        print(ANS)

    else:
        ANS=MAXY-MINY
        x1=xq+l//2+1
        x2=xq-l//2-1

        ANS+=min(abs(x1-a)+abs(x1-c),abs(x2-a)+abs(x2-c))

        print(ANS)

Submission status: Wrong Answer

Solution code:
Q = int(input())
for _ in [0]*Q:
    A,B,C,D = map(lambda x: int(x)-1,input().split())
    black = 0
    ab = 0
    e = 1
    for k in range(32):
        a,b,c,d = A//e,B//e,C//e,D//e
        if a==c and b==d:
            break
        elif a==c:
            ab = 1
            if a%3==1:
                black = max(black,e)
        elif b==d:
            ab = 2
            if b%3==1:
                black = max(black,e)
        e *= 3

    e //= 3
    a,b,c,d = A//e,B//e,C//e,D//e
    if black == 0:
        ans = abs(A-C)+abs(B-D)
    elif ab==1:
        ans = abs(B-D)
        F = A//black*black-1
        G = F+black+1
        ans += min(abs(A-F)+abs(C-F),abs(A-G)+abs(C-G))
        pass
    else:
        ans = abs(A-C)
        F = B//black*black-1
        G = F+black+1
        ans += min(abs(B-F)+abs(D-F),abs(B-G)+abs(D-G))
        pass
    print(ans)

Submission status: Wrong Answer

Solution code:
Q = int(input())
for _ in [0]*Q:
    A,B,C,D = map(lambda x: int(x)-1,input().split())
    black = 0
    ab = 0
    e = 1
    for k in range(31):
        a,b,c,d = A//e,B//e,C//e,D//e
        if a==c and b==d:
            break
        elif a==c:
            ab = 1
            if a%3==1:
                black = max(black,e)
        elif b==d:
            ab = 2
            if b%3==1:
                black = max(black,e)
        e *= 3

    e //= 3
    a,b,c,d = A//e,B//e,C//e,D//e
    if black == 0:
        ans = abs(A-C)+abs(B-D)
    elif ab==1:
        ans = abs(B-D)
        F = A//black*black-1
        G = F+black+1
        ans += min(abs(A-F)+abs(C-F),abs(A-G)+abs(C-G))
        pass
    else:
        ans = abs(A-C)
        F = B//black*black-1
        G = F+black+1
        ans += min(abs(B-F)+abs(D-F),abs(B-G)+abs(D-G))
        pass
    print(ans)

Submission status: Wrong Answer

Solution code:
def solve(A,B,C,D, level):
    E = 3**level
    if level == -1:
        return int(abs(A-C) + abs(B-D))
    a,b,c,d = A//E, B//E, C//E, D//E
    if a != c and b != d:
        return int(abs(A-C) + abs(B-D))

    if a == c and b==d:
        return solve(A,B,C,D,level-1)

    if a != c and b==d:
        A,B,C,D = B,A,D,C
        a,b,c,d = b,a,d,c

    if b != d and a == c:
        if a%3 != 1:
            return solve(A,B,C,D,level-1)
        if abs(b-d) == 1:
            return solve(A,B,C,D,level-1)

        if B > D:
            A, B, C, D = C, D, A, B
            a, b, c, d = c, d, a, b

        x = E * a -1
        y1 = E * (b+1) -1
        y2 = E * d
        print(level)
        d = abs(x-A) + abs(y1-B) + abs(y1-y2) + abs(x-C) + abs(y2-D)
        x = E *(a+1)
        d2 = abs(x-A) + abs(y1-B) + abs(y1-y2) + abs(x-C) + abs(y2-D)
        return min(d,d2)

N = int(input())

for i in range(N):
    sg = [int(j.strip())  for j in input().split(' ')]
    s,g = [sg[0]-1,sg[1]-1],[sg[2]-1,sg[3]-1]
    A,B,C,D = s[0],s[1],g[0],g[1]
    print(solve(A,B,C,D,30))

Submission status: Wrong Answer

Solution code:
def solve(A,B,C,D, level):
    E = 3**level
    if level == 0:
        return int(abs(A-C) + abs(B-D))
    a,b,c,d = A//E, B//E, C//E, D//E
    if a != c and b != d:
        return int(abs(A-C) + abs(B-D))

    if a == c and b==d:
        return solve(A,B,C,D,level-1)

    if a != c and b==d:
        A,B,C,D = B,A,D,C
        a,b,c,d = b,a,d,c

    if b != d and a == c:
        if a%3 != 1:
            return solve(A,B,C,D,level-1)
        if abs(b-d) == 1:
            return solve(A,B,C,D,level-1)

        if B > D:
            A, B, C, D = C, D, A, B
            a, b, c, d = c, d, a, b

        x = E * a -1
        y1 = E * (b+1) -1
        y2 = E * d
        d = abs(x-A) + abs(y1-B) + abs(y1-y2) + abs(x-C) + abs(y2-D)
        x = E *(a+1)
        d2 = abs(x-A) + abs(y1-B) + abs(y1-y2) + abs(x-C) + abs(y2-D)
        return min(d,d2)

N = int(input())

for i in range(N):
    sg = [int(j.strip())  for j in input().split(' ')]
    s,g = [sg[0]-1,sg[1]-1],[sg[2]-1,sg[3]-1]
    A,B,C,D = s[0],s[1],g[0],g[1]
    print(solve(A,B,C,D,30))

Submission status: Wrong Answer

Solution code:
def solve(A,B,C,D, level):
    if A != int:
        print('level' +str(level))
    E = 3**level
    if level == 0:
        return int(abs(A-C) + abs(B-D))
    a,b,c,d = A//E, B//E, C//E, D//E
    if a != c and b != d:
        return int(abs(A-C) + abs(B-D))

    if a == c and b==d:
        return solve(A,B,C,D,level-1)

    if a != c and b==d:
        A,B,C,D = B,A,D,C
        a,b,c,d = b,a,d,c

    if b != d and a == c:
        if a%3 != 1:
            return solve(A,B,C,D,level-1)
        if abs(b-d) == 1:
            return solve(A,B,C,D,level-1)

        if B > D:
            A, B, C, D = C, D, A, B
            a, b, c, d = c, d, a, b

        x = E * a -1
        y1 = E * (b+1) -1
        y2 = E * d
        print(abs(x-A),abs(y1-B),abs(y1-y2),abs(x-C),abs(y2-D))
        d = abs(x-A) + abs(y1-B) + abs(y1-y2) + abs(x-C) + abs(y2-D)
        x = E *(a+1)
        d2 = abs(x-A) + abs(y1-B) + abs(y1-y2) + abs(x-C) + abs(y2-D)
        return min(d,d2)

N = int(input())

for i in range(N):
    sg = [int(j.strip())  for j in input().split(' ')]
    s,g = [sg[0]-1,sg[1]-1],[sg[2]-1,sg[3]-1]
    A,B,C,D = s[0],s[1],g[0],g[1]
    print(solve(A,B,C,D,30))

Submission status: Wrong Answer

Solution code:
def solve(A,B,C,D, level):
    E = 3**level
    if not E:
        return abs(A-C) + abs(B-D)
    a,b,c,d = A//E, B//E, C//E, D//E
    if a != c and b != d:
        return abs(A-C) + abs(B-D)

    if a == c and b==d:
        return solve(A,B,C,D,level-1)

    if a != c and b==d:
        A,B,C,D = B,A,D,C
        a,b,c,d = b,a,d,c

    if b != d and a == c:
        if a%3 != 1:
            return solve(A,B,C,D,level-1)
        if abs(b-d) == 1:
            return solve(A,B,C,D,level-1)

        if B > D:
            A, B, C, D = C, D, A, B
            a, b, c, d = c, d, a, b

        x = E * a -1
        y1 = E * (b+1) -1
        y2 = E * d
        d = abs(x-A) + abs(y1-B) + abs(y1-y2) + abs(x-C) + abs(y2-D)
        x = E *(a+1)
        d2 = abs(x-A) + abs(y1-B) + abs(y1-y2) + abs(x-C) + abs(y2-D)
        return min(d,d2)

N = int(input())

for i in range(N):
    sg = [int(j.strip())  for j in input().split(' ')]
    s,g = [sg[0]-1,sg[1]-1],[sg[2]-1,sg[3]-1]
    A,B,C,D = s[0],s[1],g[0],g[1]
    print(solve(A,B,C,D,30))

Submission status: Wrong Answer

Solution code:
def check_4628(s,g,lev):
    width = 3**lev
    middle = 3**(lev-1)
    a = s[0] % width
    b = s[1] % width
    c = g[0] % width
    d = g[1] % width
    flg = 0
    # print(middle)

    if int(s[0]/middle) == int(g[0]/middle) and int(g[0]/middle)/3 == 1:
        if int(s[1]/middle) != int(g[1]/middle):
            flg =1
            n1,m1 = a % middle+1, c % middle+1
            n2, m2 = 2 * middle -a, 2 * middle - c
            detour = n1+m1 if n1+m1 < n2+m2 else n2+m2
            return abs(s[1]-g[1]) + detour

    elif int(s[0]/middle) == int(g[0]/middle) and int(g[0]/middle)/3 == 1:
        # print(int(g[0]/middle),int(s[0]/middle))
        if int(s[0]/middle) != int(g[0]/middle):
            flg =1
            n1,m1 = b % middle+1, d % middle+1
            n2, m2 = 2 * middle -b, 2 * middle - d
            detour = n1+m1 if n1+m1 < n2+m2 else n2+m2
            # print(lev)
            # print(detour)
            # print('aaa')
            return abs(s[0]-g[0]) + detour

    if flg == 0:
        return 0

N = int(input())

for i in range(N):
    sg = [int(j.strip())  for j in input().split(' ')]
    s,g = [sg[0]-1,sg[1]-1],[sg[2]-1,sg[3]-1]
    # print(s,g)
    for i in range(30,-1,-1):
        if i == 0:
            print(abs(s[0]-g[0]) + abs(s[1]-g[1]))
            break
        a = check_4628(s,g,i)
        if a == 0:
            continue
        else:
            print(a)
            break

Submission status: Wrong Answer

Solution code:
def check_4628(s,g,lev):
    width = 3**lev
    middle = 3**(lev-1)
    a = s[0] % width
    b = s[1] % width
    c = g[0] % width
    d = g[1] % width
    flg = 0

    if middle <= a and a < 2*middle and middle <= c and c < 2*middle:
        if int(s[1]/middle) != int(g[1]/middle):
            flg =1
            n1,m1 = a % middle+1, c % middle+1
            n2, m2 = 2 * middle -a, 2 * middle - c
            detour = n1+m1 if n1+m1 < n2+m2 else n2+m2
            return abs(s[1]-g[1]) + detour

    elif middle <= b and b < 2*middle and middle <= d and d < 2*middle:
        # print(int(g[0]/middle),int(s[0]/middle))
        if int(s[0]/middle) != int(g[0]/middle):
            flg =1
            n1,m1 = b % middle+1, d % middle+1
            n2, m2 = 2 * middle -b, 2 * middle - d
            detour = n1+m1 if n1+m1 < n2+m2 else n2+m2
            return abs(s[0]-g[0]) + detour

    if flg == 0:
        return 0

N = int(input())

for i in range(N):
    sg = [int(j.strip())  for j in input().split(' ')]
    s,g = [sg[0]-1,sg[1]-1],[sg[2]-1,sg[3]-1]
    print(check_4628(s,g,1))
    exit()
    for i in range(30,-1,-1):
        if i == 0:
            print(abs(s[0]-g[0]) + abs(s[1]-g[1]))
            break
        a = check_4628(s,g,i)
        if a == 0:
            continue
        else:
            print(a)
            break

Submission status: Wrong Answer

Solution code:
def check_4628(s,g,lev):
    width = 3**lev
    middle = 3**(lev-1)
    a = s[0] % width
    b = s[1] % width
    c = g[0] % width
    d = g[1] % width
    flg = 0

    if middle <= a and a < 2*middle and middle <= c and c < 2*middle:
        if (b <  middle and d >= 2*middle) or (b <  middle and d >= 2*middle):
            flg =1
            n1,m1 = a % middle+1, c % middle+1
            n2, m2 = 2 * middle -a, 2 * middle - c
            detour = n1+m1 if n1+m1 < n2+m2 else n2+m2
            return abs(s[1]-g[1]) + detour

    elif middle <= b and b < 2*middle and middle <= d and d < 2*middle:
        if (a <  middle and c >= 2*middle) or (c <  middle and a >= 2*middle):
            flg =1
            n1,m1 = b % middle+1, d % middle+1
            n2, m2 = 2 * middle -a, 2 * middle - c
            detour = n1+m1 if n1+m1 < n2+m2 else n2+m2
            return abs(s[0]-g[0]) + detour

    if flg == 0:
        return 0

N = int(input())

for i in range(N):
    sg = [int(j.strip())  for j in input().split(' ')]
    s,g = [sg[0]-1,sg[1]-1],[sg[2]-1,sg[3]-1]
    for i in range(30,-1,-1):
        if i == 0:
            print(abs(s[0]-g[0]) + abs(s[1]-g[1]))
            break
        a = check_4628(s,g,i)
        if a == 0:
            continue
        else:
            print(a)
            break

Submission status: Wrong Answer

Solution code:
def solve(a, b, c, d):
  for k in range(29, -1, -1):
    block_size = 3**k
    box_size = block_size * 3
    x1, y1, x2, y2 = map(lambda x:x//block_size, (a, b, c, d))
    x1, x2 = sorted([x1, x2])
    y1, y2 = sorted([y1, y2])
    if x1!=x2 and y1!=y2:
      return abs(a-c)+abs(b-d)
    if x1==x2 and x1%3==1 and (y1+1)//3*3+1<y2:
      a, c = map(lambda x:x%box_size, (a, c))
      return min(a+c-2*block_size+2, 4*block_size-a-c)+abs(b-d)
    elif y1==y2 and y1%3==1 and (x1+1)//3*3+1<x2:
      b, d = map(lambda x:x%box_size, (b, d))
      return min(b+d-2*block_size+2, 4*block_size-b-d)+abs(a-c)
  return abs(a-c)+abs(b-d)

for i in range(int(input())):
  print(solve(*map(int, input().split())))

Submission status: Wrong Answer

Solution code:
def solve(a, b, c, d):
  for k in range(29, -1, -1):
    block_size = 3**k
    box_size = block_size * 3
    x1, y1, x2, y2 = map(lambda x:x//block_size, (a, b, c, d))
    x1, x2 = sorted([x1, x2])
    y1, y2 = sorted([y1, y2])
    if x1!=x2 and y1!=y2:
      return abs(a-c)+abs(b-d)
    if x1==x2 and x1%box_size==1 and (y1+1)//3*3+1<y2:
      a, c = map(lambda x:x%box_size, (a, c))
      return min(a+c-2*block_size+2, 4*block_size-a-c)+abs(b-d)
    elif y1==y2 and y1%box_size==1 and (x1+1)//3*3+1<x2:
      b, d = map(lambda x:x%box_size, (b, d))
      return min(b+d-2*block_size+2, 4*block_size-b-d)+abs(a-c)
  return abs(a-c)+abs(b-d)

for i in range(int(input())):
  print(solve(*map(int, input().split())))

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
    if Y1 > Y2:
        Y1, Y2 = Y2, Y1
    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 == 1:
            # x1 と x2 の間に 1, 4, 7, ... があればそれ
            if x2 - x1 >= 2:
                while x1 % 3 != 1:
                    x1 += 1
                return x1 * size, y1 * size, size
        if x1 == x2 == 1:
            if y2 - y1 >= 2:
                while y1 % 3 != 1:
                    y1 += 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))
    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:
q = int(input())

def dec_to_3(x):
    ret = [0] * 30
    for i in range(30):
        ret[i] = x % 3
        x = x // 3
    return ret

def d(x1,y1,x2,y2):
    ret = abs(y1 - y2)
    x1_3 = dec_to_3(x1)
    x2_3 = dec_to_3(x2)
    y1_3 = dec_to_3(y1)
    y2_3 = dec_to_3(y2)
    i = 29
    y_diff = False
    while i >= 0:
        if y1_3[i] != y2_3[i]:
            y_diff = True
        if x1_3[i] == 1 and x2_3[i] == 1 and y_diff:
            x1_res = x1 % (3 ** i)
            x2_res = x2 % (3 ** i)
            ret += min(x1_res + x2_res + 2, 2 * 3 ** i - x1_res - x2_res)
            break
        if x1_3[i] != x2_3[i]:
            ret += abs(x1 - x2)
            break
        i -= 1
    return ret

for _ in range(q):
    x1,y1,x2,y2 = (int(num) - 1 for num in input().split())
    print(max(d(x1,y1,x2,y2), d(y1,x1,y2,x2)))

Submission status: Wrong Answer

Solution code:
q = int(input())

def dec_to_3(x):
    ret = [0] * 30
    for i in range(30):
        ret[i] = x % 3
        x = x // 3
    return ret

def d(x1,y1,x2,y2):
    ret = abs(y1 - y2)
    x1_3 = dec_to_3(x1)
    x2_3 = dec_to_3(x2)
    i = 29
    while i >= 0:
        if x1_3[i] == 1 and x2_3[i] == 1:
            x1_res = x1 % (3 ** i)
            x2_res = x2 % (3 ** i)
            ret += min(x1_res + x2_res + 2, 2 * 3 ** i - x1_res - x2_res)
            break
        if x1_3[i] != x2_3[i]:
            ret += abs(x1 - x2)
            break
        i -= 1
    return ret

for _ in range(q):
    x1,y1,x2,y2 = (int(num) - 1 for num in input().split())
    print(max(d(x1,y1,x2,y2), d(y1,x1,y2,x2)))