Здравствуйте. Есть задача: на вход поступают числа A, B, S, T, k, где
1 <= A, B <= 10^19;
1 <= S, T <= 162;
2 <= k <= 100.
Нужно найти количество всех чисел, которые находятся на интервале [A, B], имеют сумму цифр, принадлежащих отрезку [S, T] и в то же время делятся на k без остатка.

Прямой перебор здесь не подходит. Как можно поступить в таком случае?

Здравствуйте, Assasin291, Вы писали:

A>Здравствуйте. Есть задача: на вход поступают числа A, B, S, T, k, где
A>1 <= A, B <= 10^19;
A>1 <= S, T <= 162;
A>2 <= k <= 100.
A>Нужно найти количество всех чисел, которые находятся на интервале [A, B], имеют сумму цифр, принадлежащих отрезку [S, T] и в то же время делятся на k без остатка.

A>Прямой перебор здесь не подходит. Как можно поступить в таком случае?

Это довольно стандартная задача на динамическое программирование.

Во-первых, научимся находить количество чисел <= X, обладающих всеми свойствами относительно суммы цифр и делимости. Пусть таких чисел будет F(X). Тогда ответ на исходную задачу будет F(B) — F(A-1). Теперь, как искать F(X)?

Пусть X у нас задано, и в нем n цифр. Будем искать все n-значные числа с заданной суммой и делящиеся на k. Представим что мы записываем число слева направо (со старших разрядов). Допустим, мы записали уже i цифр. Тогда нас интересуют следующие свойства записанного числа: остаток от деления на k (обозначим q), сумма цифр (обозначим s) и то, гарантирует ли записанный префикс, что любое число с этим префиксом меньше X (обозначим l, это булевский флаг). Посчитаем количество чисел которые можно получить из префикса длины i с остатком q, суммой s и флагом l, так чтобы они удовлетворяли всем условиям задачи и были меньше X. Обозначим это количество как F(i, q, s, l).

Тогда какие у нас варианты? Если l == true, то есть префикс заведомо меньше X, мы можем приписать любую цифру справа. Получается:

F(i, q, s, true) = sum(d in [0..9], F(i+1, (q*10 + d) mod k, s + d, true)

Если l == false:

F(i, q, s, false) = sum(d in [0..X[i]], F(i+1, (q*10 + d) mod k, s + d, d < X[i])

Где X[i] — это i-я цифра числа X (нумерация с 0, 0 — самый старший разряд).

Тогда F(X) = F(0, 0, 0, false)

начальные условия:

F(n, q, s, l) = 1 if q == 0 and S <= s <= T else 0, где n — длина числа X.

Получилась рекуррентная формула, которую осталось только запрограммировать (с мемоизацией).

Здравствуйте, Assasin291, Вы писали:

A>Здравствуйте. Есть задача: на вход поступают числа A, B, S, T, k, где
A>1 <= A, B <= 10^19;
A>1 <= S, T <= 162;
A>2 <= k <= 100.
A>Нужно найти количество всех чисел, которые находятся на интервале [A, B], имеют сумму цифр, принадлежащих отрезку [S, T] и в то же время делятся на k без остатка.

A>Прямой перебор здесь не подходит. Как можно поступить в таком случае?

условия [S, T] и k дадут нижнюю и верхнюю границы поиска
k даст шаг

потом перебор с шагом по условию sum in [S,T].

пример:

TEST 1:

A=15
B=99999
S=15
T=20
k=3

Low bound for [15]: 69
Low bound for [99999]: 99999
Low bound for [15]: 69
Low bound for [20]: 299
Upper bound for [20]: 99200
Checking range [69] - [99198] step [3], estimated amount [33043]
Result [8086]

TEST 2:

A=1
B=10M
S=15
T=20
k=3


Low bound for [1]: 1
Low bound for [10000000]: 99999999
Low bound for [15]: 69
Low bound for [20]: 299
Upper bound for [20]: 99200000
Checking range [69] - [9999999] step [3], estimated amount [3333310]
Result [164605]

здесь "Low bound for [N]" минимальное число, сумма цифр которого дает N но не больше нашего максимуса (B). если такого нет то просто девятки в количестве не больше чем разрядность B. Ноходится жадным алгоритимом.

"Upper bound for [N]" максимальное число, сумма цифр которого дает N но не больше нашего максимуса (B). А вот как найти верхнюю границу кроме как перебором вниз я не придумал

на глазок перебор N/3 элементов.

Здравствуйте, baxton_ulf, Вы писали:

условия [S, T] и k дадут нижнюю и верхнюю границы поиска
k даст шаг

потом перебор с шагом по условию sum in [S,T].

Что-то подобное я хотел сделать, но всё равно, при k = 2, A = S = 1, T = 162, B = 10^19 такой алгоритм работать будет очень долго.

Vintik_69, спасибо. Думаю, это как раз то, что мне надо.

Здравствуйте, Assasin291, Вы писали:


A>Что-то подобное я хотел сделать, но всё равно, при k = 2, A = S = 1, T = 162, B = 10^19 такой алгоритм работать будет очень долго.

тут то как раз все быстро можно перебирать только числа удовлетворяющие условию sum in [S, T]. кстати их можно получить так:

1) ищем минимальное для S (smin)
2) ищем максимальное для T (tmax)
3) начинаем работать с парами цифр из tmax так чтобы новое число n удовлетворяло:
3.1) smin < n < tmax
3.2) sumOfDigs(n) in [S,T], те если пара цифр a и b, то одно изменение это a++;b--; или a--;b++

так мы гарантированно пройдем только по числам удовлетворяющим условию sum in [S, T].


A>Vintik_69, спасибо. Думаю, это как раз то, что мне надо.

сдается мне тут тоже перебор. очень интересно на имплементацию посмотреть, выложи потом plz

Здравствуйте, baxton_ulf, Вы писали:

_>сдается мне тут тоже перебор. очень интересно на имплементацию посмотреть, выложи потом plz

Хорошо, думаю, за выходные сделаю.

Здравствуйте, Vintik_69, Вы писали:

V_>Получилась рекуррентная формула, которую осталось только запрограммировать (с мемоизацией).

Вчера попробовал запрограммировать формулу, но сегодня, запустив, получил в качестве ответа ноль(искал количество чисел, не превосходящих 140, делящихся на 13 и с суммой цифр от 11 до 18), хотя ответ должен получиться "3" (39, 65, 78). Можете указать ошибку? Просто дебажить такое очень трудно.

unsigned func(unsigned i, unsigned q, unsigned s, bool l) {
    if(i != 20)
    {
        unsigned long long temp = 0;
        if(l)
        {
            for (unsigned d = 0; d <= 9; ++d)
                temp += func(i + 1, (q * 10 + d) % k, s + d, true);
            return temp;
        }
        else
        {
            for(unsigned d = 0; d <= aArray[i]; ++d)
                temp += func(i + 1, (q * 10 + d) % k, s + d, d < aArray[i]);
            return temp;
        }
    }
    else
        //p — левая граница суммы цифр, t — правая.
        if(q == 0 && p <= s && s <= t)
            return 1;
        else
            return 0;
}
void check() {
    num = func(0, 0, 0, false);
    cout << num;
}

aArray[i] — i-ая цифра числа 140. Сам массив выглядит так: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 4, 0 (17 нулей и 1, 4, 0). aArray[17] = 1, aArray[18] = 4, aArray[19] = 0.

A>Вчера попробовал запрограммировать формулу, но сегодня, запустив, получил в качестве ответа ноль(искал количество чисел, не превосходящих 140, делящихся на 13 и с суммой цифр от 11 до 18), хотя ответ должен получиться "3" (39, 65, 78). Можете указать ошибку? Просто дебажить такое очень трудно.

Странно. Поменял условие с if (i != 20) на if (i != 21) и вернул обратно. Теперь выдаёт правильный результат.

А какие именно значения надо сохранять и как их структуризировать? Просто в примере с числами Фибоначчи ясно видно, что хранить надо все значения, чтобы не выполнять функцию с одними и теми же аргументами по несколько раз, но тут как-то всё не очень ясно видно. Каждый раз меняется хотя бы один из параметров.

Здравствуйте, Assasin291, Вы писали:

A>Странно. Поменял условие с if (i != 20) на if (i != 21) и вернул обратно. Теперь выдаёт правильный результат.

Да вроде и с 20 все работает. Скорее всего aArray сдвинут на 1.

A>А какие именно значения надо сохранять и как их структуризировать? Просто в примере с числами Фибоначчи ясно видно, что хранить надо все значения, чтобы не выполнять функцию с одними и теми же аргументами по несколько раз, но тут как-то всё не очень ясно видно. Каждый раз меняется хотя бы один из параметров.

Проще всего все числа хранить, в четырехмерном массиве 20x100x162x2.

Можно заполнять не рекурсивно, а послойно начиная с i = 20 и уменьшая i до нуля, тогда надо будет хранить только массив d[q][s][l]. Но проще всего дополнить рекурсивное решение мемоизацией всего.

Здравствуйте, Vintik_69, Вы писали:

V_>Можно заполнять не рекурсивно, а послойно начиная с i = 20 и уменьшая i до нуля, тогда надо будет хранить только массив d[q][s][l]. Но проще всего дополнить рекурсивное решение мемоизацией всего.

Спасибо, просто я думал, что сохранять все данные — это большое расточительство. Надеялся, что можно сэкономить без особых (в т. ч. и умственных) затрат.

Здравствуйте, baxton_ulf, Вы писали:

_>сдается мне тут тоже перебор. очень интересно на имплементацию посмотреть, выложи потом plz

Вот что у меня получилось:

#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;

unsigned long long a, b, numA, numB, ****resultArray, ****forBArray;
unsigned p, t, k;
unsigned *aArray = new unsigned[20], //массив цифр числа A
         *bArray = new unsigned[20], //массив цифр числа B
         bLength = 20, aLength = 20; //их длины

void getData() {
//получаю данные из файла
    ifstream in ("input.txt");
    in >> k >> a >> b >> p >> t;
    --a;
    in.close();
}

unsigned long long func(unsigned i, unsigned q, unsigned s, bool l) {
    if(i != 20)
    {//если i == 20, значит записано уже 20 цифр
        unsigned tempQ, tempS;
        unsigned long long temp = 0;

        if(l)
        {
            for (unsigned d = 0; d <= 9; ++d)
            {
                tempQ = (q * 10 + d) % k;
                tempS = s + d;
                 if (i != 19 && resultArray[i + 1][tempQ][tempS][l] != ULONG_LONG_MAX)
                //если нужного результата нет в массиве или записано уже 20 цифр, то вызываем func
                //иначе — берём данные из "таблицы"
                    temp += resultArray[i + 1][tempQ][tempS][l];
                 else
                    temp += func(i + 1, tempQ, tempS, true);
            }

            //сохраняем результат, который собираемся возвращать
             if (resultArray[i][q][s][l] == ULONG_LONG_MAX)
                 resultArray[i][q][s][l] = temp;

            return temp;
        }
        else
        {
            for(unsigned d = 0; d <= aArray[i]; ++d)
                //думаю, здесь меморизировать ничего не надо в силу уникальности полученных результатов
                temp += func(i + 1, (q * 10 + d) % k, s + d, d < aArray[i]);

            return temp;
        }

    }
    else
        if(q == 0 && p <= s && s <= t)
            return 1L;
        else
            return 0L;
}

void check() {
    --a;
    ofstream out("output.txt");
    numA = func(0, 0, 0, false);
    //чтобы не переписывать функцию для нахождения F(B), просто меняю ссылки
    aArray = bArray;
    numB = func(0, 0, 0, false);
    cout << (unsigned long long)(numB - numA); //вот полученный ответ
    out << numA;
    out.close();
}

int main() {
    getData();

    //инициализация массивов, в которых будут храниться результаты выполнения func для чисел A и B соответственно
    resultArray = new unsigned long long ***[20];
    forBArray = new unsigned long long ***[20];
    for(int i = 0; i < 20; ++i)
    {
        resultArray[i] = new unsigned long long **[200];
        forBArray[i] = new unsigned long long **[200];
        for (int j = 0; j < 200; ++j)
        {
            resultArray[i][j] = new unsigned long long *[162];
            forBArray[i][j] = new unsigned long long *[162];
            for (int k = 0; k < 162; ++k)
            {
                resultArray[i][j][k] = new unsigned long long [2];
                forBArray[i][j][k] = new unsigned long long [2];
                resultArray[i][j][k][0] = resultArray[i][j][k][1] = forBArray[i][j][k][0] = forBArray[i][j][k][1] = ULONG_LONG_MAX;
            }
        }
    }

    unsigned long long d = 10, aTemp = a, bTemp = b;
    unsigned aElement, bElement;

    //преобразуем числа A и B в массивы цифр
    for(int j = 19; j >= 0; --j, aTemp /= d, bTemp /= d)
    {
        aElement = aArray[j] = aTemp % d;
        bElement = bArray[j] = bTemp % d;
        if(bTemp == 0 && bArray[j + 1] != 0)
            bLength = j + 1;
        if(aTemp == 0 && aArray[j + 1] != 0)
            aLength = j + 1;
    }

    check();
    return 0;
}

Здравствуйте, Assasin291, Вы писали:

_>>сдается мне тут тоже перебор. очень интересно на имплементацию посмотреть, выложи потом plz

A>Вот что у меня получилось:

Можно немного упростить. Во-первых, мемоизацию лучше делать не в месте вызова, в вместо собственно вычисления. Во-вторых, поскольку задача олимпиадная и ограничения известны, можно массив для мемоизации выделять не динамически. В-третьих, действительно, из мемоизации можно убрать булевый параметр, если немного код подвигать:

#include <iostream>
#include <vector>

using namespace std;

vector<int> parse(int n) {
  vector<int> res;
  while (n > 9) {
    res.push_back(n%10);
    n/=10;
  }
  res.push_back(n);
  reverse(res.begin(), res.end());
  return res;
}

int S, T, k;
long long d[21][170][110];

long long calc(const vector<int>& num, int i, int s, int q) {
  if (i == num.size()) {
    return s <= T && S <= s && q == 0;
  }

  long long& res = d[i][s][q];
  if (res == -1) {
    res = 0;
    for (int d=0; d < 10; d++) {
      res += calc(num, i+1, s+d, (q*10 + d)%k);
    }
  }
  return res;
}

long long solve(const vector<int>& num) {
  memset(d, -1, sizeof(d));
  long long res = 0;
  int s = 0, q = 0;
  for (int i=0; i < num.size(); i++) {
    for (int d=0; d < num[i]; d++) {
      res += calc(num, i+1, s + d, (q*10 + d)%k);
    }
    s += num[i];
    q = (q*10 + num[i])%k;
  }
  return res + (s <= T && S <= s && q == 0);
}

int  main() {
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);

  long long A, B;
  cin >> k >> A >> B >> S >> T;
  cout << solve(parse(B)) - solve(parse(A-1)) << endl;
}

Здравствуйте, Vintik_69, Вы писали:

Спасибо, заставило задуматься и подразобраться с ДП

В качестве мелкого занудства:

А где мемоизация? В смысле массив d не заполнятся посчитанными значениями.
Почему не отсекаются заведомо не проходные значения — когда сумма цифр префикса вышла из диапазона?