本题为2024年10月19日小米机考原题

小米机考的介绍点击这里

题目内容

小塔最近正在学习魔法，通过魔法可以改变纸上的数字。

小塔一共会两种魔法，第一种魔法可以将纸上数字变为它的$a$倍，比如在$a=3$时，他可以将$666$变成$1998$;第二种魔法可以让纸上的数字循环右移一次，比如$12345$在施加第二种魔法后会变成$51234$，$119$会变$911$，需要注意的是，小塔无法对小于$10$或是以$0$为结尾的数施加第二种魔法。

纸上的数字初始是$1$，小塔想将它变成自己的幸运数字$b$，那么请问小塔至少需要施加几次魔法。如果无论如何 都无法将它变成$b$,请输出$-1$。

输入描述

输入一行，包含两个正整数$a,b$ $2≤a,b<10^6$

输出描述

输出一行一个数，表示最少的魔法次数，或输出$-1$表示无解。

样例1

输入

3 621

输出

6

说明

样例解释$1$

一种可行的方法为:$1->3->9->27->72->216->621$

输入样例$2$

$3\ 666$

输出样例2

$-1$

题目大意

求出将$1$变成$b$的最少次数(不能变则输出-1)有两个操作。 1.将当前数字$*a$ 2.将当前数字循环右移一次$(12345->51234)$

思路:单源BFS

我们在看完题面之后，我们需要将数字1变成b。通过乘法或者循环右移，没有规律可言。注意到我们的数据范围(a,b)都是小于$10^6$。也就是我们把a变成大于min($10^6$,b)之后这个状态是肯定没有用的。

状态只有$10^6$这么多，把两种操作看成是两条单向边。这样就变成了一个典型的最短路径问题。那么我们使用BFS(或者记忆化搜索)来解决。

假如$a$=2,就会抽象成一个这样的图，这里展示前10个数方便理解，在加大数据则图会非常庞大。

1.初始化：

使用一个队列来进行 BFS，初始状态为 1，步数为 0。 使用一个数组 visited 来记录每个数字被访问的最少步数，初始时所有值为 -1（未访问）。

2.BFS 过程：

从队列中取出当前数字current 和当前步数 steps。 如果 current == b，返回 steps。 执行两种魔法：

乘法魔法： 计算 next1 = current * a，如果 next1 未被访问且在合法范围内，标记为已访问并加入队列，步数加 1。

旋转魔法：

检查 current >= 10 且 current % 10 != 0。 将 current 循环右移一次，得到 next2。 如果 next2 未被访问且在合法范围内，标记为已访问并加入队列，步数加 1。

3.终止条件：

如果队列为空且未找到目标，返回 -1

最后贴上我们的ac代码~

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	
	// 如果b小于1，直接输出-1
	if (b < 1) {
		cout << -1;
		return 0;
	}
	
	// 定义一个数组来记录访问状态，范围到10^6
	vector<int> visited(1000001, -1);
	queue<int> q;
	
	// 从1开始
	q.push(1);
	visited[1] = 0;
	
	while (!q.empty()) {
		int current = q.front();
		q.pop();
		
		// 如果到达目标，输出结果
		if (current == b) {
			cout << visited[current];
			return 0;
		}
		
		// 第一种魔法：乘以a
		long long next1 = (long long)current * a;
		if (next1 <= 1000000 && visited[next1] == -1) {
			visited[next1] = visited[current] + 1;
			q.push(next1);
		}
		
		// 第二种魔法：循环右移一次
		// 只有当当前数字 >=10 且最后一位不为0时才可以旋转
		if (current >= 10 && current % 10 != 0) {
			string s = to_string(current);
			// 循环右移一次
			string rotated = to_string(current);
			rotated = rotated.substr(rotated.size() - 1) + rotated.substr(0, rotated.size() - 1);
			// 转换回整数
			int next2 = stoi(rotated);
			if (next2 <= 1000000 && visited[next2] == -1) {
				visited[next2] = visited[current] + 1;
				q.push(next2);
			}
		}
	}
	
	// 如果无法到达目标，输出-1
	cout << -1;
	return 0;
}

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();

        // 如果b小于1，直接输出-1
        if (b < 1) {
            System.out.println(-1);
            return;
        }

        // 定义一个数组来记录访问状态，范围到10^6
        int[] visited = new int[1000001];
        Arrays.fill(visited, -1);
        Queue<Integer> q = new LinkedList<>();

        // 从1开始
        q.add(1);
        visited[1] = 0;

        while (!q.isEmpty()) {
            int current = q.poll();

            // 如果到达目标，输出结果
            if (current == b) {
                System.out.println(visited[current]);
                return;
            }

            // 第一种魔法：乘以a
            long next1 = (long) current * a;
            if (next1 <= 1000000 && visited[(int) next1] == -1) {
                visited[(int) next1] = visited[current] + 1;
                q.add((int) next1);
            }

            // 第二种魔法：循环右移一次
            if (current >= 10 && current % 10 != 0) {
                String s = Integer.toString(current);
                String rotated = s.charAt(s.length() - 1) + s.substring(0, s.length() - 1);
                int next2 = Integer.parseInt(rotated);

                if (next2 <= 1000000 && visited[next2] == -1) {
                    visited[next2] = visited[current] + 1;
                    q.add(next2);
                }
            }
        }

        // 如果无法到达目标，输出-1
        System.out.println(-1);
    }
}

python

from collections import deque

def main():
    a, b = map(int, input().split())

    # 如果b小于1，直接输出-1
    if b < 1:
        print(-1)
        return

    # 定义一个数组来记录访问状态，范围到10^6
    visited = [-1] * (1000001)
    q = deque()

    # 从1开始
    q.append(1)
    visited[1] = 0

    while q:
        current = q.popleft()

        # 如果到达目标，输出结果
        if current == b:
            print(visited[current])
            return

        # 第一种魔法：乘以a
        next1 = current * a
        if next1 <= 1000000 and visited[next1] == -1:
            visited[next1] = visited[current] + 1
            q.append(next1)

        # 第二种魔法：循环右移一次
        if current >= 10 and current % 10 != 0:
            rotated = str(current)[-1] + str(current)[:-1]
            next2 = int(rotated)

            if next2 <= 1000000 and visited[next2] == -1:
                visited[next2] = visited[current] + 1
                q.append(next2)

    # 如果无法到达目标，输出-1
    print(-1)

if __name__ == "__main__":
    main()