Решить задачу с помощью рекуррентного соотношения, алгоритмы (С++)

129

17 ноября 2021, 13:00

Назовём число счастливым, если оно делится на k и сумма его цифр лежит в интервале [p, q]. Нужно подсчитать, сколько счастливых чисел лежат в интервале [a, b].

Задачу требуется решить с помощью рекуррентного соотношения, но я не знаю как. Набросал кода, который работает, но медленно.

Заранее спасибо за ответ!

 short SumLuckyNumbers(uint64_t x)
{
    uint64_t s = 0;
    while (x != 0)
    {
        s += x % 10;
        x /= 10;
    }
    return s;
}
int main() {
    short k;
    uint64_t a, b;
    short p, q;
    size_t count = 0;
    std::cin >> k >> a >> b >> p >> q;
    //ищу первый элемент, который делится на k, чтобы лишние разы не проверять в цикле
    int first;
    if (a % k == 0)
        first = a;
   else
    {
        if (a > k)
            first = (a / k) * (k + 1);
        else
            first = k;
    }
    //иду по всем k, проверяя сумму цифр
    for (int i = first; i <= b; i += k) {
        short s = SumLuckyNumbers(i); // подсчет суммы цифр числа
        if (s >= p && s <= q) 
            count++;
    }
    std::cout << count;

Answer 1

Задача на динамическое программирование. Конкретно: Digit DP. Советую почитать здесь.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector <int> v;
int sz;
ll dp[20][200][110][2]; // pos - sum - remainder - flag
ll a, b, p, q, k;
// Проходимся по всем цифрам
// pos - текущая цифра
// sum - текущая сумма
// num - число
// flag - равно false если мы можем идти до 9
//        равно true если мы должны идти до v[pos]
ll calc(int pos, ll sum, ll num, int flag) {
    // Если дошли до конца числа
    if(pos == sz) {
        // Если сумма заходит в диапозон И число делится на k
        if(sum >= p && sum <= q && num % k == 0) {
            // +1 к результату
            return 1;
        }
        return 0;
    }
    // Если такой случай уже был - выводим 
    if(dp[pos][sum][num%k][flag]) {
        return dp[pos][sum][num%k][flag];
    }
    // Максимальная цифра до которой можем дойти
    int mx = 9;
    ll res = 0;
    if(flag)
        mx = v[pos];
    // Идем до максимальной цифры
    for(int i=0; i <= mx; i++) {
        // следующий flag (next flag)
        bool nf = (i == mx && flag);
        // делаем следующий шаг
        res += calc(pos+1, sum+i, num*10+i, nf);
    }
    // Запоминаем случай
    return dp[pos][sum][num%k][flag] = res;
}
ll solve(ll n) {
    v.clear();
    // Делаем все элементы массива равным 0
    memset(dp, 0, sizeof(dp));
    // Конвертируем число в вектор
    while(n) {
        v.push_back(n%10);
        n /= 10;
    }
    // Пример: n - 172, v = { 1, 7, 2 }
    reverse(v.begin(), v.end());
    sz = v.size();
    return calc(0, 0ll, 0ll, 1);
}
int main() {
    cin >> k >> a >> b >> p >> q;
    // a < b
    // p < q
    cout << solve(b) - solve(a-1);
    return 0;
}