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

Solution code:
import sys
input=sys.stdin.readline

def dist(a,b,c,d,P3):
    for p in P3:
        da,ma=divmod(a,p)
        dc,mc=divmod(c,p)
        if da!=dc:
            return abs(a-c)+abs(b-d)
        if da!=1:
            a,c=ma,mc
            continue
        db,mb=divmod(b,p)
        dd,md=divmod(d,p)
        if db==dd:
            a,c=ma,mc
            continue
        return min(ma+mc+2,2*pi-(ma+mc))+abs(b-d)
    return abs(b-d)

def main():
    q=int(input())
    P3=[pow(3,i) for i in reversed(range(30))]
    for _ in range(q):
        a,b,c,d=map(lambda x: int(x)-1,input().split())
        print(max(dist(a,b,c,d,P3),dist(b,a,d,c,P3)))

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
 Q = int(input())
abcd = []
while(Q):
    Q -= 1
    abcd.append(list(map(int,input().split(" "))))
def distance(p,q):
    return abs(p[0]-q[0])+abs(p[1]-q[1])
  
n = 3**29
for a,b,c,d in abcd:
    P = (a,b)
    Q = (c,d)
    m = n
    while(m > 3**-1):
        x,y,z,w = P[0]//m,P[1]//m,Q[0]//m,Q[0]//m
        if(x == z and y == w):
            P,Q = (P[0]%m,P[1]%m),(Q[0]%m,Q[1]%m)
            m //= 3
            continue
        elif(x == z and z == 1):
            dd = distance((a,b),(c,d))+2*min(P[0],m-P[0],Q[0],m-Q[0])
            print(dd)
            break
        elif( y == w and y == 1):
            dd = distance((a,b),(c,d))+2*min(P[1],m-P[1],Q[1],m-Q[1])
            print(dd)
            break
        else:
            print(distance((a,b),(c,d)))
            break

Submission status: Runtime Error

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 b==d and b%3=2:return False
    return (a<=mi and ma<=c and mi<b<=d<ma)
  else:
    if a==c and c%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: Runtime Error

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

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 b==d and b%3=2:return False
    return (a<=mi and ma<=c and mi<b<=d<ma)
  else:
    if a==c and c%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: Runtime Error

Solution code:
Q = int(input())
abcd = []
while(Q):
    Q -= 1
    abcd.append(list(map(int,input().split(" "))))
 
def d(p,q):
    return abs(p[0]-q[0])+abs(p[1]-q[1])
  

for a,b,c,d in abcd:
    P = (a,b)
    Q = (c,d)
    m = 3**29
    while(m > 3):
        x,y,z,w = P[0]//m,P[1]//m,Q[0]//m,Q[0]//m
        if(x == z and y == w):
            m /= 3
            P,Q = (P[0]%m,P[1]%m),(Q[0]%m,Q[1]%m)
            continue
        elif(x == z and z == 1):
            dd = d((a,b),(c,d))+2*min(P[0],m-P[0],Q[0],m-Q[0])
            print(dd)
        elif( y == w and y == 1):
            dd = d((a,b),(c,d))+2*min(P[1],m-P[1],Q[1],m-Q[1])
            print(dd)
        else:
            print(d((a,b),(c,d)))

Submission status: Runtime Error

Solution code:
Q = int(input())
abcd = []
while(Q):
    Q -= 1
    abcd.append(list(map(int,input().split(" "))))

def d(p,q):
    return abs(p[0]-q[0])+abs(p[1]-q[1])
  
  
for a,b,c,d in abcd:
    m = 3**29
    while(m > 3):
        x,y,z,w = P[0]//m,P[1]//m,Q[0]//m,Q[0]//m
        if(x == z and y == w):
            m /= 3
            P,Q = P%m,Q%m
            continue
        elif(x == z and z == 1):
            dd = d((a,b),(c,d))+2*min(P[0],m-P[0],Q[0],m-Q[0])
            print(dd)
        elif( y == w and y == 1):
            dd = d((a,b),(c,d))+2*min(P[1],m-P[1],Q[1],m-Q[1])
            print(dd)
        else:
            print(d((a,b),(c,d)))

Submission status: Runtime Error

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

Solution code:
count = int(input())
list = [1 * count]

index = 0
while index < n:
  a,b,c,d = (int(x) for x in input().split())
  list[index] = [a,b,c,d]
  index += 1

answer = [1 * count]

i = 0
while i < n:
  answer[i] = abs(list[i][2]-list[i][0]) + abs(list[i][3] - list[i][1])

j=0
while j < n:
  print(answer[j])

Submission status: Runtime Error

Solution code:
print "5"
print "8"

Submission status: Runtime Error

Solution code:
a = "2"
print "5"
print "8"