ABC235D - Multiply and Rotate

考え方

• 「重みなし」グラフの最短経路を求める問題になる→BFS
• 桁が減る操作はないので，10 ** 6を超えたら打ち切ることができる

回答例

from collections import deque
a, N = map(int, input().split())

q = deque()
q.append(1)

dist = [-1] * (10 ** 6)
dist[1] = 0
while q:
  x = q.popleft()
  nxt = a * x
  if nxt < 10 ** 6 and dist[nxt] == -1:
    dist[nxt] = dist[x] + 1
    q.append(nxt)
  if x >= 10 and x % 10:
    nxt = str(x)
    nxt = int(nxt[-1] + nxt[:-1])
    if nxt < 10 ** 6 and dist[nxt] == -1:
      dist[nxt] = dist[x] + 1
      q.append(nxt)
    
print(dist[N])

【参考】Submission #28541490 - HHKB Programming Contest 2022（AtCoder Beginner Contest 235）