首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#13207

从A到B 我们来做一个数字游戏,通过一系列操作把一个数字 A 变成另一个数字 B。设当前数字是 X,规定每次操作可以从以下 3 种里面选一种进行: - X =…

从A到B

我们来做一个数字游戏,通过一系列操作把一个数字 A 变成另一个数字 B。设当前数字是 X,规定每次操作可以从以下 3 种里面选一种进行:

- X = X + 1

- X = X - 1

- X = X × N

你的任务就是求出从 A 变成 B 至少需要多少步。

时间限制:1000

内存限制:65536

输入

每组输入包含多个测试用例。先给出一个整数 K(≤ 10),为测试用例的个数。随后 K 行,每行给出一个测试用例的三个整数:A、B、N,其中 -105 ≤ A, B ≤ 105,1 < N < 10。同行数字间以空格分隔。

输出

对每个测试用例,在一行中输出从 A 变成 B 至少需要多少步。


样例输入

3
3 11 2
-5 -12 3
-2 1000 7

样例输出

3
2
13

提示

样例解释: 第 1 组:(3 × 2 × 2)-1=11 第 2 组:(-5+1) × 3 = -12 第 3 组:(((-2+1+1+1+1+1)×7-1)×7+1+1+1)×7-1 = 1000

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;unordered_map&gt; using namespace std; int solve(long long A, long long B, int N) { if (A == B) return 0; queue&lt;pair&lt;long long, int&gt;&gt; q; unordered_map&lt;long long, int&gt; visited; q.push({A, 0}); visited[A] = 0; while (!q.empty()) { auto [current, steps] = q.front(); q.pop(); if (current == B) { return steps; } vector&lt;long long&gt; next_values = {current + 1, current - 1, current * N}; for (long long next_val : next_values) { if (next_val == B) { return steps + 1; } if (!visited.count(next_val)) { visited[next_val] = steps + 1; q.push({next_val, steps + 1}); } } } return -1; // 理论上不会执行到这里 } int main() { ios::sync_with_stdio(false); cin.tie(0); int K; cin &gt;&gt; K; while (K--) { long long A, B; int N; cin &gt;&gt; A &gt;&gt; B &gt;&gt; N; cout &lt;&lt; solve(A, B, N) &lt;&lt; '\n'; } return 0; }</pre>
这道题暂未补解析。