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

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve(ai,aj,bi,bj):
    s=pow(3,30)
    dist=abs(ai-bi)+abs(aj-bj)
    while s>1:
        s//=3
        si,sj,ti,tj=ai//s,aj//s,bi//s,bj//s
        if si!=ti:
            return dist
        if abs(sj-tj)>1 and si%3==1:
            up=s*si-1
            down=s*(si+1)
            return min(min(ai,bi)-up,down-max(ai,bi))*2+dist
    return dist

def main():
    q=II()
    for _ in range(q):
        ai,aj,bi,bj=MI1()
        if abs(ai-bi)>abs(aj-bj):ai,aj,bi,bj=aj,ai,bj,bi
        print(solve(ai,aj,bi,bj))

main()

Submission status: Accepted

Solution code:
import sys
def grid(p, level):
    c = 3 ** level
    return ((p[0] % (3 * c)) // c, (p[1] % (3 * c)) // c)

def sub(p1, p2, level):
    # print('sub',(p1, p2, level))
    if level < 0:
        return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    g1, g2 = grid(p1, level), grid(p2, level)
    assert 0 <= g1[0] < 3
    assert 0 <= g1[1] < 3
    assert 0 <= g2[0] < 3
    assert 0 <= g2[1] < 3
    if g1[0] != g2[0]:
        return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    if g1[0] == 1:
        c = 3 ** level
        y1, y2 = p1[1] // c, p2[1] //c
        if abs(y1 - y2) < 2:
            return sub(p1, p2, level - 1)
        i1, i2 = p1[0] % c, p2[0] % c
        xp = min(i1 + i2 + 2, 2 * c - i1 - i2)
        return xp + abs(p1[1] - p2[1])
    return sub(p1, p2, level - 1)

def solve(p1, p2, level):
    g1, g2 = grid(p1, level), grid(p2, level)
    if g1 == g2:
        if level == 0:
           return 0 
        return solve(p1, p2, level - 1)
    if g1[0] == g2[0]:
        return sub(p1, p2, level)
    elif g1[1] == g2[1]:
        return sub((p1[1], p1[0]), (p2[1], p2[0]), level)
    else:
        return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

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

Submission status: Accepted

Solution code:
def solve(a, b, c, d):
  mnx = min(a, c)
  mxx = max(a, c)
  mny = min(b, d)
  mxy = max(b, d)
  s = 3
  for k in range(32):
    if a<c:
      rx = (a+s/3*2)/s*s+s/3
      ry = (max(b, d)+s/3)/s*s+s/3
      if rx+s/3<=c and ry+s/3>max(b, d) and ry<=min(b, d):
        mny = min(mny, ry-1)
        mxy = max(mxy, ry+s/3)
        #print "a", k, s, rx, ry
    else:
      rx = (c+s/3*2)/s*s+s/3
      ry = (max(b, d)+s/3)/s*s+s/3
      if rx+s/3<=a and ry+s/3>max(b, d) and ry<=min(b, d):
        mny = min(mny, ry-1)
        mxy = max(mxy, ry+s/3)
        #print "b", k, s, rx, ry
    if b<d:
      rx = (max(a, c)+s/3)/s*s+s/3
      ry = (b+s/3*2)/s*s+s/3
      if ry+s/3<=d and rx+s/3>max(a, c) and rx<=min(a, c):
        mnx = min(mnx, rx-1)
        mxx = max(mxx, rx+s/3)
        #print "c", k, s, rx, ry
    else:
      rx = (max(a, c)+s/3)/s*s+s/3
      ry = (d+s/3*2)/s*s+s/3
      if ry+s/3<=b and rx+s/3>max(a, c) and rx<=min(a, c):
        mnx = min(mnx, rx-1)
        mxx = max(mxx, rx+s/3)
        #print "d", k, s, rx, ry
    s *= 3
  return min(a-mnx+c-mnx, mxx-a+mxx-c)+min(b-mny+d-mny, mxy-b+mxy-d)

"""
n = 9
F = [[None]*n for _ in range(n)]
def f(x, y, s):
  if s==1:
    return False
  if s/3<=x<s/3*2 and s/3<=y<s/3*2:
    return True
  return f(x%(s/3), y%(s/3), s/3)
for y in range(n):
  for x in range(n):
    F[y][x] = f(x, y, n)

def naive(a, b, c, d):
  D = [[9999]*n for _ in range(n)]
  D[b][a] = 0
  for dd in range(2*n):
    for y in range(n):
      for x in range(n):
        if D[y][x]==dd:
          for i in range(4):
            tx = x + [1, -1, 0, 0][i]
            ty = y + [0, 0, 1, -1][i]
            if 0<=tx<n and 0<=ty<n and not F[ty][tx]:
              D[ty][tx] = min(D[ty][tx], dd+1)
  return D[d][c]

for a in range(n):
  for b in range(n):
    if not F[b][a]:
      for c in range(n):
        for d in range(n):
          if not F[d][c]:
            x = solve(a, b, c, d)
            y = naive(a, b, c, d)
            if x!=y:
              print a, b, c, d, x, y
"""

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

Submission status: Accepted

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%L+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: Accepted

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(max(dist(a,b,c,d), dist(b,a,d,c)))

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

Submission status: Accepted

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 abs(db-dd)<2:
            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: Accepted

Solution code:
def solve():
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    if a > c:
        a, b, c, d = c, d, a, b
    for k in range(30, -1, -1):
        def check(a, b, c, d):
            if a // 3 ** k == c // 3 ** k and a // 3 ** k % 3 == 1 \
                    and (min(b, d) // 3 ** k % 3 == 0 and max(b, d) // 3 ** k % 3 == 2
                            or max(b, d) // 3 ** k - min(b, d) // 3 ** k >= 3):
                print(min(a % 3 ** k + 1 + c % 3 ** k + 1 + abs(b - d),
                    3 ** k - a % 3 ** k + 3 ** k - c % 3 ** k + abs(b - d)))
                return True
        if check(a, b, c, d) or check(b, a, d, c):
            return
    print(abs(a - c) + abs(b - d))

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

Submission status: Accepted

Solution code:
#解説を写経することは最高に悪魔的な行為だ…
def between(x,y1,y2):
    if y1>y2:y1,y2=y2,y1
    y1+=1;y2-=1
    if not(y1<=y2):
        return False
    while(x>0):
        if x%3==1:
            if y2-y1>3:
                return True
            for y in range(y1,y2+1):
                if y%3==1:
                    return True
        x//=3
        y1//=3
        y2//=3
    return False
def get_extra(x1,y1,x2,y2):
    ans=0
    three=1
    for i in range(35):
        if(x1//three==x2//three and between(x1//three,y1//three,y2//three)):
            tmp=min(min(x1%three,x2%three)+1,three-max(x1%three,x2%three))
            ans=max(ans,tmp)
        three*=3
    return ans
def get_dist(x1,y1,x2,y2):
    return abs(x1-x2)+abs(y1-y2)+2*max(get_extra(x1,y1,x2,y2),get_extra(y1,x1,y2,x2))
Q=int(input())
for i in range(Q):
    a,b,c,d=map(int,input().split())
    print(get_dist(a-1,b-1,c-1,d-1))

Submission status: Accepted

Solution code:
import sys


def solve(a, b, c, d):
    """ Lv.i の中央の■を、上下(a,c)に迂回する """
    for i in range(30, 0, -1):
        # ここに到達している時点で、Lv.i 盤面の同じ横ならびに位置することは保証されている
        d3i = d3[i - 1]
        da, ma = divmod(a, d3i)
        dc, mc = divmod(c, d3i)
        if da != dc:
            return abs(a - c) + abs(b - d)
        if da != 1:
            a, c = ma, mc
            continue
        db, mb = divmod(b, d3i)
        dd, md = divmod(d, d3i)
        if (abs(db - dd) < 2):
            a, c = ma, mc
            continue
        return min(ma + mc + 2, 2 * d3i - (ma + mc)) + abs(b - d)
    return abs(a - c) + abs(b - d)


d3 = [pow(3, i) for i in range(31)] + [0]

q = int(input())
buf = []
for line in sys.stdin:
    a, b, c, d = map(int, line.split())
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    ans = max(solve(a, b, c, d), solve(b, a, d, c))
    buf.append(ans)
print('\n'.join(map(str, buf)))

Submission status: Accepted

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):
    # 大きさEの穴まで考慮
    if not E:
        return abs(A-C) + abs(B-D)
    a = A//E
    b = B//E
    c = C//E
    d = 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,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 a % 3 != 1:
            return solve(A,B,C,D,E//3)
        if abs(b-d) == 1:
            return solve(A,B,C,D,E//3)
        if B > D:
            A,B,C,D = C,D,A,B
            a,b,c,d = c,d,a,b
        x1 = E * a - 1
        y1 = E * (b+1) - 1
        y2 = E * d
        dist1 = abs(x1-A) + abs(y1-B) + abs(y1-y2) + abs(x1-C) + abs(y2-D)
        x1 = E * (a+1)
        y1 = E * (b+1) - 1
        y2 = E * d
        dist2 = abs(x1-A) + abs(y1-B) + abs(y1-y2) + abs(x1-C) + abs(y2-D)
        return min(dist1, dist2)
 
solve(2,1,3,1)
 
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: Accepted

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):
    # 大きさEの穴まで考慮
    if not E:
        return abs(A-C) + abs(B-D)
    a = A//E
    b = B//E
    c = C//E
    d = 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,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 a % 3 != 1:
            return solve(A,B,C,D,E//3)
        if abs(b-d) == 1:
            return solve(A,B,C,D,E//3)
        if B > D:
            A,B,C,D = C,D,A,B
            a,b,c,d = c,d,a,b
        x1 = E * a - 1
        y1 = E * (b+1) - 1
        y2 = E * d
        dist1 = abs(x1-A) + abs(y1-B) + abs(y1-y2) + abs(x1-C) + abs(y2-D)
        x1 = E * (a+1)
        y1 = E * (b+1) - 1
        y2 = E * d
        dist2 = abs(x1-A) + abs(y1-B) + abs(y1-y2) + abs(x1-C) + abs(y2-D)
        return min(dist1, dist2)

solve(2,1,3,1)

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

Solution code:
def calc(a, b, c, d):
    if abs(c - a) < abs(d - b): a, b, c, d = b, a, d, c
    if c < a: a, b, c, d = c, d, a, b
    
    s = 3 ** 29
    while s:
        bb = b // s
        dd = d // s
        if bb != dd: return c - a + abs(d - b)
        if bb % 3 == 1 and c // s - a // s >= 2:
            l = bb * s - 1
            r = (bb + 1) * s
            return c - a + min(b + d - 2 * l, 2 * r - b - d)
        s //= 3
    return c - a + abs(d - b)

Q = int(input())
for _ in range(Q):
    a, b, c, d = map(int, input().split())
    print(calc(a-1, b-1, c-1, d-1))

Submission status: Runtime Error

Solution code:
i don't understand

Submission status: Runtime Error

Solution code:
def mod3(n):
    b= n
    sho = []
    while b >= 1:
        a = int(b % 3)
        b = int((b - a)/3)
        sho.append(a)
    return sho

def cal_dis(ss,tt):
    s,t = mod3(ss),mod3(tt)
    c = 0
    if len(s) == len(t):
        n = len(s)
        k = 0
        b = 0
        flg =0
        for i in range(n):
            if s[i] == 1 and t[i] == 1:
                k = i+1
                b =2
                flg =1
                if i > 0:
                    c = int(3**(k-1)/2) +1
                    amari = ss % (3^k-1)
                    amari2 = tt%(3^k-1)
                    if amari > (3^k-1)/2:
                        amari = (3^k-1) -amari
                    if amari2 > (3^k-1)/2:
                        amari2 = (3^k-1) -amari2
                    b = amari+2 +amari2 
        if flg == 0:
            a = ss - tt if ss > tt else tt-ss
            return a
        else:
            return b

    else:
        return ss - tt if ss > tt else tt-ss

N = int(input())
dic ={}
for i in range(N):
    dic[i] = [int(a) for a in input().split(' ')]

for i in range(N):
    s = [dic[i][0]-1,dic[i][1]-1]
    t = [dic[i][2]-1,dic[i][3]-1]

    print(cal_dis(s[0],t[0]) + cal_dis(s[1], t[1]))

Submission status: Runtime Error

Solution code:


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

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

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

Submission status: Runtime Error

Solution code:


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

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

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

Submission status: Runtime Error

Solution code:
def mod3(n):
    b= n
    sho = []
    while b >= 1:
        a = int(b % 3)
        b = int((b - a)/3)
        sho.append(a)
    return sho

def cal_dis(ss,tt):
    s,t = mod3(ss),mod3(tt)
    if len(s) == len(t):
        n = len(s)
        k = 0
        for i in range(n):
            if s[i] == 1 and t[i] == 1:
                k = i+1
                if i > 0:
                    b = abs(s[i-1] - t[i-1])
        a = ss - tt if ss > tt else tt-ss
        return a + 2*k - 2* b

    else:
        return ss - tt if ss > tt else tt-ss

N = int(input())
dic ={}
for i in range(N):
    dic[i] = [int(a) for a in input().split(' ')]

for i in range(N):
    s = [dic[i][0]-1,dic[i][1]-1]
    t = [dic[i][2]-1,dic[i][3]-1]


    print(cal_dis(s[0],t[0]) + cal_dis(s[1], t[1]))

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve(ai,aj,bi,bj):
    s=pow(3,30)
    dist=abs(ai-bi)+abs(aj-bj)
    while 1:
        s//=3
        si,sj,ti,tj=ai//s,aj//s,bi//s,bj//s
        if si==sj and ti==tj:continue
        if si!=ti:return dist
        if abs(sj-tj)>1 and si%3==1:
            up=s*(si-1)-1
            down=s*si
            return min(min(ai,bi)-up,down-max(ai,bi))*2+dist

def main():
    q=II()
    for _ in range(q):
        ai,aj,bi,bj=MI1()
        if abs(ai-bi)<abs(aj-bj):ai,aj,bi,bj=bi,bj,ai,aj
        print(solve(ai,aj,bi,bj))

main()

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <cmath>

using namespace std;

long long solve(long long a, long long b, long long c, long long d){
    long long res = abs(a-c) + abs(b-d);
    auto calc = [](long long x1, long long y1, long long x2, long long y2){
        auto sx = x1, sy = y1, gx = x2, gy = y2; 
        long long res = 0;
        long long block = 1;
        for(int i=0;i<30;i++){
            if(sx == gx && sx%3 == 1 && abs(sy - gy) >= 2){
                long long c1 = x1 % block;
                long long c2 = x2 % block;
                res = max(res, min(c1+c2+2, 2*block-c1-c2) + abs(y1 - y2));
            }
            sx /= 3;
            sy /= 3;
            gx /= 3;
            gy /= 3;
            block *= 3;
        }
        return res;
    };
    return max(res, max(calc(a, b, c, d), calc(b, a, d, c)));
}

int main(){
    int Q;
    while(cin >> Q){
        while(Q--){
            long long a, b, c, d;
            cin >> a >> b >> c >> d;
            cout << solve(a-1, b-1, c-1, d-1) << endl;
        }
    }
}

Submission status: Runtime Error

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: 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: Runtime Error

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+(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),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))