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:
def dist(a,b,c,d,n):
    L=3**n
    area1=(a//L)*3+b//L
    if area1==2:
        b=L*3-b-1
        d=L*3-d-1
    if area1==3:
        a,b=b,a
        c,d=d,c
    if area1==5:
        a,b=L*3-b-1,a
        c,d=L*3-d-1,c
    if area1 in [6,7]:
        a=L*3-a-1
        c=L*3-c-1
    if area1==8:
        a,b=L*3-a-1,L*3-b-1
        c,d=L*3-c-1,L*3-d-1

    area1=(a//L)*3+b//L
    area2=(c//L)*3+d//L
    if area1>8 or area2>8:
        a=0
        while True:
            a+=1
    
    if n==1:
        if area1==1 and area2==7: return 4
        else: return abs(a-c)+abs(b-d)

    if area1>area2:
        a,b,c,d=c,d,a,b
        area1,area2=area2,area1

    if area1==area2:
        return dist(a%L,b%L,c%L,d%L,n-1)
        
    elif area1==0:
        if area2 in [5,7,8]:
            return abs(a-c)+abs(b-d)
        elif area2 in [3,6]:
            return dist(b,a,d,c,n)

        elif area2 in [1,2]:
            L=3**(n-1)
            a12=(a//L)*3+b//L
            a22=(c//L)*3+(d-3*area2*L)//L
            if a//L!=c//L:
                return abs(a-c)+abs(b-d)
            elif a//L==0:
                p=(d//L)-(b//L)
                if p==1: return dist(a,b-2*L,c,d-2*L,n)
                else: return dist(a,b%L,c,d-(p-2)*L,n)+(p-2)*L
            elif a//L==1:
                if area2==1 and a12==5 and a22==3:
                    return dist(a-L,b-2*L,c-L,d-2*L,n)
                else:
                    return min(a+c-2*(L-1),4*L-a-c)+abs(b-d)
            elif a//L==2: return dist(a-2*L,b,c-2*L,d,n)

        else: return 0

    elif area1==1:
        if area2 in [3,5,6,8]:
            return abs(a-c)+abs(b-d)
        elif area2==2:
            return dist(a,b-L,c,d-L,n)
        elif area2==7:
            return min(b+d-2*(L-1),(4*L)-b-d)+abs(a-c)
        else: return 0



for i in range(int(input())):
    a,b,c,d=map(int,input().split())
    print(dist(a-1,b-1,c-1,d-1,29))

Submission status: Wrong Answer

Solution code:
def dist(a,b,c,d,n):
    L=3**n
    area1=(a//L)*3+b//L
    if area1==2:
        b=L*3-b-1
        d=L*3-d-1
    if area1==3:
        a,b=b,a
        c,d=d,c
    if area1==5:
        a,b=L*3-b-1,a
        c,d=L*3-d-1,c
    if area1 in [6,7]:
        a=L*3-a-1
        c=L*3-c-1
    if area1==8:
        a,b=L*3-a-1,L*3-b-1
        c,d=L*3-c-1,L*3-d-1

    area1=(a//L)*3+b//L
    area2=(c//L)*3+d//L
    if area1>8 or area2>8:
        a=0
        while True:
            a+=1
    
    if n==1:
        if area1==1 and area2==7: return 4
        else: return abs(a-c)+abs(b-d)

    if area1>area2:
        a,b,c,d=c,d,a,b
        area1,area2=area2,area1

    if area1==area2:
        return dist(a%L,b%L,c%L,d%L,n-1)
    elif area1==0:
        if area2 in [5,7,8]:
            return abs(a-c)+abs(b-d)
        elif area2 in [3,6]:
            return dist(b,a,d,c,n)

        elif area2 in [1,2]:
            L=3**(n-1)
            a12=(a//L)*3+b//L
            a22=(c//L)*3+(d-3*area2*L)//L
            if a//L!=c//L:
                return abs(a-c)+abs(b-d)
            elif a//L==0:
                p=(d//L)-(b//L)
                if p==1: return dist(a,b-2*L,c,d-2*L,n-1)
                else: return dist(a,b%L,c,d-(p-2)*L,n-1)+(p-2)*L
            elif a//L==1:
                if area2==1 and a12==5 and a22==3:
                    return dist(a-L,b-2*L,c-L,d-2*L,n-1)
                else:
                    return min(a+c-2*(L-1),4*L-a-c)+abs(b-d)
            elif a//L==2: return dist(a-2*L,b,c-2*L,d,n)

        else: return 0

    elif area1==1:
        if area2 in [3,5,6,8]:
            return abs(a-c)+abs(b-d)
        elif area2==2:
            return dist(a,b-L,c,d-L,n)
        elif area2==7:
            return min(b+d-2*(L-1),(4*L)-b-d)+abs(a-c)
        else: return 0



for i in range(int(input())):
    a,b,c,d=map(int,input().split())
    print(dist(a-1,b-1,c-1,d-1,29))

Submission status: Wrong Answer

Solution code:
def dist(a,b,c,d,n):
    L=3**n
    area1=(a//L)*3+b//L
    if area1==2:
        b=L*3-b-1
        d=L*3-d-1
    if area1==3:
        a,b=b,a
        c,d=d,c
    if area1==5:
        a,b=L*3-b-1,a
        c,d=L*3-d-1,c
    if area1 in [6,7]:
        a=L*3-a-1
        c=L*3-c-1
    if area1==8:
        a,b=L*3-a-1,L*3-b-1
        c,d=L*3-c-1,L*3-d-1

    area1=(a//L)*3+b//L
    area2=(c//L)*3+d//L
    
    if n==1:
        if area1==1 and area2==7: return 4
        else: return abs(a-c)+abs(b-d)

    if area1>area2:
        a,b,c,d=c,d,a,b
        area1,area2=area2,area1

    if area1==area2:
        return dist(a%L,b%L,c%L,d%L,n-1)
    elif area1==0:
        if area2 in [5,7,8]:
            return abs(a-c)+abs(b-d)
        elif area2 in [3,6]:
            return dist(b,a,d,c,n)

        elif area2 in [1,2]:
            L=3**(n-1)
            a12=(a//L)*3+b//L
            a22=(c//L)*3+(d-3*area2*L)//L
            if a//L!=c//L:
                return abs(a-c)+abs(b-d)
            elif a//L==0:
                p=(d//L)-(b//L)
                if p==1: return dist(a,b-2*L,c,d-2*L,n-1)
                else: return dist(a,b%L,c,d-(p-2)*L,n-1)+(p-2)*L
            elif a//L==1:
                if area2==1 and a12==5 and a22==3:
                    return dist(a-L,b-2*L,c-L,d-2*L,n-1)
                else:
                    return min(a+c-2*(L-1),4*L-a-c)+abs(b-d)
            elif a//L==2: return dist(a-2*L,b,c-2*L,d,n)

        else: return 0

    elif area1==1:
        if area2 in [3,5,6,8]:
            return abs(a-c)+abs(b-d)
        elif area2==2:
            return dist(a,b-L,c,d-L,n)
        elif area2==7:
            return min(b+d-2*(L-1),(4*L)-b-d)+abs(a-c)
        else: return 0



for i in range(int(input())):
    a,b,c,d=map(int,input().split())
    print(dist(a-1,b-1,c-1,d-1,29))

Submission status: Wrong Answer

Solution code:
def dist(a,b,c,d,n):
    L=3**n
    area1=(a//L)*3+b//L
    if area1==2:
        b=L*3-b-1
        d=L*3-d-1
    if area1==3:
        a,b=b,a
        c,d=d,c
    if area1==5:
        a,b=L*3-b-1,a
        c,d=L*3-d-1,c
    if area1 in [6,7]:
        a=L*3-a-1
        c=L*3-c-1
    if area1==8:
        a,b=L*3-a-1,L*3-b-1
        c,d=L*3-c-1,L*3-d-1

    area1=(a//L)*3+b//L
    area2=(c//L)*3+d//L
    if area1>8 or area2>8:
        while True:
            a=1
    
    if n==1:
        if area1==1 and area2==7: return 4
        else: return abs(a-c)+abs(b-d)

    if area1>area2:
        a,b,c,d=c,d,a,b
        area1,area2=area2,area1

    if area1==area2:
        return dist(a%L,b%L,c%L,d%L,n-1)
    elif area1==0:
        if area2 in [5,7,8]:
            return abs(a-c)+abs(b-d)
        elif area2 in [3,6]:
            return dist(b,a,d,c,n)

        elif area2 in [1,2]:
            L=3**(n-1)
            a12=(a//L)*3+b//L
            a22=(c//L)*3+(d-3*area2*L)//L
            if a//L!=c//L:
                return abs(a-c)+abs(b-d)
            elif a//L==0:
                p=(d//L)-(b//L)
                if p==1: return dist(a,b-2*L,c,d-2*L,n-1)
                else: return dist(a,b%L,c,d-(p-2)*L,n-1)+(p-2)*L
            elif a//L==1:
                if area2==1 and a12==5 and a22==3:
                    return dist(a-L,b-2*L,c-L,d-2*L,n-1)
                else:
                    return min(a+c-2*(L-1),4*L-a-c)+abs(b-d)
            elif a//L==2: return dist(a-2*L,b,c-2*L,d,n)

        else: return 0

    elif area1==1:
        if area2 in [3,5,6,8]:
            return abs(a-c)+abs(b-d)
        elif area2==2:
            return dist(a,b-L,c,d-L,n)
        elif area2==7:
            return min(b+d-2*(L-1),(4*L)-b-d)+abs(a-c)
        else: return 0



for i in range(int(input())):
    a,b,c,d=map(int,input().split())
    print(dist(a-1,b-1,c-1,d-1,29))

Submission status: Wrong Answer

Solution code:
def dist(a,b,c,d,n):
    L=3**n
    area1=(a//L)*3+b//L
    if area1==2:
        b=L*3-b-1
        d=L*3-d-1
    if area1==3:
        a,b=b,a
        c,d=d,c
    if area1==5:
        a,b=L*3-b-1,a
        c,d=L*3-d-1,c
    if area1 in [6,7]:
        a=L*3-a-1
        c=L*3-c-1
    if area1==8:
        a,b=L*3-a-1,L*3-b-1
        c,d=L*3-c-1,L*3-d-1

    area1=(a//L)*3+b//L
    area2=(c//L)*3+d//L
    
    if n==1:
        if area1==1 and area2==7: return 4
        else: return abs(a-c)+abs(b-d)

    if area1>area2:
        a,b,c,d=c,d,a,b
        area1,area2=area2,area1

    if area1==area2:
        return dist(a%L,b%L,c%L,d%L,n-1)
    elif area1==0:
        if area2 in [5,7,8]:
            return abs(a-c)+abs(b-d)
        elif area2 in [3,6]:
            return dist(b,a,d,c,n)

        elif area2 in [1,2]:
            L=3**(n-1)
            a12=(a//L)*3+b//L
            a22=(c//L)*3+(d-3*area2*L)//L
            if a//L!=c//L:
                return abs(a-c)+abs(b-d)
            elif a//L==0: return dist(a,b%L,c,d-(d//L-b//L-2)*L,n-1)+(d//L-b//L)*L
            elif a//L==1:
                if area2==1 and a12==5 and a22==3:
                    return dist(a-L,b-2*L,c-L,d-2*L,n-1)
                else:
                    return min(a+c-2*(L-1),4*L-a-c)+abs(b-d)
            elif a//L==2: return dist(a-2*L,b,c-2*L,d,n)

        else: return 0

    elif area1==1:
        if area2 in [3,5,6,8]:
            return abs(a-c)+abs(b-d)
        elif area2==2:
            return dist(a,b-L,c,d-L,n)
        elif area2==7:
            return min(b+d-2*(L-1),(4*L)-b-d)+abs(a-c)
        else: return 0



for i in range(int(input())):
    a,b,c,d=map(int,input().split())
    print(dist(a-1,b-1,c-1,d-1,29))

Submission status: Wrong Answer

Solution code:
def dist(a,b,c,d,n):
    L=3**n
    area1=(a//L)*3+b//L
    if area1==2:
        b=L*3-b-1
        d=L*3-d-1
    if area1==3:
        a,b=b,a
        c,d=d,c
    if area1==5:
        a,b=L*3-b-1,a
        c,d=L*3-d-1,c
    if area1 in [6,7]:
        a=L*3-a-1
        c=L*3-c-1
    if area1==8:
        a,b=L*3-a-1,L*3-b-1
        c,d=L*3-c-1,L*3-d-1

    area1=(a//L)*3+b//L
    area2=(c//L)*3+d//L
    
    if n==1:
        if area1==1 and area2==7: return 4
        else: return abs(a-c)+abs(b-d)


    if area1>area2:
        a,b,c,d=c,d,a,b
        area1,area2=area2,area1

    if area1==area2:
        return dist(a%L,b%L,c%L,d%L,n-1)
    elif area1==0:
        if area2 in [5,7,8]:
            return abs(a-c)+abs(b-d)
        if area2 in [3,6]:
            return dist(b,a,d,c,n)

        if area2==1:
            L=3**(n-1)
            a12=(a//L)*3+b//L
            a22=(c//L)*3+(d-3*L)//L
            if a//L!=c//L:
                return abs(a-c)+abs(b-d)
            elif a//L==1:
                if a12==5 and a22==3: return dist(a-L,b-2*L,c-L,d-2*L,n-1)
                else: return min(a+c-2*(L-1),4*L-a-c)+abs(b-d)
            elif a//L==0:
                if a12==0:
                    return dist(a,b,c,d-(a22+1)*L,n-1) + (a22+1)*L
                else: return dist(a,b-a12*L,c,d-a12*L,n) 
            elif a//L==2: return dist(a-2*L,b,c-2*L,d,n)

        if area2==2:
            L=3**(n-1)
            if a//L!=c//L:
                return abs(a-c)+abs(b-d)
            elif a//L in [0,2]:
                return dist(a,b,c,d-3*L,n)+3*L
            else:
                return min(a+c-2*(L-1),2*L-a-c)+abs(b-d)

        else: return 0

    elif area1==1:
        if area2 in [3,5,6,8]:
            return abs(a-c)+abs(b-d)
        elif area2==2:
            return dist(a,b-L,c,d-L,n)
        elif area2==7:
            return min(b+d-2*(L-1),(4*L)-b-d)+abs(a-c)
        else: return 0



for i in range(int(input())):
    a,b,c,d=map(int,input().split())
    print(dist(a-1,b-1,c-1,d-1,29))

Submission status: Wrong Answer

Solution code:
def dist(a,b,c,d,n):
    L=3**n
    area1=(a//L)*3+b//L
    if area1==2:
        b=L*3-b-1
        d=L*3-d-1
    if area1==3:
        a,b=b,a
        c,d=d,c
    if area1==5:
        a,b=L*3-b-1,a
        c,d=L*3-d-1,c
    if area1 in [6,7]:
        a=L*3-a-1
        c=L*3-c-1
    if area1==8:
        a,b=L*3-a-1,L*3-b-1
        c,d=L*3-c-1,L*3-d-1

    area1=(a//L)*3+b//L
    area2=(c//L)*3+d//L


    if area1>area2:
        a,b,c,d=c,d,a,b
        area1,area2=area2,area1

    if area1==area2:
        return dist(a%L,b%L,c%L,d%L,n-1)
    elif area1==0:
        if area2 in [5,7,8]:
            return abs(a-c)+abs(b-d)
        if area2 in [3,6]:
            return dist(b,a,d,c,n)

        if area2==1:
            L=3**(n-1)
            a12=(a//L)*3+b//L
            a22=(c//L)*3+(b-3*L)//L

            if a//L!=c//L:
                return abs(a-c)+abs(b-d)
            elif a//L==1:
                if a12==5 and a22==3: return dist(a-L,b-2*L,c-L,d-2*L,n-1)
                else: return min(a+c-2*(L-1),2*L-a-c)+abs(b-d)
            elif a//L==0:
                if a12==0: return dist(a,b,c,d-(a22+1)*L,n-1)+(a22+1)*L
                else: return dist(a,b-a12*L,c,d-a12*L,n) 
            elif a//L==2: return dist(a-2*L,b,c-2*L,d,n)

        if area2==2:
            L=3**(n-1)
            if a//L!=c//L:
                return abs(a-c)+abs(b-d)
            elif a//L in [0,2]:
                return dist(a,b,c,d-3*L,n)+3*L
            else:
                return min(a+c-2*(L-1),2*L-a-c)+abs(b-d)

        else: return 0

    elif area1==1:
        if area2 in [3,5,6,8]:
            return abs(a-c)+abs(b-d)
        elif area2==2:
            return dist(a,b-L,c,d-L,n)
        elif area2==7:
            return min(b+d-2*(L-1),(4*L)-b-d)+abs(a-c)
        else: return 0



for i in range(int(input())):
    a,b,c,d=map(int,input().split())
    print(dist(a-1,b-1,c-1,d-1,29))

Submission status: Wrong Answer

Solution code:
def dist(a,b,c,d,n):
    L=3**n
    area1=(a//L)*3+b//L
    if area1==2:
        b=L*3-b-1
        d=L*3-d-1
    if area1==3:
        a,b=b,a
        c,d=d,c
    if area1==5:
        a,b=L*3-b-1,a
        c,d=L*3-d-1,c
    if area1 in [6,7]:
        a=L*3-a-1
        c=L*3-c-1
    if area1==8:
        a,b=L*3-a-1,L*3-b-1
        c,d=L*3-c-1,L*3-d-1

    area1=(a//L)*3+b//L
    area2=(c//L)*3+d//L


    if area1>area2:
        a,b,c,d=c,d,a,b
        area1,area2=area2,area1

    if area1==area2:
        return dist(a%L,b%L,c%L,d%L,n-1)
    elif area1==0:
        if area2 in [5,7,8]:
            return abs(a-c)+abs(b-d)
        if area2 in [3,6]:
            return dist(b,a,d,c,n)

        if area2==1:
            L=3**(n-1)
            a12=(a//L)*3+b//L
            a22=(c//L)*3+(b-3*L)//L

            if a//L!=c//L:
                return abs(a-c)+abs(b-d)
            elif a//L==1:
                if a12==5 and a22==3: return dist(a-L,b-2*L,c-L,d-2*L,n-1)
                else: return min(a+c-2*(L-1),2*L-a-c)+abs(b-d)
            elif a//L==0:
                if a12==0: return dist(a,b,c,d-(a22+1)*L,n-1)+(a22+1)*L
                else: return dist(a,b-a12*L,c,d-a12*L,n) 
            elif a//L==2: return dist(a-2*L,b,c-2*L,d,n)



            return 0

        if area2==2:
            L=3**(n-1)
            if a//L!=c//L:
                return abs(a-c)+abs(b-d)
            elif a//L in [0,2]:
                return dist(a,b,c,d-3*L,n)+3*L
            else:
                return min(a+c-2*(L-1),2*L-a-c)+abs(b-d)

        else: return 0

    elif area1==1:
        if area2 in [3,5,6,8]:
            return abs(a-c)+abs(b-d)
        elif area2==2:
            return dist(a,b-L,c,d-L,n)
        elif area2==7:
            return min(b+d-2*(L-1),(2*L)-b-d)+abs(a-c)
        else: return 0



for i in range(int(input())):
    a,b,c,d=map(int,input().split())
    print(dist(a-1,b-1,c-1,d-1,29))

Submission status: Wrong Answer

Solution code:
def between(x, y1, y2):
    if x % 3 != 1:return False
    if y1 > y2:
        y1,y2= y2,y1
    for i in range(10):
        if y1 + i >= y2:break
        if (y1 + i) % 3 == 1:
            return True
    return False
    
def dist(x1, y1, x2, y2):
    three = 1
    extra = 0
    for i in range(33):
        if x1 // three == x2 // three and between(x1 //three, y1 //three, y2//three):
            extra = max(extra, min(min(x1 % three, x2 %three) + 1, three - max(x1 % three, x2 % three)))
        three *= 3

    return abs(x1-x2) + abs(y1-y2) + extra * 2

def solve():
    a,b,c,d = map(int, input().split())
    a,b,c,d = a-1,b-1,c-1,d-1
    print(min(dist(a,b,c,d), dist(b,a,d,c)))

q = int(input())
for _ in range(q):
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

def dist(a,b,c,d,P3):
    for p in P3:
        da,ma=divmod(a,p)
        dc,mc=divmod(c,p)
        if da!=dc:
            return abs(a-c)+abs(b-d)
        if da!=1:
            a,c=ma,mc
            continue
        db,mb=divmod(b,p)
        dd,md=divmod(d,p)
        if db==dd:
            a,c=ma,mc
            continue
        return min(ma+mc+2,2*p-(ma+mc))+abs(b-d)
    return abs(a-c)+abs(b-d)

def main():
    q=int(input())
    P3=[pow(3,i) for i in reversed(range(30))]
    for _ in range(q):
        a,b,c,d=map(lambda x: int(x)-1,input().split())
        print(max(dist(a,b,c,d,P3),dist(b,a,d,c,P3)))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

def dist(a,b,c,d,P3):
    for p in P3:
        da,ma=divmod(a,p)
        dc,mc=divmod(c,p)
        if da!=dc:
            return abs(a-c)+abs(b-d)
        if da!=1:
            a,c=ma,mc
            continue
        db,mb=divmod(b,p)
        dd,md=divmod(d,p)
        if db==dd:
            a,c=ma,mc
            continue
        return min(ma+mc+2,2*p-(ma+mc))+abs(b-d)
    return abs(b-d)

def main():
    q=int(input())
    P3=[pow(3,i) for i in reversed(range(30))]
    for _ in range(q):
        a,b,c,d=map(lambda x: int(x)-1,input().split())
        print(max(dist(a,b,c,d,P3),dist(b,a,d,c,P3)))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
def between(x, y1, y2):
 #   if x % 3 != 1:return False
    if y1 > y2:
        y1,y2= y2,y1
    for i in range(1,4):
        if y1 + i >= y2:break
        if (y1 + i) % 3 == 1:
            return True
    return False
    
def dist(x1, y1, x2, y2):
    three = 1
    extra = 0
    for i in range(33):
        if x1 // three == x2 // three and between(x1 //three, y1 //three, y2//three):
            extra = max(extra, min(min(x1 % three, x2 %three) + 1, three - max(x1 % three, x2 % three)))
        three *= 3

    return abs(x1-x2) + abs(y1-y2) + extra * 2

def solve():
    a,b,c,d = map(int, input().split())
    a,b,c,d = a-1,b-1,c-1,d-1
    print(min(dist(a,b,c,d), dist(b,a,d,c)))

q = int(input())
for _ in range(q):
    solve()

Submission status: Wrong Answer

Solution code:
def between(x, y1, y2):
    if x % 3 != 1:return False
    if y1 > y2:
        y1,y2= y2,y1
    for i in range(1,4):
        if y1 + i >= y2:break
        if (y1 + i) % 3 == 1:
            return True
    return False
    
def dist(x1, y1, x2, y2):
    three = 1
    extra = 0
    for i in range(33):
        if x1 // three == x2 // three and between(x1 //three, y1 //three, y2//three):
            extra = max(extra, min(min(x1 % three, x2 %three) + 1, three - max(x1 % three, x2 % three)))
        three *= 3

    return abs(x1-x2) + abs(y1-y2) + extra * 2

def solve():
    a,b,c,d = map(int, input().split())
    a,b,c,d = a-1,b-1,c-1,d-1
    print(min(dist(a,b,c,d), dist(b,a,d,c)))

q = int(input())
for _ in range(q):
    solve()

Submission status: Wrong Answer

Solution code:
def between(x, y1, y2):
    if x % 3 != 1:return False
    if y1 > y2:
        y1,y2= y2,y1
    for i in range(1,4):
        if y1 + i >= y2:break
        if (y1 + i) % 3 == 1:
            return True
    return False
    
def dist(x1, y1, x2, y2):
    three = 1
    extra = 0
    for i in range(33):
        if x1 // three == x2 // three and between(x1 //three, y1 //three, y2//three):
            extra = max(extra, min(min(x1 % three, x2 %three) + 1, three - max(x1 % three, x2 % three)))

    return abs(x1-x2) + abs(y1-y2) + extra * 2

def solve():
    a,b,c,d = map(int, input().split())
    a,b,c,d = a-1,b-1,c-1,d-1
    print(min(dist(a,b,c,d), dist(b,a,d,c)))

q = int(input())
for _ in range(q):
    solve()

Submission status: Wrong Answer

Solution code:
def between(x, y1, y2):
    if y1 > y2:
        y1,y2= y2,y1
    for i in range(1,4):
        if y1 + i >= y2:continue
        if (y1 + i) % 3 == 1:
            return True
    return False
    
def dist(x1, y1, x2, y2):
    three = 1
    extra = 0
    for i in range(33):
        if x1 // three == x2 // three and between(x1 //three, y1 //three, y2//three):
            extra = max(extra, min(x1 % three, x2 %three) + 1, three - max(x1 % three, x2 % three))

    return abs(x1-x2) + abs(y1-y2) + extra * 2

def solve():
    a,b,c,d = map(int, input().split())
    a,b,c,d = a-1,b-1,c-1,d-1
    print(min(dist(a,b,c,d), dist(b,a,d,c)))

q = int(input())
for _ in range(q):
    solve()

Submission status: Wrong Answer

Solution code:
def between(x, y1, y2):
    if y1 > y2:
        y1,y2= y2,y1
    for i in range(3):
        if y1 + i > y2:continue
        if (y1 + i) % 3 == 1:
            return True
    return False
    
def dist(x1, y1, x2, y2):
    three = 1
    extra = 0
    for i in range(33):
        if x1 // three == x2 // three and between(x1 //three, y1 //three, y2//three):
            extra = max(extra, min(x1 % three, x2 %three) + 1, three - max(x1 % three, x2 % three))

    return abs(x1-x2) + abs(y1-y2) + extra * 2

def solve():
    a,b,c,d = map(int, input().split())
    a,b,c,d = a-1,b-1,c-1,d-1
    print(min(dist(a,b,c,d), dist(b,a,d,c)))

q = int(input())
for _ in range(q):
    solve()

Submission status: Wrong Answer

Solution code:

def fc (x):
    for i in range(30):
        j = 3 ** (30 - i)
        if x // j == 2:
            return j//3
    return 0
q = int(input())
for i in range(q):
    p = [int(x) for x in input().split()]
    ans = abs(p[0]-p[2])+abs(p[1]-p[3])
    q = [fc(x) for x in p]
    a1 = abs(p[0]-p[2])
    a2 = abs(p[1]-p[3])
    for v in range(4):
        if q[v] != 0:
            p[v] = p[v] % q[v]
            if p[v] == 0:
                p[v] = q[v]
    a,b,c,d = p
    k,l,m,n = q
    if k == m and k*m != 0:
        if a1 > k:
            ans += min(k-a+m-c,a+c)
    if l == n and l*n != 0:
        if a2 > l:
            ans += min(b+d,l-b+n-d)
    print(ans)

Submission status: Wrong Answer

Solution code:

def fc (x):
    for i in range(30):
        j = 3 ** (30 - i)
        if x // j == 2:
            return j//3
    return 0
q = int(input())
for i in range(q):
    p = [int(x) for x in input().split()]
    ans = abs(p[0]-p[2])+abs(p[1]-p[3])
    q = [fc(x) for x in p]
    for v in range(4):
        if q[v] != 0:
            p[v] = p[v] % q[v]
            if p[v] == 0:
                p[v] = q[v]
    a,b,c,d = p
    k,l,m,n = q
    if k == m and k*m != 0:
        if abs(b-d) > k:
            ans += min(k-a+m-c,a+c)
    if l == n and l*n != 0:
        if abs(a-c) > l:
            ans += min(b+d,l-b+n-d)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

q = int(input())
query = [list(map(int, input().split())) for i in range(q)]

for a,b,c,d in query:
    a,b,c,d = a-1,b-1,c-1,d-1
    for lv in range(30,0,-1):
        k = pow(3, lv-1)
        l = 3*k
        x1,y1 = a//k%3, b//k%3
        x2,y2 = c//k%3, d//k%3
        dx = abs(x1-x2)
        dy = abs(y1-y2)
        xx1, yy1 = a//k, b//k
        xx2, yy2 = c//k, d//k
        dxx = abs(xx1-xx2)
        dyy = abs(yy1-yy2)
        if x1==x2==1:
            if dyy < 2:
                continue
            xa = a%l
            xc = c%l
            ans = abs(a-c)+abs(b-d)
            ans += 2*min([abs(k-1-xa), abs(2*k-xa), abs(k-1-xc), abs(2*k-xc)])
            print(ans)
            break
        elif y1==y2==1:
            if dxx < 2:
                continue
            yb = b%l
            yd = d%l
            ans = abs(a-c)+abs(b-d)
            ans += 2*min([abs(k-1-yb), abs(2*k-yb), abs(k-1-yd), abs(2*k-yd)])
            print(ans)
            break
        elif (dx == 2 and dy != 0) or (dx != 0 and dy == 2):
            ans = abs(a-c) + abs(b-d)
            print(ans)
            break
    else:
        ans = abs(a-c)+abs(b-d)
        print(ans)

Submission status: Wrong Answer

Solution code:

def fc (x):
    for i in range(30):
        j = 3 ** (30 - i)
        if x // j == 2:
            return j//3
    return 0
q = int(input())
for i in range(q):
    p = [int(x) for x in input().split()]
    ans = abs(p[0]-p[2])+abs(p[1]-p[3])
    q = [fc(x) for x in p]
    for v in range(4):
        if q[v] != 0:
            p[v] = p[v] % q[v]
            if p[v] == 0:
                p[v] = q[v]
    a,b,c,d = p
    k,l,m,n = q
    if k == m and k*m != 0:
        if abs(b-d) > k:
            ans += min(a-k+c-m,2*k-a+1+2*m-c+1)
    if l == n and l*n != 0:
        if abs(a-c) > l:
            ans += min(b-l+d-n,2*l-b+1+2*n-d+1)
    print(ans)

Submission status: Wrong Answer

Solution code:
Q, *abcd = map(int, open(0).read().split())
abcd = list(zip(*[iter(abcd)] * 4))

for a,b,c,d in abcd:
    md = abs(a-c) + abs(b-d)
    dx = 0
    for i in range(1,30):
        dx_1 = 0
        dx_2 = 0
        g = 3 ** i
        if (a%3==1) == (c%3==1):
            dx_1 = (a%g) + (c%g) + 2
            dx_1 = min(dx, (g+1)/2 - dx)
        if (b%3==1) == (d%3==1):
            dx_2 = (b%g) + (d%g) + 2
            dx_2 = min(dx, (g+1)/2 - dx)
        dx = max(dx, dx_1, dx_2)
        a = a // 3
        b = b // 3
        c = c // 3
        d = d // 3
    print(md + dx)

Submission status: Wrong Answer

Solution code:
def makeVec(a, b):
    ret = []
    for i in range(30):
        a, r1 = divmod(a, 3)
        b, r2 = divmod(b, 3)
        ret.append((r1, r2))
    assert a == 0
    assert b == 0
    return ret


def solve(A, B, C, D):
    source = makeVec(A, B)
    dest = makeVec(C, D)
    detour = 0
    for level in range(29, -1, -1):
        a, b = source[level]
        c, d = dest[level]
        if (a, b) != (c, d):
            # Find the highest level where we need to move due to a blocking center block.
            axis = None
            if a == c == 1:
                assert (b, d) == (0, 2) or (b, d) == (2, 0)
                axis = 0
            elif b == d == 1:
                print(a, c)
                assert (a, c) == (0, 2) or (a, c) == (2, 0)
                axis = 1
            if axis is not None:
                # Best move is to just move to sideways to the axis of blockage.
                # Edges of the fractal are always blank so just need manhattan distance to reach it.
                move1 = sum(
                    (source[l][axis] + dest[l][axis]) * (3 ** l) for l in range(level)
                )
                move2 = sum(
                    (2 - source[l][axis] + 2 - dest[l][axis]) * (3 ** l)
                    for l in range(level)
                )
                detour += min(move1, move2) + 2
                break
    ans = abs(A - C) + abs(B - D) + detour
    return ans


if False:
    print(solve(0, 4, 2, 4) == 4)
    print(solve(0, 4, 6, 4) == 10)
    print(solve(0, 4, 8, 4) == 12)


Q, = list(map(int, input().split()))

for i in range(Q):
    A, B, C, D = (int(x) - 1 for x in input().split())
    print(solve(A, B, C, D))

Submission status: Wrong Answer

Solution code:
Q = int(input())
abcd = []
while(Q):
    Q -= 1
    abcd.append(list(map(int,input().split(" "))))
def distance(p,q):
    return abs(p[0]-q[0])+abs(p[1]-q[1])
  
n = 3**29
for a,b,c,d in abcd:
    P = (a,b)
    Q = (c,d)
    m = n
    while(m > 3**-1):
        x,y,z,w = P[0]//m,P[1]//m,Q[0]//m,Q[0]//m
        if(x == z and y == w):
            P,Q = (P[0]%m,P[1]%m),(Q[0]%m,Q[1]%m)
            m //= 3
            continue
        elif(x == z and z == 1):
            dd = distance((a,b),(c,d))+2*min(P[0],m-P[0],Q[0],m-Q[0])
            print(dd)
            break
        elif( y == w and y == 1):
            dd = distance((a,b),(c,d))+2*min(P[1],m-P[1],Q[1],m-Q[1])
            print(dd)
            break
        else:
            print(distance((a,b),(c,d)))
            break

Submission status: Wrong Answer

Solution code:
q = int(input())
for iii in range(q):
    a, b, c, d = map(int,input().split())
    a-=1
    b-=1
    c-=1
    d-=1

    def f(n):
        A = [0] * 30
        for i in range(30):
            A[i] = n%3
            n//=3
        return A
    A = f(a)[::-1]
    B = f(b)[::-1]
    C = f(c)[::-1]
    D = f(d)[::-1]

    def g(A, B):
        # print(A,B)
        # ans = float("inf")
        A = A[::-1]
        B = B[::-1]
        aa=0
        bb=0
        k = 1
        for i in range(len(A)):
            aa += k*A[i]
            bb += k*B[i]
            k *= 3
        # print(aa+1, k-aa, bb+1, k-bb)
        return min(aa+1, k-aa, bb+1, k-bb)
    
    def h(A, B):
        A = A[::-1]
        B = B[::-1]
        aa=0
        bb=0
        k = 1
        for i in range(len(A)):
            aa += k*A[i]
            bb += k*B[i]
            k *= 3
        if abs(aa-bb)==1:
            return 1
        return 0

    aaa = 0
    i = 0
    while i < 30 and A[i] == C[i]:
        if A[i]==1 and h(B[:i+1], D[:i+1]) == 0:
            aaa = g(A[i+1:],C[i+1:]) if i != 30 else 1
            break
        i += 1
    i = 0
    while i < 30 and B[i] == D[i]:
        if B[i]==1 and h(A[:i+1], C[:i+1]) == 0:
            aaa = g(D[i+1:],B[i+1:]) if i != 30 else 1
            break
        i += 1
    # print(aaa)
    print(abs(a-c)+abs(b-d)+aaa*2)

Submission status: Wrong Answer

Solution code:
Q = int(input())
abcd = []
while(Q):
    Q -= 1
    abcd.append(list(map(int,input().split(" "))))
 
def distance(p,q):
    return abs(p[0]-q[0])+abs(p[1]-q[1])
  

for a,b,c,d in abcd:
    P = (a,b)
    Q = (c,d)
    m = 3**29
    while(m > 3**-1):
        x,y,z,w = P[0]//m,P[1]//m,Q[0]//m,Q[0]//m
        print(m,P[0],P[1],Q[0],Q[1])
        print(x,y,z,w)
        if(x == z and y == w):
            P,Q = (P[0]%m,P[1]%m),(Q[0]%m,Q[1]%m)
            m //= 3
            continue
        elif(x == z and z == 1):
            dd = distance((a,b),(c,d))+2*min(P[0],m-P[0],Q[0],m-Q[0])
            print(dd)
        elif( y == w and y == 1):
            dd = distance((a,b),(c,d))+2*min(P[1],m-P[1],Q[1],m-Q[1])
            print(dd)
        else:
            print(distance((a,b),(c,d)))
            break