Problem p02746 (python)

Fixed submission:
def solve(aa,bb,cc,dd):
  a,b,c,d=aa,bb,cc,dd
  mx=my=0
  for i in range(1,31):
    if a==c and a%3==2 and abs(b-d)>=2:mx=i
    if b==d and b%3==2 and abs(a-c)>=2:my=i
    a=0--a//3
    b=0--b//3
    c=0--c//3
    d=0--d//3
  a,b,c,d=aa,bb,cc,dd
  if mx==my==0:return abs(a-c)+abs(b-d)
  if mx<my:
    ans=abs(a-c)
    mi=3**(my-1)
    ma=2*3**(my-1)+1
    bd=(3**my)*((0--b//(3**my))-1)
    b-=bd
    d-=bd
    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
    ac=(3**mx)*((0--a//(3**mx))-1)
    a-=ac
    c-=ac
    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))

Buggy submission (verdict: Runtime Error):


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

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

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

Buggy submission (verdict: Runtime Error):


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))

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

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

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

Buggy submission (verdict: Runtime Error):

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))

Buggy submission (verdict: Runtime Error):

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))