Поиск числа повезло или нет

Question

Я пытаюсь решить проблему с ранжирования хакера более here.

Возникает вопрос:

Так решить эту проблему, я попытался с помощью простого математики уравнения:

4x + 7y = lucky_number 

Например, чтобы проверить 15 является lucky_number или нет, я могли бы начинаться с x, y значений 0 и подставляя это уравнение до тех пор, пока оно не станет равным или больше (если так остановитесь и скажите, что это не luc ky number)

Вышеупомянутая логика отлично работает. Но проблема в большом количестве, представьте себе, чтобы проверить номер 966888032206353 повезло или нет, начиная с x,y до 0 не будет эффективной идеей.

Любые указания для этого?

Answer 1

Все номера от 7 * 4 = 28 до (на самом деле даже все барабанщики от 18 до) счастливы, а остальные просто прекоммутируют небольшую таблицу.

Answer 2

Одна из ваших проблем заключается в том, что описание проблемы очень неполное. Вы можете infact представлять любое целое число как 4x + 7y, если вы допустили только отрицательные x и y. Например, 1 = 4*2 + (-1)*7, и вы можете получить решение для любого числа, умножив его на этот коэффициент.

Я думаю, лучшее решение с точки зрения алгоритмики - использовать динамическое программирование. Вы можете просто начать проверять номера, удачливы ли они в вашем смысле или нет. Как только вы найдете 4 счастливых номера, вы можете остановиться, потому что любое число после этого будет удачным, просто добавив 4 подходящего количества раз. Наверное, вы найдете последовательность из четырех счастливых чисел очень рано.

Answer 3

Другой способ думать об этом: Все, что вам нужно сделать, это участок линии

7y = -4x + 966888032206353 

и выявить точки, где оба х и у являются целыми числами.

Таким образом, вам не нужен вложенный цикл. Вместо этого:

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 все в порядке.