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:
from collections import defaultdict, Counter, deque


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):
            axis = None
            if a == c == 1:
                axis = 0
            elif b == d == 1:
                axis = 1
            if axis is not None:
                move1 = sum(
                    (source[l][axis] + dest[l][axis]) * (3 ** l) for l in range(level)
                )
                move2 = sum(
                    (3 - source[l][axis] + 3 - 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:

def check(lv,aa,bb,cc,dd,xy):
  a,b,c,d=aa,bb,cc,dd
  if a>c:a,c=c,a
  if b>d:b,d=d,b
  mi=3**(lv-1)
  ma=2*3**(lv-1)+1
  aa=0--a//3
  bb=0--b//3
  cc=0--c//3
  dd=0--d//3
  if xy=="y":
    if bb==dd and bb%3==2:return False
    return (a<=mi and ma<=c and mi<b<=d<ma)
  else:
    if aa==cc and cc%3==2:return False
    return (b<=mi and ma<=d and mi<a<=c<ma)
def solve(a,b,c,d):
  mx=my=0
  for i in range(1,31):
    if check(i,a,b,c,d,"x"):mx=i
    if check(i,a,b,c,d,"y"):my=i
  if mx<my:
    ans=abs(a-c)
    mi=3**(my-1)
    ma=2*3**(my-1)+1
    ans+=min(abs(mi-b)+abs(mi-d),abs(ma-b)+abs(ma-d))
    return ans
  if mx>my:
    ans=abs(b-d)
    mi=3**(mx-1)
    ma=2*3**(mx-1)+1
    ans+=min(abs(mi-a)+abs(mi-c),abs(ma-a)+abs(ma-c))
    return ans
  if mx==my==0:return abs(a-c)+abs(b-d)
  ans=1/0#正しければ実行されないはず
q=int(input())
for _ in range(q):
  a,b,c,d=map(int,input().split())
  print(solve(a,b,c,d))

Submission status: Wrong Answer

Solution code:
def solve(q, abc_list):
    res_list = [0] * q
    for i in range(q):
        a, b, c, d = abc_list[i]
        a, b, c, d = a - 1, b - 1, c - 1, d - 1
        a2, b2, c2, d2 = a, b, c, d
        k1 = 29
        flag = 0
        while k1 >= 0:
            if 3 ** k1 <= a2 < 2 * 3 ** k1 and 3 ** k1 <= c2 < 2 * 3 ** k1:
                if min(b2, d2) < 3 ** k1 and 2 * 3 ** k1 <= max(b2, d2):
                    flag = 1
                    break
            elif 3 ** k1 <= b2 < 2 * 3 ** k1 and 3 ** k1 <= d2 < 2 * 3 ** k1:
                if min(a2, c2) < 3 ** k1 and 2 * 3 ** k1 <= max(a2, c2):
                    flag = 2
                    break
            elif a2 // (3 ** k1) != c2 // (3 ** k1) and a2 // (3 ** k1) != c2 // (3 ** k1):
                k1 = -1
                break
            a2, b2, c2, d2 = a2 % 3, b2 % 3, c2 % 3, d2 % 3
            k1 -= 1

        add = 0

        if flag == 1:
            add = min(a2 - 3 ** k1 + 1 + c2 - 3 ** k1 + 1, 2 * (3 ** k1) - a2 + 2 * (3 ** k1) - c2)
        elif flag == 2:
            add = min(b2 - 3 ** k1 + 1 + d2 - 3 ** k1 + 1, 2 * (3 ** k1) - b2 + 2 * (3 ** k1) - d2)
        res_list[i] = abs(a - c) + abs(b - d) + add
    return res_list


def main():
    q = int(input())
    abc_list = [list(map(int, input().split())) for _ in range(q)]
    res_list = solve(q, abc_list)
    for r in res_list:
        print(r)


def test():
    assert solve(2, [[4, 2, 7, 4], [9, 9, 1, 9]]) == [5, 8]


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
import sys


def solve(a, b, c, d):
    """ Lv.i の中央の■を、上下(a,c)に迂回する """
    for i in range(3, 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: 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)

    aaa = 0
    i = 0
    while i < 30 and A[i] == C[i]:
        if (((B[i], D[i]) == (0,2) or\
            (B[i], D[i]) == (2,0)) and A[i]==1):
            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 (((A[i], C[i]) == (0,2) or\
            (A[i], C[i]) == (2,0)) and B[i]==1):
            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 = input()
for q in range(Q):
  a, b, c, d = map(int, raw_input().split())
  a -= 1
  b -= 1
  c -= 1
  d -= 1
  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 = (b+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 = (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 = (a+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 = (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(mny, rx-1)
        mxx = max(mxy, rx+s/3)
        #print "d", k, s, rx, ry
    s *= 3
  print min(a-mnx+c-mnx, mxx-a+mxx-c)+min(b-mny+d-mny, mxy-b+mxy-d)

Submission status: Wrong Answer

Solution code:
Q = int(input())
abcd = [list(map(int, input().split())) for _ in range(Q)]
K = 30
for a, b, c, d in abcd:
    a_tmp, b_tmp, c_tmp, d_tmp = a-1, b-1, c-1, d-1
    detour = 0
    dist = abs(a_tmp-c_tmp)+abs(b_tmp-d_tmp)
    tmp = 3**(K-1)
    for k in range(K-1):
        a_tmp, b_tmp, c_tmp, d_tmp = a_tmp%tmp, b_tmp%tmp, c_tmp%tmp, d_tmp%tmp
        tmp //= 3
        # レベルkのフラクタルで同じ行にいなければbreak
        if a_tmp//tmp != c_tmp//tmp:
            break
        # レベルkのフラクタルで同じマスにいれば次のレベルへ
        if b_tmp//tmp == d_tmp//tmp:
            continue
        # レベルkのフラクタルで1行目にいなければ次のレベルへ
        if a_tmp//tmp != 1:
            continue
        detour += 2
    if detour > 0:
        print(detour+dist)
        continue
    a_tmp, b_tmp, c_tmp, d_tmp = a-1, b-1, c-1, d-1
    tmp = 3**(K-1)
    for k in range(K-1):
        a_tmp, b_tmp, c_tmp, d_tmp = a_tmp%tmp, b_tmp%tmp, c_tmp%tmp, d_tmp%tmp
        tmp //= 3
        if b_tmp//tmp != d_tmp//tmp:
            break
        if a_tmp//tmp == c_tmp//tmp:
            continue
        if b_tmp//tmp != 1:
            continue
        detour += 2
    print(detour+dist)

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)

    aaa = 0
    i = 0
    while i < 30 and A[i] == C[i]:
        if (((B[i], D[i]) == (0,2) or\
            (B[i], D[i]) == (2,0)) and A[i]==1):
            aaa = g(A[i+1:],C[i+1:]) if i != 30 else 1
            break
        i += 1
    while i < 30 and B[i] == D[i]:
        if (((A[i], C[i]) == (0,2) or\
            (A[i], C[i]) == (2,0)) and B[i]==1):
            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:
import math
Q = int(input())
for i in range(Q):
    a, b, c, d = map(int, input().split())
    if abs(a - c) > abs(b - d):
        a, b, c, d = b, a, d, c
    dist = abs(a - c) + abs(b - d)
    start_level = math.ceil(math.log(abs(a - c) + 1, 3)) + 1
    end_level = math.ceil(math.log(abs(b - d) + 1, 3)) + 1
    for level in reversed(range(start_level, end_level)):
        p = a % 3 ** level
        q = c % 3 ** level
        if (p // 3 ** (level - 1) == 1 and q // 3 ** (level - 1) == 1):
            dist = min(p + q - 2 * (3 ** (level - 1) - 1), 4 * (3 ** (level - 1)) - p - q)
            dist += abs(b - d)
            break
    print(dist)

Submission status: Wrong Answer

Solution code:
q = int(input())
for _ in range(q):
  x1,y1,x2,y2 = map(lambda x:int(x)-1,input().split())
  ans = abs(x1-x2) + abs(y1-y2)
  att = 0
  for d in range(30):
    if att == 1:
      if a//3 == b//3:
        if a//3 == 1:
          can = []
          can.append(a//(3**(29-d))+1)
          can.append(-b//(3**(29-d))+1)
          print(ans+min(can))
          break
        else:
          a %= 3**(29-d)
          b %= 3**(29-d)
          continue
      else:
        print(ans)
        break
    if x1//3 == x2//3 and y1//3 == y2//3:
      x1 %= 3**(29-d)
      x2 %= 3**(29-d)
      y1 %= 3**(29-d)
      y2 %= 3**(29-d)
      continue
    elif x1//3 != x2//3 and y1//3 != y2//3:
      print(ans)
      break
    if x1//3 != x2//3 and y1//3 == y2//3:
      x1,x2,y1,y2 = y1,y2,x1,x2
    if x1 > x2:
      x1,x2 = x2,x1
    if x1//3 == 1:
      can = []
      can.append(x1//(3**(29-d))+1)
      can.append(-x2//(3**(29-d)))
      print(ans+min(can))
      break
    else:
      att = 1
      a,b = x1%(3**(29-d)),x2%(3**(29-d))
  else:
    print(ans)

Submission status: Wrong Answer

Solution code:
def isblack(x,y):
    K=30
    p,q=x,y
    while(K>0):
        L=3**(K-1)
        pp=p//L
        qq=q//L
        if (pp,qq)==(1,1):
            return True
        p=p%L
        q=q%L
        K-=1
    return False
def existblackpoint(a,p,q):
    print(a,p,q)
    #(a,p)->(a,q)
    K=30
    while(K>0):
        L=3**(K-1)
        x,y=min(p,q),max(p,q)
        xx,yy=x//L,y//L
        if x%L==0 and y-x==L-1:
            if isblack(a,x+L//3):
                return True
            else:
                return False
        if yy==xx:
            continue
        elif yy-xx==1:
            if existblackpoint(a,x,(xx+1)*L-1)==False and existblackpoint(a,(yy+1)*L,y)==False:
                return False
            else:
                return True
        elif yy-xx==2:
            if existblackpoint(a,x,L-1)==False and existblackpoint(a,L,2*L-1)==False and existblackpoint(a,2*L,y)==False:
                return False
            else:
                return True

        K-=1
#print(existblackpoint(8,0,8))
def dist(K,a,b,c,d):
    #print(K,a,b,c,d)
    L=3**(K-1)
    aa=a//L
    bb=b//L
    cc=c//L
    dd=d//L
    if aa==cc and bb==dd:
        return dist(K-1,a%L,b%L,c%L,d%L)
    elif aa==cc and bb!=dd:
        if a==c:
            if isblack(a,a):
                pass
            else:
                return abs(a-c)+abs(b-d)
        if aa!=1:
            return abs(a-c)+abs(b-d)
        else:
            ans=L*10
            for x,y in [(2*L,L),(L-1,L)]:
                ans=min(ans,abs(a-x)+abs(x-c)+abs(b-y)+abs(y-d))
            return ans
    elif aa!=cc and bb==dd:
        if bb!=1:
            return abs(a-c)+abs(b-d)
        else:
            ans=L*10
            for x,y in [(L,2*L),(L,L-1)]:
                ans=min(ans,abs(a-x)+abs(x-c)+abs(b-y)+abs(y-d))
            return ans
    else:
        return abs(a-c)+abs(b-d)
Q=int(input())
for i in range(Q):
    p,q,r,s=map(int,input().split())
    #print(30,p,q,r,s,"##")
    print(dist(30,p-1,q-1,r-1,s-1))

Submission status: Wrong Answer

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):
        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:
            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
        if b // 3 ** k == d // 3 ** k and b // 3 ** k % 3 == 1 \
                and min(a, c) // 3 ** k % 3 == 0 and max(a, c) // 3 ** k % 3 == 2:
            print(min(b % 3 ** k + 1 + d % 3 ** k + 1 + abs(a - c),
                3 ** k - b % 3 ** k + 3 ** k - d % 3 ** k + abs(a - c)))
            return
    print(abs(a - c) + abs(b - d))

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

Submission status: Wrong Answer

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

    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):
        # 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
        return min(aa+1, k-aa, bb+1, k-bb)

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

Submission status: Wrong Answer

Solution code:
#def f(x,y,n):
#    for i in range(n):
#        if x%3 == 1 and y%3 == 1:
#            return False
#        x //= 3
#        y //= 3
#    return True
#
#n = 3
#sz = 3**n
#for y in range(sz):
#    print(''.join('x '[f(x,y,n)] for x in range(sz)))

def which_hit_x(x1,y1,x2,y2):
    for level in reversed(range(30)):
        yy1 = y1//3**level % 3
        yy2 = y2//3**level % 3
        lim = 3**level
        xx1 = x1//3**(level+1)
        xx2 = x2//3**(level+1)
        xx1,xx2 = sorted([xx1, xx2])
        asd = (xx2 - xx1 == 1) and x1%(3**(level+1)) > 2*lim - 1 and x2%(3**(level+1)) < lim
        if yy1 == 1 and yy2 == 1 and abs(x1 - x2) > lim and not asd:
            return level
    return -1

t = int(input())

for _ in range(t):
    x1,y1,x2,y2 = [int(x)-1 for x in input().split()]
    hit_x = which_hit_x(x1,y1,x2,y2)
    hit_y = which_hit_x(y1,x1,y2,x2)

    if hit_x == hit_y == -1:
        print(abs(x1 - x2) + abs(y1 - y2))
    elif hit_x != -1:
        sz = (3**hit_x)
        y1 %= sz
        y2 %= sz
        print(abs(x1 - x2) + min(y1 + 1 + y2 + 1, sz - y1 + sz - y2))
    elif hit_y != -1:
        sz = (3**hit_y)
        x1 %= sz
        x2 %= sz
        print(abs(y1 - y2) + min(x1 + 1 + x2 + 1, sz - x1 + sz - x2))

#def common_size(x1,y1,x2,y2):
#    sz = 0
#    while x1 != x2 or y1 != y2:
#        x1 //= 3
#        y1 //= 3
#        x2 //= 3
#        y2 //= 3
#        sz += 1
#    return sz
#
#print(common_size(3,0, 5,0))

Submission status: Wrong Answer

Solution code:
q = int(input()) 

def hoge(x):
  y = x
  res = []
  for i in range(30):
    res.append(y % 3 == 1)
    y = y // 3
  return res

def fuga(la, lb):
  res = -1
  for i, (a, b) in enumerate(zip(la, lb)):
    if a and b:
      res = i
  return res

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

  x =  fuga(hoge(a), hoge(c))
  y =  fuga(hoge(b), hoge(d))
  if x == -1 and y == -1:
    pass
  elif x > y:
    z = 3 ** x - 1
    w = 3 ** (x - 1)
    piyo = min(min(abs(z - a), abs(w - a)), min(abs(z - c), abs(w - c)))
    ans += 2 * piyo
  elif y > x:
    z = 3 ** y - 1
    w = 3 ** (y - 1)
    piyo = min(min(abs(z - b), abs(w - b)), min(abs(z - d), abs(w - d)))
    ans += 2 * piyo
  else:
    raise ValueError()

  print(ans)

Submission status: Wrong Answer

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

    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):
        # 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
        return min(aa+1, k-aa, bb+1, k-bb)

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

Submission status: Wrong Answer

Solution code:
Q = input()
for q in range(Q):
  a, b, c, d = map(int, raw_input().split())
  a -= 1
  b -= 1
  c -= 1
  d -= 1
  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 = (b+s/3)/s*s+s/3
      if rx+s/3<=c and ry+s/3>d:
        mny = min(mny, ry-1)
        mxy = max(mxy, ry+s/3-1)
        #print "a", k, s, rx, ry
    else:
      rx = (c+s/3*2)/s*s+s/3
      ry = (d+s/3)/s*s+s/3
      if rx+s/3<=a and ry+s/3>b:
        mny = min(mny, ry-1)
        mxy = max(mxy, ry+s/3-1)
        #print "b", k, s, rx, ry
    if b<d:
      rx = (a+s/3)/s*s+s/3
      ry = (b+s/3*2)/s*s+s/3
      if ry+s/3<=d and rx+s/3>c:
        mnx = min(mnx, rx-1)
        mxx = max(mxx, rx+s/3-1)
        #print "c", k, s, rx, ry
    else:
      rx = (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>a:
        mnx = min(mny, rx-1)
        mxx = max(mxy, rx+s/3-1)
        #print "d", k, s, rx, ry
    s *= 3
  print min(a-mnx+c-mnx, mxx-a+mxx-c)+min(b-mny+d-mny, mxy-b+mxy-d)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)

input = sys.stdin.readline

cluster = [1]
cluster_append = cluster.append
for _ in range(30):
    cluster_append(cluster[-1] * 3)

def check(x1, x2, n = 29): #同じクラスターの時 True, 違う時 False
    if n == 0:
        return False
    if (x1 <= cluster[n] and x2 <= cluster[n]) or (cluster[n] < x1 <= 2 * cluster[n] and cluster[n] < x2 <= 2 * cluster[n]) or (2 * cluster[n] < x1 and 2 * cluster[n] < x2):
        return True
    return False

def calc(x1, x2, y1, y2, n = 29):
    if not check(x1, x2, n): #違うクラスターに所属している時
        if n == 0 and x1 % 3 == 2:
            return 2
        # print ('A')
        return abs(x1 - x2)
    else: #同じクラスターの時
        # print ('B')
        if cluster[n] < x1 <= 2 * cluster[n]: #真ん中のクラスターに入っている時
            # print ('B-1')
            if check(y1, y2, n): #yも同じクラスターに入っている時
                return calc(x1, x2, y1, y2, n - 1)
            else: #yが上と下のクラスターに入っている時
                tmp1 = (2 * cluster[n] - x1) + (2 * cluster[n] - x2) + 2
                tmp2 = (x1 - cluster[n]) + (x2 - cluster[n])
                tmp = min(tmp1, tmp2)
                return tmp
        else: #端のクラスターに入っている時
            return calc(x1, x2, y1, y2, n - 1)

# print (cluster)
# print (len(cluster))
# print (check(4, 7, 1))

# print (calc(4, 7, 2, 3, 1))
# print ()
# print (calc(2, 3, 4, 7, 1))

Q = int(input())
for _ in range(Q):
    x1, y1, x2, y2 = map(int, input().split())
    print (calc(x1, x2, y1, y2) + calc(y1, y2, x1, x2))
    # print (calc(x1, x2, y1, y2), calc(y1, y2, x1, x2))

Submission status: Wrong Answer

Solution code:
q = int(input())
for _ in range(q):
  x1,y1,x2,y2 = map(lambda x:int(x)-1,input().split())
  ans = abs(x1-x2) + abs(y1-y2)
  att = 0
  for d in range(30):
    if att == 1:
      if a//3 == b//3:
        if a//3 == 1:
          can = []
          can.append(a//(3**(29-d))+1)
          can.append(-b//(3**(29-d)))
          print(ans+min(can))
          break
        else:
          a %= 3**(29-d)
          b %= 3**(29-d)
          continue
      else:
        print(ans)
        break
    if x1//3 == x2//3 and y1//3 == y2//3:
      x1 %= 3**(29-d)
      x2 %= 3**(29-d)
      y1 %= 3**(29-d)
      y2 %= 3**(29-d)
      continue
    elif x1//3 != x2//3 and y1//3 != y2//3:
      print(ans)
      break
    if x1//3 != x2//3 and y1//3 == y2//3:
      x1,x2,y1,y2 = y1,y2,x1,x2
    if x1 > x2:
      x1,x2 = x2,x1
    if x1//3 == 1:
      can = []
      can.append(x1//(3**(29-d))+1)
      can.append(-x2//(3**(29-d)))
      print(ans+min(can))
      break
    else:
      att = 1
      a,b = x1%(3**(29-d)),x2%(3**(29-d))
  else:
    print(ans)

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 or A[i]==C[i]==2:
            continue
            
        elif A[i]==C[i]==1:
            if abs(b-d)<=3**i:
                continue
            else:
                aaa=a%3**(i+1)
                ccc=c%3**(i+1)
                num1=aaa-3**i+1+ccc-3**i+1
                num2=2*3**i-aaa+2*3**i-ccc
                ans+=min(num1,num2)
                break
                
        else:
            ans+=abs(a-c)
            break
    for i in range(30,-1,-1):
        if B[i]==D[i]==0 or B[i]==D[i]==0:
            continue
            
        elif B[i]==D[i]==1:
            if abs(a-c)<=3**i:
                continue
            else:
                bbb=b%3**(i+1)
                ddd=d%3**(i+1)
                num1=bbb-3**i+1+ddd-3**i+1
                num2=2*3**i-bbb+2*3**i-ddd
                ans+=min(num1,num2)
                break
                
        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:
#def f(x,y,n):
#    for i in range(n):
#        if x%3 == 1 and y%3 == 1:
#            return False
#        x //= 3
#        y //= 3
#    return True
#
#n = 3
#sz = 3**n
#for y in range(sz):
#    print(''.join('x '[f(x,y,n)] for x in range(sz)))

def which_hit_x(x1,y1,x2,y2):
    for level in reversed(range(30)):
        yy1 = y1//3**level % 3
        yy2 = y2//3**level % 3
        lim = 3**level
        xx1 = x1//3**(level+1)
        xx2 = x2//3**(level+1)
        xx1,xx2 = sorted([xx1, xx2])
        asd = (xx2 - xx1 == 1) and x1%(3**(level+1)) > 2*lim - 1 and x2%(3**(level+1)) < lim
        if yy1 == 1 and yy2 == 1 and abs(x1 - x2) > lim and asd:
            return level
    return -1

t = int(input())

for _ in range(t):
    x1,y1,x2,y2 = [int(x)-1 for x in input().split()]
    hit_x = which_hit_x(x1,y1,x2,y2)
    hit_y = which_hit_x(y1,x1,y2,x2)

    if hit_x == hit_y == -1:
        print(abs(x1 - x2) + abs(y1 - y2))
    elif hit_x != -1:
        sz = (3**hit_x)
        y1 %= sz
        y2 %= sz
        print(abs(x1 - x2) + min(y1 + 1 + y2 + 1, sz - y1 + sz - y2))
    elif hit_y != -1:
        sz = (3**hit_y)
        x1 %= sz
        x2 %= sz
        print(abs(y1 - y2) + min(x1 + 1 + x2 + 1, sz - x1 + sz - x2))

#def common_size(x1,y1,x2,y2):
#    sz = 0
#    while x1 != x2 or y1 != y2:
#        x1 //= 3
#        y1 //= 3
#        x2 //= 3
#        y2 //= 3
#        sz += 1
#    return sz
#
#print(common_size(3,0, 5,0))

Submission status: Wrong Answer

Solution code:
q = int(input())
for _ in range(q):
  x1,y1,x2,y2 = map(lambda x:int(x)-1,input().split())
  ans = abs(x1-x2) + abs(y1-y2)
  att = 0
  for d in range(30):
    if att == 1:
      if a//3 == b//3:
        if a//3 == 1:
          can = []
          can.append(a//(3**(29-d))+1)
          can.append(-b//(3**(29-d)))
          print(ans+min(can))
          break
        else:
          a %= 3**(29-d)
          b %= 3**(29-d)
          continue
      else:
        print(ans)
        break
    if x1//3 == x2//3 and y1//3 == y2//3:
      x1 %= 3**(29-d)
      x2 %= 3**(29-d)
      y1 %= 3**(29-d)
      y2 %= 3**(29-d)
      continue
    elif x1//3 != x2//3 and y1//3 != y2//3:
      print(ans)
      break
    if x1//3 != x2//3 and y1//3 == y2//3:
      x1,x2,y1,y2 = y1,y2,x1,x2
    if x1 > x2:
      x1,x2 = x2,x1
    if x1//3 == 1:
      can = []
      can.append(x1//(3**(29-d))+1)
      can.append(-x2//(3**(29-d)))
      print(ans+min(can))
      break
    else:
      att = 1
      a,b = x1%3**(29-d),x2%3**(29-d)
  else:
    print(ans)

Submission status: Wrong Answer

Solution code:
q = int(input())

for _ in range(q):
    a,b,c,d = map(int,input().split())
    ans=abs(c-a)+abs(d-b)
    for i in range(1,31):
        am=a%(3**i)
        bm=b%(3**i)
        cm=c%(3**i)
        dm=d%(3**i)
        if 3**(i-1)<am<=2*3**(i-1) and 3**(i-1)<cm<=2*3**(i-1) and a//(3**i) == c//(3**i) and b//(3**(i-1)) != d//(3**(i-1)):
            ans+=2
        if 3**(i-1)<bm<=2*3**(i-1) and 3**(i-1)<dm<=2*3**(i-1) and b//(3**i) == d//(3**i) and a//(3**(i-1)) != c//(3**(i-1)) :
            ans+=2
    print(ans)

Submission status: Wrong Answer

Solution code:
Q = int(input())
for i in range (Q):
    a,b,c,d = list(map(int,input().split()))
    sa = [0]*30
    sb = [0]*30
    sc = [0]*30
    sd = [0]*30
    for i in range (30):
        sa[i] = ((a-1)//(3**(29 - i)))%3
        sb[i] = ((b-1)//(3**(29 - i)))%3
        sc[i] = ((c-1)//(3**(29 - i)))%3
        sd[i] = ((d-1)//(3**(29 - i)))%3
    for i in range(30):
        if sa[i] != sc[i] or sb[i] != sd[i]:
            if sa[i] + sc[i] != 2 or sb[i] + sd[i] != 2:
                print(abs(c-a)+abs(d-b))
            elif sa[i] != sc[i] and sb[i] != sd[i]:
                print(abs(c-a)+abs(d-b))
            elif sa[i] != sc[i]:
                k = (b-1) % (3**(29 - i))
                l = min(k+1,3**(29-i)-k)
                m = (d-1) % (3**(29 - i))
                n =  min(m+1,3**(29-i)-m)
                print(abs(c-a)+abs(d-b) + 2 * min(l,n))
            else:
                k = (a-1) % (3**(29 - i))
                l = min(k+1,3**(29-i)-k)
                m = (c-1) % (3**(29 - i))
                n =  min(m+1,3**(29-i)-m)
                print(abs(c-a)+abs(d-b) + 2 * min(l,n))
            break

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 and dy==2:
            if dyy == 1:
                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 dx==2 and y1==y2==1:
            if dxx == 1:
                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)