找到幸运与否的数字

Question

我正在尝试解决黑客等级超过 here 的问题。

问题是：

所以为了解决这个问题，我尝试了一个简单的数学方程式：

4x + 7y = lucky_number

例如，要检查 15 是否为 lucky_number，我可以从 x、y 值 0 开始并代入上面的等式直到它等于或大于（如果是这样停下来说它不是幸运数字）

以上逻辑运行良好。但问题是大数字，想象一下检查数字 966888032206353 幸运与否，从 x,y 到 0 不是一个有效的想法。

有什么指导吗？

Answer 1

你的一个问题是你的问题描述很不完整。实际上，如果只允许负 x 和 y，则可以将任何整数表示为 4x + 7y。例如，1 = 4*2 + (-1)*7，您可以通过乘以该因数得到任何数字的解。

我想从算法的角度来看，最好的解决方案是使用动态规划。您可以简单地开始检查数字是否在您看来是幸运的。一旦找到 4 个连续的幸运数字，就可以停下来，因为之后的任何数字只需将 4 加适当的次数即可幸运。我猜你会很早就找到一个由 4 个连续的幸运数字组成的序列。

Answer 2

另一种思考方式：您需要做的就是绘制直线

7y = -4x + 966888032206353

并找出 x 和 y 均为整数的任何点。

因此，您不需要嵌套循环。相反：

将 y 作为整数进行迭代。 for y=0; y<966888032206353 / 7; y++
对于每次迭代，使用浮点数学求解 x。
若x为整数，则为幸运数

这将需要大约 138T 次迭代。

Answer 3

所有7*4=28以上的数字（实际上是18以上的所有数字）都是幸运的，其余的只需预先计算一个小的table。

Answer 4

这是我提交给 Hackerrank 的代码。

#include <bits/stdc++.h>
using namespace std;
int q; long long n; bool dp[1009];
int main() {
    cin >> q;
    dp[0] = true;
    for(int i = 1; i <= 1000; i++) {
        if(i >= 4 && dp[i - 4]) dp[i] = true;
        if(i >= 7 && dp[i - 7]) dp[i] = true;
    }
    while(q--) {
        cin >> n;
        if(n >= 1000 || dp[n]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

这是动态规划，但是如果n >= 28总是可以的。

找到幸运与否的数字

Finding a number lucky or not

algorithm

equation-solving