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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def solve(A,B,C,D,E=3**30):
    if E:
        EE = 3 * E
        a = A//EE
        b = B//EE
        c = C//EE
        d = D//EE
    else:
        a,b,c,d = A,B,C,D
        if a != c and b != d:
            return abs(A-C) + abs(B-D)
        if b == d and a != c:
            A,B = B,A
            a,b = b,a
            C,D = D,C
            c,d = d,c
        if a == c and b != d:
            if a % 3 != 1:
                return abs(b-d)
            else:
                return abs(b-d) + 2
    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,E//3)
    if b == d and a != c:
        A,B = B,A
        a,b = b,a
        C,D = D,C
        c,d = d,c
    if a == c and b != d:
        if B > D:
            A,B,C,D = C,D,A,B
            a,b,c,d = c,d,a,b
        if a % 3 != 1:
            return solve(A,B,C,D,E//3)
        x1 = EE * a - 1
        y1 = EE * (b+1) - 1
        y2 = EE * d
        dist1 = abs(x1-A) + abs(y1-B) + abs(y1-y2) + abs(x1-C) + abs(y2-D)
        x1 = EE * (a+1)
        y1 = EE * (b+1) - 1
        y2 = EE * d
        dist2 = abs(x1-A) + abs(y1-B) + abs(y1-y2) + abs(x1-C) + abs(y2-D)
        return min(dist1, dist2)

solve(0,4,6,4)

N = int(readline())
m = map(int,read().split())
for A,B,C,D in zip(m,m,m,m):
    print(solve(A-1,B-1,C-1,D-1,3**30))

Submission status: Wrong Answer

Solution code:
def g(x):
    kkk=[0]*31
    for j in range(30,-1,-1):
        kkk[j]=x//data[j]
        x%=data[j]
    return kkk

def f(a,b,c,d):
    a-=1
    b-=1
    c-=1
    d-=1
    A=g(a)
    B=g(b)
    C=g(c)
    D=g(d)
    ans=0
    for i in range(30,-1,-1):
        if A[i]==C[i]==0:
            continue
        elif A[i]==C[i]==1:
            num1=a-3**i+1+c-3**i+1
            num2=2*3**i-a+2*3**i-c
            ans+=min(num1,num2)
            break
        elif A[i]==C[i]==2:
            continue
        else:
            ans+=abs(a-c)
            break
    for i in range(30,-1,-1):
        if B[i]==D[i]==0:
            continue
        elif B[i]==D[i]==1:
            num1=b-3**i+1+d-3**i+1
            num2=2*3**i-b+2*3**i-d
            ans+=min(num1,num2)
            break
        elif B[i]==D[i]==2:
            continue
        else:
            ans+=abs(b-d)
            break
    return ans

data=[0]*31
data[0]=1
for i in range(1,31):
    data[i]=3*data[i-1]
    
Q=int(input())
abcd=[list(map(int,input().split())) for i in range(Q)]

for a,b,c,d in abcd:
    print(f(a,b,c,d))

Submission status: Wrong Answer

Solution code:
x=int(input())
ans=0
for i in range(x):
	a,b,c,d=list(map(int, input().split()))
	ans=0
	if a%3==2 and a==c and abs(b-d)!=1:
		ans=ans+2
	if b%3==2 and b==d and abs(a-c)!=1:
		ans=ans+2
	print(ans+abs(a-c)+abs(b-d))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def solve(A,B,C,D,E=3**30):
    if E:
        EE = 3 * E
        a = A//EE
        b = B//EE
        c = C//EE
        d = D//EE
    else:
        a,b,c,d = A,B,C,D
        if a != c and b != d:
            return abs(A-C) + abs(B-D)
        if b == d and a != c:
            A,B = B,A
            a,b = b,a
            C,D = D,C
            c,d = d,c
        if a == c and b != d:
            if a % 3 != 1:
                return abs(b-d)
            else:
                return abs(b-d) + 2
    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,E//3)
    if b == d and a != c:
        A,B = B,A
        a,b = b,a
        C,D = D,C
        c,d = d,c
    if a == c and b != d:
        if B > D:
            A,B,C,D = C,D,A,B
            a,b,c,d = c,d,a,b
        if a % 3 != 1:
            return solve(A,B,C,D,E//3)
        x1 = EE * a - 1
        y1 = EE * (b+1) - 1
        y2 = EE * d
        dist1 = abs(x1-A) + abs(y1-B) + abs(y1-y2) + abs(x1-C) + abs(y2-D)
        x1 = EE * (a+1)
        y1 = EE * b - 1
        y2 = EE * (d-1)
        dist2 = abs(x1-A) + abs(y1-B) + abs(y1-y2) + abs(x1-C) + abs(y2-D)
        return min(dist1, dist2)

N = int(readline())
m = map(int,read().split())
for A,B,C,D in zip(m,m,m,m):
    print(solve(A-1,B-1,C-1,D-1,3**30))

Submission status: Wrong Answer

Solution code:

def x(a, c):
    k = 3 ** 10
    for _ in range(10):
        if (a % k) // (k // 3) == 1 and (c % k) // (k // 3) == 1:
            kk = k//3
            aa = a % k
            cc = c % k
            return min(aa + cc+2 - 2 * kk, k * 2 - aa - cc - 2 * kk)
        k//=3
    return abs(a-c)

q = int(input())
for _ in range(q):
    a, b, c, d = [int(i) - 1 for i in input().split()]
    
    print(x(a,c)+x(b,d))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def solve(A,B,C,D,E=3**30):
    if E:
        EE = 3 * E
        a = A//EE
        b = B//EE
        c = C//EE
        d = D//EE
    else:
        a,b,c,d = A,B,C,D
        if a != c and b != d:
            return abs(A-C) + abs(B-D)
        if b == d and a != c:
            A,B = B,A
            a,b = b,a
            C,D = D,C
            c,d = d,c
        if a == c and b != d:
            if a % 3 != 1:
                return abs(b-d)
            else:
                return abs(b-d) + 2
    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,E//3)
    if b == d and a != c:
        A,B = B,A
        a,b = b,a
        C,D = D,C
        c,d = d,c
    if a == c and b != d:
        if B > D:
            A,B,C,D = C,D,A,B
            a,b,c,d = c,d,a,b
        if a % 3 != 1:
            return solve(A,B,C,D,E//3)
        print('!!',A,B,C,D,E)
        x = solve(E*a-1,E*b-1,E*a-1,E*(d-1),E) + E*(d-b) + 1
        y = solve(E*(a+1),E*b-1,E*(a+1),E*(d-1),E) + E*(d-b) + 1
        return min(x,y)
    

N = int(readline())
m = map(int,read().split())
for A,B,C,D in zip(m,m,m,m):
    print(solve(A-1,B-1,C-1,D-1,3**30))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
q = int(input())
for _ in range(q):
    a, b, c, d = [int(i) - 1 for i in input().split()]
    ans = 0
    k = 3
    while True:
        if a // k == c // k:
            break
        k *= 3
    kk = k//3
    aa = a % k
    cc = c % k
    if aa // (k // 3) == 1 and cc // (k // 3) == 1:
        ans += min(aa + cc+2 - 2 * kk, k * 2 - aa - cc - 2 * kk)
    else:
        ans += abs(a - c)

    k = 3
    while True:
        if b // k == d // k:
            break
        k *= 3
    kk = k//3
    aa = b % k
    cc = d % k
    if aa // (k // 3) == 1 and cc // (k // 3) == 1:
        ans += min(aa + cc+2 - 2 * kk, k * 2 - aa - cc - 2 * kk)
    else:
        ans += abs(b-d)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def solve(A,B,C,D,E):
    if E == 0:
        return abs(C-A) + abs(D-B)
    EE = E * 3
    a = A//EE
    b = B//EE
    c = C//EE
    d = D//EE
    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,E//3)
    if b == d and a != c:
        A,B = B,A
        a,b = b,a
        C,D = D,C
        c,d = d,c
    if a == c and b != d:
        if B > D:
            A,B,C,D = C,D,A,B
            a,b,c,d = c,d,a,b
        if a % 3 != 1:
            return solve(A,B,C,D,E//3)
        x = solve(E*a-1,E*b-1,E*a-1,E*(d-1),E) + E*(d-b) + 1
        y = solve(E*(a+1),E*b-1,E*(a+1),E*(d-1),E) + E*(d-b) + 1
        return min(x,y)
    

N = int(readline())
m = map(int,read().split())
for A,B,C,D in zip(m,m,m,m):
    print(solve(A-1,B-1,C-1,D-1,3**30))

Submission status: Wrong Answer

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
'''


#a = list(map(int, input().split()))

n = int(input())

for k in range(n):
        
    a = list(map(int, input().split()))
    ac = []
    for j in range(4):
        a[j] -= 1
        ac.append(a[j])
    
    t = [[0 for i in range(30)] for j in range(4)]
         
    for j in range(4):
        for i in range(30):
            t[j][i] = a[j]%3
            a[j] = a[j]//3
    
    cor1 = -1
    
    for i in range(30):
        if(t[0][29-i] != t[2][29-i]):
            cor1 = -1
            break
        else:
            if(t[0][29-i] == 1):
                cor1 = 29-i
                break
    cor2 = -1
    for i in range(30):
        if(t[1][29-i] != t[3][29-i]):
            cor2 = -1
            break
        else:
            if(t[1][29-i] == 1):
                cor2 = 29-i
                break
    
    
    
    if(cor1>=cor2 and cor1>=0):
        base = 3**cor1
        x1 = ac[0]%base
        x2 = ac[2]%base
        xdist = min(base+1-x1 + base+1-x2, x1+1 + x2+1)
        ydist = abs(ac[1]-ac[3])
        #print(xdist,ydist)
        print(int(0.01+xdist+ydist))
        
    elif(cor2>=0):
        base = 3**cor2
        y1 = ac[1]%base
        y2 = ac[3]%base
        xdist = min(base+1-y1 + base+1-y2, y1+1 + y2+1)
        ydist = abs(ac[0]-ac[2])
        #print(xdist,ydist)
        print(int(0.01+xdist+ydist))
    else:
        xdist=abs(ac[0]-ac[2])
        ydist=abs(ac[1]-ac[3])
        print(int(0.01+xdist+ydist))

Submission status: Wrong Answer

Solution code:
q = int(input())
for _ in range(q):
    a, b, c, d = [int(i) - 1 for i in input().split()]
    ans = 0
    k = 3
    while True:
        if a // k == c // k:
            break
        k *= 3
    kk = k//3
    aa = a % k
    cc = c % k
    if aa // (k // 3) == 1 and cc // (k // 3) == 1:
        ans += min(a + c+2 - 2 * kk, k * 2 - a - c - 2 * kk)
    else:
        ans += abs(a - c)

    k = 3
    while True:
        if b // k == d // k:
            break
        k *= 3
    kk = k//3
    aa = b % k
    cc = d % k
    if aa // (k // 3) == 1 and cc // (k // 3) == 1:
        ans += min(b+d+2 - 2 * kk, k * 2-b-d - 2 * kk)
    else:
        ans += abs(b-d)
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
'''


#a = list(map(int, input().split()))

n = int(input())

for k in range(n):
        
    a = list(map(int, input().split()))
    ac = []
    for j in range(4):
        a[j] -= 1
        ac.append(a[j])
    
    t = [[0 for i in range(30)] for j in range(4)]
         
    for j in range(4):
        for i in range(30):
            t[j][i] = a[j]%3
            a[j] = a[j]//3
    
    cor1 = -1
    
    for i in range(30):
        if(t[0][29-i] != t[2][29-i]):
            cor1 = -1
            break
        else:
            if(t[0][29-i] == 1):
                cor1 = 29-i
                break
    cor2 = -1
    for i in range(30):
        if(t[1][29-i] != t[3][29-i]):
            cor2 = -1
            break
        else:
            if(t[1][29-i] == 1):
                cor2 = 29-i
                break
    
    if(cor1>=cor2):
        base = 3**cor1
        x1 = ac[0]%base
        x2 = ac[2]%base
        xdist = min(base+1-x1 + base+1-x2, x1+1 + x2+1)
        ydist = abs(ac[1]-ac[3])
        #print(xdist,ydist)
        print(int(0.01+xdist+ydist))
        
    else:
        base = 3**cor2
        y1 = ac[1]%base
        y2 = ac[3]%base
        xdist = min(base+1-y1 + base+1-y2, y1+1 + y2+1)
        ydist = abs(ac[0]-ac[2])
        #print(xdist,ydist)
        print(int(0.01+xdist+ydist))

Submission status: Wrong Answer

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

Submission status: Time Limit Exceeded

Solution code:
def dist(a,b,c,d,n):
    L=3**n
    area1=(a//L)*3+b//L
    if area1==2:
        b=3*L-b-1
        d=3*L-d-1
    if area1==3:
        a,b=b,a
        c,d=d,c
    if area1==5:
        a,b=3*L-b-1,a
        c,d=3*L-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==0:
        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)
                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: Time Limit Exceeded

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
        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

Submission status: Accepted

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 and ((m2 and bb!=dd) or (not m2 and abs(b-d)>2*pow(3,i))):
#             print(aa,bb,cc,dd,m1,m2,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)>2*pow(3,i))):
#             print(aa,bb,cc,dd,m1,m2,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: Accepted

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) == (l2  // v):
            if (l1 % v < _l) & (l2 % v > _h):
                c4 = True
            else:c4=False
        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: Accepted

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(29,-1,-1):
        r,q=B[i]
        l=3**i

        xcen=-(-(MINX-q)//r)*r+q
        ycen=-(-(MINY-q)//r)*r+q

        for xq in [xcen-r,xcen,xcen+r]:
            for yq in [ycen-r,ycen,ycen+r]:

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

                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:
                break
        if flag!=0:
            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: Accepted

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
        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: Accepted

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

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

Submission status: Accepted

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(lambda x:int(x)-1, input().split())))

Submission status: Accepted

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 and y1 % 3 == y2 % 3 == 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 and x1 % 3 == x2 % 3 == 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: Accepted

Solution code:
q=abs;s=lambda t,i:0--t//3**i;m=lambda a,b,c,d:max([i for i in range(30)if s(a,i)==s(c,i)and s(a,i)%3==2and 1<q(s(b,i)-s(d,i))]+[-1])+1
for _ in[0]*int(input()):
  a,b,c,d=map(int,input().split());h=m(a,b,c,d);w=m(b,a,d,c)
  if h==w==0:print(q(b-d)+q(a-c));continue
  if h<w:h,a,b,c,d=w,b,a,d,c
  i=3**h//3;x=2*i+1;g=a-(a-1)%(3*i)-1;a-=g;c-=g;print(q(b-d)+min(q(i-a)+q(i-c),q(x-a)+q(x-c)))

Submission status: Accepted

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==0:print(abs(b-d)+abs(a-c));continue
  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: Accepted

Solution code:
def solve(aa,bb,cc,dd):
  a,b,c,d=aa,bb,cc,dd
  mx=my=0
  for i in range(1,31):
    if a==c and a%3==2 and abs(b-d)>=2:mx=i
    if b==d and b%3==2 and abs(a-c)>=2:my=i
    a=0--a//3
    b=0--b//3
    c=0--c//3
    d=0--d//3
  a,b,c,d=aa,bb,cc,dd
  if mx==my==0:return abs(a-c)+abs(b-d)
  if mx<my:
    ans=abs(a-c)
    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
  if mx>my:
    ans=abs(b-d)
    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
  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: Accepted

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:
        if gga == ggc:
            return solve(a % kk, b % kk, c % kk, d % kk + kk, i+1, carry)
        else:
            return man(a,b,c,d) + 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))