番号が幸運であるかどうかを見つける

Question

私はハッカーの問題を解決しようとしています。hereのランクです。

質問です：

だからこれを解決するために、私は簡単な数学の方程式を試してみました：15をチェックするために、例えば

4x + 7y = lucky_number 

lucky_numberかではなく、I x、yの値0で始まり、上の方程式に等しいかそれよりも大きくなるまで（もしそうならば停止し、 r）

上記のロジックは正常に動作します。しかし問題は大きな数字で、数字966888032206353が幸運であるかどうかをチェックすることを想像してください。x,yから0までは効率的なアイデアではありません。

これまでのガイダンスはありますか？

Answer 1

7 * 4 = 28アップ（実際には18人までのすべてのマウンタでさえ）からの数字はすべて幸運です。残りの部分は小さなテーブルを事前計算するだけです。

Answer 2

あなたの問題の1つは、問題の説明が非常に不完全であることです。あなたは、負の値がxとyしか許されていない場合、実際には整数を表すことができます。4x + 7yたとえば、1 = 4*2 + (-1)*7とその係数を乗算すれば、任意の数の解を得ることができます。

アルゴリズムの観点からは、動的プログラミングを使用するのが最適なソリューションだと思います。彼らはあなたの感覚で幸運であるかどうかを簡単に確認することができます。 4つの連続的な幸運な数字が見つかるとすぐに、停止することができます。それ以降の数字は、適切な回数を4回追加するだけで幸運になるからです。私はあなたが4つの連続した幸運な数字のシーケンスを非常に早く見つけるだろうと思う。

Answer 3

それを考えるための別の方法：あなたがやらなければならないことは、プロットは、ライン

7y = -4x + 966888032206353 

xとyの両方が整数である任意のポイントを特定します。

したがって、ネストループは必要ありません。代わりに：

1. yを整数として反復します。 for y=0; y<966888032206353/7; y++

2. 各繰り返しで、浮動小数点演算を使用してxを解く。

3. xが整数の場合、その数はラッキーです。

これには約138T回の反復が必要です。

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の場合は常にOKです。