(新卷,200分)- 数字加减游戏（Java JS Python）

(新卷,200分)- 数字加减游戏（Java & JS & Python）

题目描述

小明在玩一个数字加减游戏，只使用加法或者减法，将一个数字s变成数字t。
每个回合，小明可以用当前的数字加上或减去一个数字。
现在有两种数字可以用来加减，分别为a,b(a!=b)，其中b没有使用次数限制。
请问小明最少可以用多少次a，才能将数字s变成数字t。
题目保证数字s一定能变成数字t。

输入描述

输入的唯一一行包含四个正整数s,t,a,b(1<=s,t,a,b<=105)，并且a!=b。

输出描述

输出的唯一一行包含一个整数，表示最少需要使用多少次a才能将数字s变成数字t。

用例

题目解析

本题有点像数学问题

比如用例1其实就是求解：

满足 5 * x + 2 * y = 9 的所有解中绝对值最小的x

比如用例2其实就是求解：

满足 4 * x + 10 * y = 22 的所有解中绝对值最小的x

因此，我们可以让x从0开始尝试，然后尝试1，-1，然后尝试2，-2，直到找到一个x能够让（比如用例1）(9 - 5*x) / 2 为一个整数。

由于本题1<=s,t,a,b<=105，数量级较小，因此上面逻辑可行。

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); rl.on("line", (line) => { const [s, t, a, b] = line.split(" ").map(Number); console.log(getResult(s, t, a, b)); }); function getResult(s, t, a, b) { let x = 0; let diff = t - s; while (true) { if ( Number.isInteger((diff - a * x) / b) || Number.isInteger((diff + a * x) / b) ) { return Math.abs(x); } x++; } }

Java算法源码

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] arr = new int[4]; for (int i = 0; i < 4; i++) { arr[i] = sc.nextInt(); } System.out.println(getResult(arr[0], arr[1], arr[2], arr[3])); } public static int getResult(int s, int t, int a, int b) { int x = 0; int diff = t - s; while (true) { if ((diff - a * x) % b == 0 || (diff + a * x) % b == 0) { return Math.abs(x); } x++; } } }

Python算法源码

# 输入获取 s, t, a, b = map(int, input().split()) # 算法入口 def getResult(s, t, a, b): x = 0 diff = t - s while True: if str((diff - a * x) / b).endswith(".0") or str((diff + a * x) / b).endswith(".0"): return abs(x) x += 1 # 算法调用 print(getResult(s, t, a, b))