[python]伯準16953 A→B(Greedy/BFS)



📌 質問する


AをBに変えます.可能な演算は次の2つです.
2を掛ける.
数の一番右に1を追加します.
AからBまでの演算の最大値を求める.

入力


第1行は、A、B(1≦A

しゅつりょく


AをBに変換するために必要な演算の最大値に1を加算して出力します.作成できない場合は、-1を出力します.

入力例1


2 162
2 → 4 → 8 → 81 → 162

サンプル出力1


5

入力例2


4 42

サンプル出力2


-1

入力例3


100 40021
100 → 200 → 2001 → 4002 → 40021

サンプル出力3


5

📌 に答える


💬 Greedy Code

import sys
input = sys.stdin.readline

a, b = map(int, input().split())
cnt = 1

while a != b:
    if b % 2 != 0: # 홀수면
        if str(b)[len(str(b))-1] == '1' and b != 1: # 끝자리가 1이면 1 제거
            b = int(str(b)[:len(str(b))-1])
            cnt += 1
        else: # 아니면 -1 출력
            cnt = -1
            break
    elif b % 2 == 0: # 짝수면 나누기 2
        b //= 2
        cnt += 1

print(cnt)

💡 Greedy Solution


Greedyで解くとAからBよりBからAの方が便利です.
  • Bは奇数
  • Bは、1で終わる奇数(ex.11,31):端数1を削除して判断
  • Bが1で終わる奇数でなければ(ex.57,43):端数1を削除できないし、すべてを2で割ることもできないので、Aに設定できます
  • Bは偶数
  • 全体2を
  • で割る.
  • BとAが同一である場合、
  • を閉じる.

    💬 BFS Code

    import sys
    from collections import deque
    input = sys.stdin.readline
    
    def bfs():
        q = deque([(a, 1)])
        while q:
            x, dist = q.popleft()
            if x == b:
                print(dist)
                sys.exit(0)
            for nx in [x * 2, int(str(x) + '1')]:
                if nx <= b:
                    q.append((nx, dist + 1))
        print(-1)
    
    a, b = map(int, input().split())
    bfs()

    💡 BFS Solution


    慣例に従って、AはBの接着剤になります.