結果

問題 No.2287 ++ -- *=a /=a
ユーザー とりゐとりゐ
提出日時 2023-04-28 23:45:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,467 bytes
コンパイル時間 175 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 131,256 KB
最終ジャッジ日時 2024-04-29 00:47:27
合計ジャッジ時間 5,858 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 112 ms
82,560 KB
testcase_01 WA -
testcase_02 AC 272 ms
78,888 KB
testcase_03 WA -
testcase_04 AC 340 ms
79,708 KB
testcase_05 WA -
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
def naive(x,y,a):
  if x==y:
    return 0
  todo=deque()
  todo.append((x,0))
  seen=set([x])
  while todo:
    v,res=todo.popleft()
    if v==y:
      return res
    if res>10:
      return 10**9
    if v+1 not in seen:
      seen.add(v+1)
      todo.append((v+1,res+1))
    if v>0 and v-1 not in seen:
      seen.add(v-1)
      todo.append((v-1,res+1))
    if v*a not in seen:
      seen.add(v*a)
      todo.append((v*a,res+1))
    if v//a not in seen:
      seen.add(v//a)
      todo.append((v//a,res+1))


from sys import stdin
input=lambda :stdin.readline()[:-1]

memo={}

def calc(y,x,a,k):
  if y in memo:
    return memo[y]
  ans=abs(y-x)
  tmpL,tmpR=y,y+1
  res=0
  while tmpR//a<=x:
    tmpL*=a
    tmpR*=a
    res+=1
    if tmpL<=x<tmpR:
      ans=min(ans,res)
    else:
      ans=min(ans,res+min(abs(tmpL-x),res+abs(tmpR-x)))
  
  y1=y//a
  if y1<y:
    res1=min(abs(y1*a-y)+1,abs(y-y1))+calc(y1,x,a,k+1)
    ans=min(ans,res1)
  y2=(y+a-1)//a
  if y2<y:
    res2=min(abs(y2*a-y)+1,abs(y-y2))+calc(y2,x,a,k+1)
    ans=min(ans,res2)
  
  if k<=120:
    ans=min(ans,calc(y+1,x,a,k+1)+1)
    if y!=0:
      ans=min(ans,calc(y-1,x,a,k+1)+1)
  memo[y]=ans
  return ans

for _ in range(0):
  import random
  memo.clear()
  x=random.randint(0,10**18)
  y=random.randint(0,10**18)
  a=random.randint(2,10**18)
  print(calc(y,x,a,1))

for _ in range(int(input())):
  memo.clear()
  x,y,a=map(int,input().split())
  print(calc(y,x,a,1))
0