Submission #22261756

Source Code Expand

import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)


X,Y = map(int, input().split())
minCost = abs(X-Y)
memo = defaultdict(lambda: float('inf'))

#YをXにする際のパターンで考える
def bfs(y,cost):
    global X,minCost,memo
    if(cost>=minCost):
        return
    minCost = min(minCost,cost+abs(X-y))
    if y==1:
        return
    #コストが更新される場合は続行
    if memo[y]<cost:
        return
    memo[y]=cost

    if(y%2==0):
        bfs(y//2,cost+1)
    else:
        bfs((y+1)//2,cost+2)
        bfs((y-1)//2,cost+2)

bfs(Y,0)
print(minCost)

Submission Info

Submission Time
Task F - +1-1x2
User H20
Language PyPy3 (7.3.0)
Score 600
Code Size 631 Byte
Status AC
Exec Time 108 ms
Memory 72108 KiB

Judge Result

Set Name Sample All after_contest
Score / Max Score 0 / 0 600 / 600 0 / 0
Status
AC × 3
AC × 49
AC × 1
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All extreme_00.txt, extreme_01.txt, extreme_02.txt, extreme_03.txt, extreme_04.txt, handmade_00.txt, handmade_01.txt, handmade_02.txt, handmade_03.txt, handmade_04.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_exp_00.txt, random_exp_01.txt, random_exp_02.txt, random_exp_03.txt, random_exp_04.txt, random_exp_05.txt, random_exp_06.txt, random_exp_07.txt, random_exp_08.txt, random_exp_09.txt, random_exp_10.txt, random_exp_11.txt, random_exp_12.txt, random_exp_13.txt, random_exp_14.txt, random_exp_15.txt, random_small_00.txt, random_small_01.txt, random_small_02.txt, random_small_03.txt, random_small_04.txt, random_small_05.txt, random_small_06.txt, random_small_07.txt, random_small_08.txt, random_small_09.txt, sample_01.txt, sample_02.txt, sample_03.txt
after_contest after_contest_01.txt
Case Name Status Exec Time Memory
after_contest_01.txt AC 77 ms 64728 KiB
extreme_00.txt AC 57 ms 64628 KiB
extreme_01.txt AC 64 ms 65188 KiB
extreme_02.txt AC 69 ms 68356 KiB
extreme_03.txt AC 76 ms 68320 KiB
extreme_04.txt AC 74 ms 69832 KiB
handmade_00.txt AC 59 ms 64684 KiB
handmade_01.txt AC 59 ms 64608 KiB
handmade_02.txt AC 58 ms 64740 KiB
handmade_03.txt AC 71 ms 68288 KiB
handmade_04.txt AC 59 ms 64548 KiB
random_00.txt AC 80 ms 70340 KiB
random_01.txt AC 83 ms 70480 KiB
random_02.txt AC 72 ms 68216 KiB
random_03.txt AC 83 ms 69980 KiB
random_04.txt AC 108 ms 72108 KiB
random_05.txt AC 87 ms 69848 KiB
random_06.txt AC 90 ms 70576 KiB
random_07.txt AC 89 ms 70656 KiB
random_08.txt AC 58 ms 65092 KiB
random_09.txt AC 76 ms 69272 KiB
random_exp_00.txt AC 56 ms 64732 KiB
random_exp_01.txt AC 68 ms 67632 KiB
random_exp_02.txt AC 77 ms 69336 KiB
random_exp_03.txt AC 56 ms 65092 KiB
random_exp_04.txt AC 97 ms 70592 KiB
random_exp_05.txt AC 56 ms 64472 KiB
random_exp_06.txt AC 75 ms 68132 KiB
random_exp_07.txt AC 75 ms 68436 KiB
random_exp_08.txt AC 75 ms 67844 KiB
random_exp_09.txt AC 82 ms 69748 KiB
random_exp_10.txt AC 57 ms 64772 KiB
random_exp_11.txt AC 58 ms 64880 KiB
random_exp_12.txt AC 61 ms 65160 KiB
random_exp_13.txt AC 68 ms 67660 KiB
random_exp_14.txt AC 102 ms 70196 KiB
random_exp_15.txt AC 59 ms 64588 KiB
random_small_00.txt AC 57 ms 64608 KiB
random_small_01.txt AC 59 ms 64616 KiB
random_small_02.txt AC 58 ms 65096 KiB
random_small_03.txt AC 57 ms 64800 KiB
random_small_04.txt AC 58 ms 65120 KiB
random_small_05.txt AC 60 ms 65072 KiB
random_small_06.txt AC 59 ms 64592 KiB
random_small_07.txt AC 52 ms 64612 KiB
random_small_08.txt AC 55 ms 64624 KiB
random_small_09.txt AC 52 ms 64488 KiB
sample_01.txt AC 58 ms 64684 KiB
sample_02.txt AC 60 ms 64788 KiB
sample_03.txt AC 60 ms 64672 KiB