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
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 - 1] - x1) + (2 * cluster[n - 1] - x2) + 2
                tmp2 = (x1 - cluster[n - 1]) + (x2 - cluster[n - 1])
                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:
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:
            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:
            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 = 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)
        #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)
        #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)
        #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)
        #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())
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
          b %= 3
          continue
      else:
        print(ans)
        break
    if x1//3 == x2//3 and y1//3 == y2//3:
      x1 %= 3
      x2 %= 3
      y1 %= 3
      y2 %= 3
      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,x2%3
  else:
    print(ans)

Submission status: Wrong Answer

Solution code:

def manh(a, b, c, d):
    return abs(a-c)+abs(b-d)

def dist(a, b, c, d):
    for i in range(30):
        if a // 3**(29-i) % 3 == 1 and c // 3**(29-i) % 3 == 1 and (abs(b-d) > 2 * 3 ** (29-i) or (min(b, d) // 3**(29-i) % 3 == 0 and max(b, d) // 3**(29-i) % 3 == 2)):
            return manh(a, b, c, d) + min(abs((a % 3**(30-i)) - (3**(29-i)-1)), abs((c % 3**(30-i)) - (3**(29-i)-1)), abs((a % 3**(30-i)) - (2*3**(29-i))), abs((c % 3**(30-i)) - (2*3**(29-i))))*2
        elif b // 3**(29-i) % 3 == 1 and d // 3**(29-i) % 3 == 1 and (abs(a-c) > 2 * 3 ** (29-i) or (min(a, c) // 3**(29-i) % 3 == 0 and max(a, c) // 3**(29-i) % 3 == 2)):
            return manh(a, b, c, d) + min(abs((b % 3**(30-i)) - (3**(29-i)-1)), abs((d % 3**(30-i)) - (3**(29-i)-1)), abs((b % 3**(30-i)) - (2*3**(29-i))), abs((d % 3**(30-i)) - (2*3**(29-i))))*2
    else:
        return manh(a, b, c, d)







q = int(input())

a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

for i in range(q):
    print(dist(a[i]-1, b[i]-1, c[i]-1, d[i]-1))

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:
        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:
        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:
        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:
        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:
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): #違うクラスターに所属している時
        # 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 - 1] - x1) + (2 * cluster[n - 1] - x2) + 2
                tmp2 = (x1 - cluster[n - 1]) + (x2 - cluster[n - 1])
                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))

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
  if xy=="y":
    return (a<=mi and ma<=c and mi<b<=d<ma)
  else:
    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)+1
    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)+1
    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():
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    for k in range(30, -1, -1):
        if a // 3 ** k == c // 3 ** k and a // 3 ** k % 3 == 1:
            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:
            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:
def calc(n, m, l, k):
    x = 1
    for i in range(30):
        if x <= n < x*2 and x <= m < x*2 and (l < x and x*2 <= k or k < x and x*2 <= l):
            return min((n - x + 1) + (m - x + 1), (x*2 - n) + (x*2 - m))
            break
        x *= 3
    return abs(n-m)


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


if __name__ == "__main__":
    main()

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
        if yy1 == 1 and yy2 == 1 and abs(x1 - x2) > lim:
            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):
    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):
            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):
            ans+=2
    print(ans)

Submission status: Wrong Answer

Solution code:

def x(a, c):
    k = 3 ** 40
    for _ in range(40):
        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:
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(30):
    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:
        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:
        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:
        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:
        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())
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:
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):
            ans+=2
        if 3**(i-1)<bm<=2*3**(i-1) and 3**(i-1)<dm<=2*3**(i-1):
            ans+=2
    print(ans)

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
  if xy=="y":
    return (a<=mi and ma<=c and mi<b<=d<ma)
  else:
    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:
n = int( input() )
l = [list(map(int,input().split())) for i in range(n)]

#print(l)

for i in range(n):
  print(abs(l[i][0] -l[i][2])+ abs(l[i][1]-l[i][3]))

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
  if xy=="x":
    return (a<=mi and ma<=c and mi<b<=d<ma)
  else:
    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:
Q = int(input())
abcd = [list(map(int, input().split())) for _ in range(Q)]
K = 30
for a, b, c, d in abcd:
    detour1 = 0
    tmp = 3**(K)
    for k in range(K, 0, -1):
        tmp //= 3
        # レベルkのフラクタルで同じ行にいなければbreak
        if a//tmp != c//tmp:
            break
        # レベルkのフラクタルで同じマスでいれば次のレベルへ
        if b//tmp != d//tmp:
            continue
        # レベルkのフラクタルで1行目にいなければ次のレベルへ
        if a//tmp != 1:
            continue
        detour1 += 2
    detour2 = 0
    tmp = 3**(K)
    for k in range(K, 0, -1):
        tmp //= 3
        if b//tmp != d//tmp:
            break
        if a//tmp != c//tmp:
            continue
        if b//tmp != 1:
            continue
        detour2 += 2
    print(min(detour1, detour2)+abs(a-c)+abs(b-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
  if xy=="x":
    return (a<=mi and ma<=c and mi<b<=d<=ma)
  else:
    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():
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    for k in range(30):
        if a // 3 ** k == c // 3 ** k == 1 \
                and min((b // 3 ** k), (d // 3 ** k)) == 0 \
                and max((b // 3 ** k), (d // 3 ** k)) == 2:
            print(min(a - 3 ** k + 1 + c - 3 ** k + 1 + abs(b - d),
                2 * 3 ** k - a + 2 * 3 ** k - c + abs(b - d)))
            return
        if b // 3 ** k == d // 3 ** k == 1 \
                and min((a // 3 ** k), (c // 3 ** k)) == 0 \
                and max((a // 3 ** k), (c // 3 ** k)) == 2:
            print(min(b - 3 ** k + 1 + d - 3 ** k + 1 + abs(a - c),
                2 * 3 ** k - b + 2 * 3 ** k - d + 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 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]:
                m = min(abs(b - 3**(29 - i)),abs(b - 3**(29 - i)*2 - 1),abs(d - 3**(29 - i)),abs(d - 3**(29 - i)*2 - 1))
                print(abs(c-a)+abs(d-b) + 2 * m)
            else:
                n = min(abs(a - 3**(29 - i)),abs(a - 3**(29 - i)*2 - 1),abs(c - 3**(29 - i)),abs(c - 3**(29 - i)*2 - 1))
                print(abs(c-a)+abs(d-b) + 2 * n)
            break

Submission status: Wrong Answer

Solution code:

def manh(a, b, c, d):
    return abs(a-c)+abs(b-d)

def dist(a, b, c, d):
    for i in range(30):
        if a // 3**(29-i) % 3 == 1 and c // 3**(29-i) % 3 == 1 and abs(b-d) > 3 ** (29-i):
            return manh(a, b, c, d) + min(abs((a % 3**(30-i)) - (3**(29-i)-1)), abs((c % 3**(30-i)) - (3**(29-i)-1)), abs((a % 3**(30-i)) - (2*3**(29-i))), abs((c % 3**(30-i)) - (2*3**(29-i))))*2
        elif b // 3**(29-i) % 3 == 1 and d // 3**(29-i) % 3 == 1 and abs(a-c) > 3 ** (29-i):
            return manh(a, b, c, d) + min(abs((b % 3**(30-i)) - (3**(29-i)-1)), abs((d % 3**(30-i)) - (3**(29-i)-1)), abs((b % 3**(30-i)) - (2*3**(29-i))), abs((d % 3**(30-i)) - (2*3**(29-i))))*2
    else:
        return manh(a, b, c, d)







q = int(input())

a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

for i in range(q):
    print(dist(a[i]-1, b[i]-1, c[i]-1, d[i]-1))

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:
            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
        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:
            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
        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:
Q = int(input())
abcd = [list(map(int, input().split())) for _ in range(Q)]

for i, (ai, bi, ci, di) in enumerate(abcd):
    pos_a = []
    a_tmp = ai - 1
    for level in range(30):
        pos_a.append(a_tmp % 3)
        a_tmp //= 3
    #
    pos_b = []
    b_tmp = bi - 1
    for level in range(30):
        pos_b.append(b_tmp % 3)
        b_tmp //= 3
    #
    pos_c = []
    c_tmp = ci - 1
    for level in range(30):
        pos_c.append(c_tmp % 3)
        c_tmp //= 3
    #
    pos_d = []
    d_tmp = di - 1
    for level in range(30):
        pos_d.append(d_tmp % 3)
        d_tmp //= 3
    #
    # print("#", pos_a)
    # print("#", pos_b)
    # print("#", pos_c)
    # print("#", pos_d)
    x = y = 0
    for level in range(30):
        x *= 3
        y *= 3
        x += (pos_a[29 - level] - pos_c[29 - level])
        y += (pos_b[29 - level] - pos_d[29 - level])
    #
    print(abs(x) + abs(y))

Submission status: Wrong Answer

Solution code:
def calc(n, m):
    x = 1
    for i in range(30):
        if x <= n < x*2 and x <= m < x*2:
            return min((n - x + 1) + (m - x + 1), (x*2 - n) + (x*2 - m))
            break
        x *= 3
    return abs(n-m)


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


if __name__ == "__main__":
    main()

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):
    # 大きさ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 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)

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 solve(a,b,c,d):
  x1,y1,x2,y2=a,b,c,d
  mx=my=0
  if x1==x2 and x1%3==2:mx=1
  if y1==y2 and y1%3==2:my=1
  for i in range(29):
    x1=0--x1//3
    y1=0--y1//3
    x2=0--x2//3
    y2=0--y2//3
    if x1==x2 and x1%3==2:mx=i+2
    if y1==y2 and y1%3==2:my=i+2
  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(a,b,c,d):
  x1,y1,x2,y2=a,b,c,d
  mx=my=0
  if x1==x2 and x1%3==2:mx=1
  if y1==y2 and y1%3==2:my=1
  for i in range(29):
    x1=0--x1//3
    y1=0--y1//3
    x2=0--x2//3
    y2=0--y2//3
    if x1==x2 and x1%3==2:mx=i+2
    if y1==y2 and y1%3==2:my=i+2
  ans=abs(a-c)+abs(b-d)
  if mx<my:
    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:
    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 ans
  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:
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//(3**(29 - i)))%3
        sb[i] = (b//(3**(29 - i)))%3
        sc[i] = (c//(3**(29 - i)))%3
        sd[i] = (d//(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]:
                m = min(abs(b - 3**(29 - i)),abs(b - 3**(29 - i)*2 - 1),abs(d - 3**(29 - i)),abs(d - 3**(29 - i)*2 - 1))
                print(abs(c-a)+abs(d-b) + 2 * m)
            else:
                n = min(abs(a - 3**(29 - i)),abs(a - 3**(29 - i)*2 - 1),abs(c - 3**(29 - i)),abs(c - 3**(29 - i)*2 - 1))
                print(abs(c-a)+abs(d-b) + 2 * n)
            break

Submission status: Wrong Answer

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 == 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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

def x(a, c):
    k = 3 ** 30
    for _ in range(30):
        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:
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:
q = int(input())

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

Submission status: Wrong Answer

Solution code:

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

Submission status: Wrong Answer

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