MarsCode奇妙货币交易问题——数学

另外，可能有数学家已经证明V= (V-2)的情形，即此时的。那么就可以利用数学的取模mod 和除法 /，来迭代判断每次。>= V-2，这种情况不满足[-2,2]了，但是可以变成。这篇文章有答案，代码很简洁，但蛮难理解的。都必须满足[-2,2]之间。都满足，就说明YES。

lucas hu

27人浏览 · 2025-01-02 01:24:25

lucas hu · 2025-01-02 01:24:25 发布

奇妙货币交易问题 - MarsCode

不会做，豆包回答动态规划感觉有问题，无法ac，它没有考虑卖家补钱，减钱的情况。

Python解决——“奇妙货币交易”问题-CSDN博客

这篇文章有答案，代码很简洁，但蛮难理解的。

W一定可以表示为 $W = k_{0}V^{0} + k_{1}V^{1} + ... +k_{n}V^{n}$ ，只不过题目要求任意 $k_{i}$ 都必须满足[-2,2]之间。

那么就可以利用数学的取模mod 和除法 /，来迭代判断每次 $k_{i}$ 是否满足，一直到 $k_{n}$ 都满足，就说明YES。

不过对于 W mod V后，为>= (V-2)的情形，即此时的 $k_{0}$ >= V-2，这种情况不满足[-2,2]了，但是可以变成 $W = V-k_{0}V^{0} +( k_{1}+1)V^{1} + ... +k_{n}V^{n}$ ，这样又满足 $V-k_{0}V^{0}$ 在[-2,2]了，所以会处理为 W = W/V + 1,让k1+1就是这样来的。

其他余数就说明不可能满足任意 $k_{i}$ 都[-2,2]了。另外，可能有数学家已经证明V<=5时，肯定能组成任意整数，当做结论进行优化吧。


public class Main {
    public static String solution(int V, int W) {
        // Edit your code here
        if(V <= 5)
            return "YES";
        int remainder;
        while(W != 0) {
            remainder = W % V;
            if(remainder <= 2)
                W = W / V;
            else if(remainder >= V - 2)
                W = (W/V) + 1;
            else
                return "NO";

        }
        return "YES";
    }

    public static void main(String[] args) {
        // Add your test cases here
        System.out.println(solution(10, 9) == "YES");
        System.out.println(solution(200, 40199) == "YES");
        System.out.println(solution(108, 50) == "NO");

    }
}