algorithm - 赢得 Frog 比赛

Question

我遇到了这个问题，但无法想出解决方案。有一场 Frog 赛跑， Frog 有一定数量的有效跳步。它可以向前或向后移动。为了赢得比赛， Frog 必须尽可能靠近终点线，但不能越过终点线。

例子。6, 1 7

因此，终点线距离 6 个单位， Frog 可以向后和向前跳跃 1 和 7 个单位。在这里，输出应该是 6，因为最佳策略是向后 1 单位，然后向前 7 步到达终点线。

Answer 1

你能到达的位置都是gcd(valid jumpsteps)的整数倍。如果答案只是壁橱可到达的位置，请在终点线之前或终点线处取倍数。

如果您还需要这些步骤，可以使用扩展欧氏算法来计算组合。