Problem:


Score : 600 points

Problem Statement

For a non-negative integer K, we define a fractal of level K as follows:

A fractal of level 0 is a grid with just one white square.

When K > 0, a fractal of level K is a 3^K \times 3^K grid. If we divide this grid into nine 3^{K-1} \times 3^{K-1} subgrids:

The central subgrid consists of only black squares.

Each of the other eight subgrids is a fractal of level K-1.

For example, a fractal of level 2 is as follows:

In a fractal of level 30, let (r, c) denote the square at the r-th row from the top and the c-th column from the left.

You are given Q quadruples of integers (a_i, b_i, c_i, d_i).
For each quadruple, find the distance from (a_i, b_i) to (c_i, d_i).

Here the distance from (a, b) to (c, d) is the minimum integer n that satisfies the following condition:

There exists a sequence of white squares (x_0, y_0), \ldots, (x_n, y_n) satisfying the following conditions:

(x_0, y_0) = (a, b)

(x_n, y_n) = (c, d)

For every i (0 \leq i \leq n-1), (x_i, y_i) and (x_{i+1}, y_{i+1}) share a side.

Constraints

1 \leq Q \leq 10000

1 \leq a_i, b_i, c_i, d_i \leq 3^{30}

(a_i, b_i) \neq (c_i, d_i)

(a_i, b_i) and (c_i, d_i) are white squares.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

Q
a_1 \ b_1 \ c_1 \ d_1
:
a_Q \ b_Q \ c_Q \ d_Q

Output

Print Q lines.
The i-th line should contain the distance from (a_i, b_i) to (c_i, d_i).

Sample Input 1

2
4 2 7 4
9 9 1 9

Sample Output 1

5
8



Sample input:
2
4 2 7 4
9 9 1 9


Sample output:
5
8

Submission status: Wrong Answer

Solution code:
def 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==4 and cd==6:
    ans=abs(b-d)+min(abs(a-m)+abs(c-m),abs(a-mm)+abs(c-mm))
    return [0,ans]
  if ab==2 and cd==8:
    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: Wrong Answer

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

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
        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
        c = int(3**(k-1)/2) +1
        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: Wrong Answer

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)
    b = 0
    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
        k = int(3**(k-1)/2) +1
        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: Wrong Answer

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

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

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)-1
            down=s*si
            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: Wrong Answer

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)-1
            down=s*si
            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=bi,bj,ai,aj
        print(solve(ai,aj,bi,bj))

main()

Submission status: Wrong Answer

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=3*((0--b//m)-1)+(0--a//m)
  cd=3*((0--d//m)-1)+(0--c//m)
  if ab>cd:
    ab,cd=cd,ab
  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: Wrong Answer

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
        a = ss - tt if ss > tt else tt-ss
        return a + 2*k

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

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==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
    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=bi,bj,ai,aj
        print(solve(ai,aj,bi,bj))

main()

Submission status: Wrong Answer

Solution code:
"""
writer:SPD_9X2
https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_f

2点を含む最小の長方形を切り取った時、それが黒によって2つに分断されていない場合、
答えは純粋にマンハッタン距離になる
→証明は…むずいけど

つまり、まずは分断されないか調べることが大事そう？
3**KでKの大きい方から割っていって、問題を小さくする？

xy両方考えるブロックと、片方のみ考えるブロックを分ける
"""

Q = int(input())

for loop in range(Q):

    a,b,c,d = map(int,input().split())
    ans = abs(a-c)+abs(b-d)
    a-=1
    b-=1
    c-=1
    d-=1

    pl = 0
    phaze = 0 #1はxのみ考える、2はyのみ考える
    for i in range(30,-1,-1):

        n = 3**i
        A = a // n
        B = b // n
        C = c // n
        D = d // n

        if (A,B) == (C,D):
            a = a % n
            b = b % n
            c = c % n
            d = d % n
            continue
        elif A != C and B != D:
            break
        elif A == C == 1:

            na = a % n
            nc = c % n
            pl = min(na+nc+2,2*n-na-nc)
            break
        elif A == C:
            phaze = 1
            a %= n
            c %= n
            break
        elif B == D == 1:
            na = b % n
            nc = d % n
            pl = min(na+nc+2,2*n-na-nc)
            break           
        elif B == D:
            phaze = 2
            b %= n
            d %= n
            break

    #print (phaze,a,b,c,d)

    if phaze == 1:

        for i in range(30,-1,-1):

            n = 3**i

            if a // n == c // n == 1:
                na = a % n
                nc = c % n
                pl = min(na+nc+2,2*n-na-nc)
                break

            a %= n
            c %= n

    elif phaze == 2:

        for i in range(30,-1,-1):

            n = 3**i

            if b // n == d // n == 1:
                nb = b % n
                nd = d % n
                pl = min(nb+nd+2,2*n-nb-nd)
                break

            b %= n
            d %= n      

    print (ans + pl)












"""
Q = int(input())

for loop in range(Q):

    a,b,c,d = map(int,input().split())
    a-=1
    b-=1
    c-=1
    d-=1
    ans = abs(a-c) + abs(b-d)

    xflag = False
    yflag = False
    pl = 0

    for i in range(29,-1,-1):

        print (i , a , (3**i) , c , (3**i))
        if xflag:
            pass
        elif a // (3**i) != c // (3**i):
            xflag = True
        elif a // (3**i) == c // (3**i) == 1:

            a2 = a % (3**i)
            c2 = c % (3**i)
            pl = min(a2+c2+2, 2*(3**i)-a2-c2 )
            print ("pl",a2+c2,2*(3**i)-a2-c2)
            break

        if yflag:
            pass
        
        elif b // (3**i) != d // (3**i):
            yflag = True
        elif b // (3**i) == d // (3**i) == 1:

            b2 = b % (3**i)
            d2 = d % (3**i)
            pl = min(b2+d2+2, 2*(3**i)-b2-d2 )
            break

    print (ans , pl)
"""
"""
    for i in range(30,-1,-1):

        

        A = a // (3**i)
        B = b // (3**i)
        C = c // (3**i)
        D = d // (3**i)

        print (A,B,C,D)

        if A != B:
            xflag = True
        elif (not xflag) and A == 1 and B == 1:
            np = (3**(i-1))
            a2 = a % np
            b2 = b % np
            pl = min(a2+b2,2*np-a2-b2)
            print (pl)
            xflag = True
            
        if C != D:
            yflag = True
        elif (not yflag) and C == 1 and D == 1:
            np = (3**(i-1))
            a2 = c % np
            b2 = d % np
            pl = min(a2+b2,2*np-a2-b2)
            yflag = True
            
        if xflag and yflag:
            break

        a = a % (3**i)
        b = b % (3**i)
        c = c % (3**i)
        d = d % (3**i)

    print (ans , pl)   
"""

Submission status: Wrong Answer

Solution code:
"""

2点を含む最小の長方形を切り取った時、それが黒によって2つに分断されていない場合、
答えは純粋にマンハッタン距離になる
→証明は…むずいけど

つまり、まずは分断されないか調べることが大事そう？

3**KでKの大きい方から割っていって、問題を小さくする？
"""

Q = int(input())

for loop in range(Q):

    a,b,c,d = map(int,input().split())
    ans = abs(a-b) + abs(c-d)

    xflag = False
    yflag = False
    pl = 0

    for i in range(30,0,-1):

        A = a % (3**i)
        B = b % (3**i)
        C = c % (3**i)
        D = d % (3**i)

        if A != B:
            xflag = True
        elif (not xflag) and A == 1 and B == 1:
            np = (3**(i-1))
            a2 = a % np
            b2 = b % np
            pl = min(a2+b2,2*np-a2-b2)
            xflag = True
            
        if C != D:
            yflag = True
        elif (not yflag) and C == 1 and D == 1:
            np = (3**(i-1))
            a2 = c % np
            b2 = d % np
            pl = min(a2+b2,2*np-a2-b2)
            yflag = True
            
        if xflag and yflag:
            break

    print (ans + pl)

Submission status: Wrong Answer

Solution code:
q = int(input())

for _ in range(q):
    r1, c1, r2, c2 = map(int, input().split())
    
    r_len = c_len = 3 ** 30
    small_r_len = small_c_len = r_len // 3

    while small_r_len:
        r1_block = (r1 - 1) // small_r_len
        r2_block = (r2 - 1) // small_r_len
        
        if r1_block != r2_block or r1_block == 1:
            break
        
        r1 %= r_len
        r2 %= r_len
        
        r_len = small_r_len
        small_r_len //= 3
    
    while small_c_len:
        c1_block = (c1 - 1) // small_c_len
        c2_block = (c2 - 1) // small_c_len
        
        if c1_block != c2_block or c1_block == 1:
            break
        
        c1 %= c_len
        c2 %= c_len
        
        c_len = small_c_len
        small_c_len //= 3
    
    if r1_block == r2_block == 1 and {c1_block, c2_block} == {0, 2}:
        dist = abs(c1 - c2) + min(r1 + r2 - (small_r_len << 1), (small_r_len << 2) - r1 - r2 + 2)
    elif c1_block == c2_block == 1 and {r1_block, r2_block} == {0, 2}:
        dist = abs(r1 - r2) + min(c1 + c2 - (small_c_len << 1), (small_c_len << 2) - c1 - c2 + 2)
    else:
        dist = abs(r1 - r2) + abs(c1 - c2)
    
    print(dist)

Submission status: Wrong Answer

Solution code:
q = int(input())

for _ in range(q):
    r1, c1, r2, c2 = map(int, input().split())
    
    r_len = c_len = 3 ** 30
    small_r_len = small_c_len = r_len // 3

    while small_r_len:
        r1_block = (r1 - 1) // small_r_len
        r2_block = (r2 - 1) // small_r_len
        
        if r1_block != r2_block or r1_block == 1:
            break
        
        r1 %= r_len
        r2 %= r_len
        
        r_len = small_r_len
        small_r_len //= 3
    
    while small_c_len:
        c1_block = (c1 - 1) // small_c_len
        c2_block = (c2 - 1) // small_c_len
        
        if c1_block != c2_block or c1_block == 1:
            break
        
        c1 %= c_len
        c2 %= c_len
        
        c_len = small_c_len
        small_c_len //= 3
    
    if r1_block == r2_block == 1:
        dist = abs(c1 - c2) + min(r1 + r2 - (small_r_len << 1), (small_r_len << 2) - r1 - r2 + 2)
    elif c1_block == c2_block == 1:
        dist = abs(r1 - r2) + min(c1 + c2 - (small_c_len << 1), (small_c_len << 2) - c1 - c2 + 2)
    else:
        dist = abs(r1 - r2) + abs(c1 - c2)
    
    print(dist)

Submission status: Wrong Answer

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

def cond1(a,b,i):
    g = 3 ** i
    con1_1 = (a // g) == (b // g)
    con1_2 = ((a % (3*g)) // g) == 1
    con1_3 = ((b % (3*g)) // g) == 1
    dx = 2*min((a % (3*g)) - g + 1, 
             (b % (3*g)) - g + 1,
             2*g - (a % (3*g)),
             2*g - (b % (3*g)))
    return con1_1 & con1_2 & con1_3, dx

def cond2(cc, dd, ii):
    gg = 3 ** ii
    st = min(cc,dd)
    ed = max(cc,dd)
    for jj in range(st+1, ed):
        if ((jj % (3*gg)) // gg) == 1:
            return True
    return False

def calc(a,b,c,d):
    a-=1
    b-=1
    c-=1
    d-=1
    md = abs(a-c) + abs(b-d)
    dx = 0
    for j in range(4):
        c1, dx = cond1(a,c,j)
        if c1:
            if cond2(b,d,j):
                return md + dx
        c1, dx = cond1(b,d,j)
        if c1:
            if cond2(a,c,j):
                return md + dx
    return md

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

Submission status: Wrong Answer

Solution code:
import sys
q = int(input())

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))
    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
        i1, i2 = p1[0] % c, p2[0] % c
        xp = min(i1 + i2 + 2, 2 * c - i1 - i2)
        return xp + abs(p1[1] - p2[1])
    if level == 0:
        return abs(p1[0] - p2[0]) + 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])

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
q = int(input())

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))
    g1, g2 = grid(p1, level), grid(p2, level)
    if g1[0] != g2[0]:
        return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    if g1[0] == 1:
        c = 3 ** level
        i1, i2 = p1[0] % c, p2[0] % c
        xp = min(i1 + i2 + 2, 2 * c - i1 - i2)
        return xp + abs(p1[1] - p2[1])
    if level == 0:
        return abs(p1[0] - p2[0]) + 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])

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

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

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 = (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(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:
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)
                else: return dist(a,b%L,c,d-(p-2)*L,n)+(p-2)*L
            elif a//L==1:
                if area2==1 and a12==5 and a22==3:
                    return dist(a-L,b-2*L,c-L,d-2*L,n)
                else:
                    return min(a+c-2*(L-1),4*L-a-c)+abs(b-d)
            elif a//L==2: return dist(a-2*L,b,c-2*L,d,n)

        else: return 0

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



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