@Maksym122

Как оптимизировать код с++ с рекурсией в времени?

Текст задачи на картинке, непонятные слова можете перевести 662501b7d9ccb024708511.png
Вот мой код:
#include <iostream>

using namespace std;

int F(int n) {
    if (n % 10 > 0) {
        return n % 10;
    } else if (n == 0) {
        return 0;
    } else {
        return F(n / 10);
    }
}

int S(int p, int q) {
    if (p == q) {
        return F(p);
    } else {
        return F(p) + S(p + 1, q);
    }
}

int main() {
    int p, q;
    cin >> p >> q;
    cout << S(p, q) << endl;
    return 0;
}

Он проходит только 50% тестирования, в остальных не хватает времени.
  • Вопрос задан
  • 137 просмотров
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Можно попробовать сделать микрооптимизации: функция F реализуется одним циклом (делите, пока делится на 10, потом берите последнюю цифру). S тоже можно считать циклом, а не рекурсией.

Но скорее всего, этого не хватит. Это решение за O(q*log(q)). Ограничения на числа в условии не видно, но если там что-то порядка 2000000000, то ваша программа будет считать несколько секунд.

Надо хорошенько подумать и применить математическую хитрость. Надо как-то считать числа в интервале p...q пачками, а не каждое отдельно.

Что такое функция F? Это последняя ненулевая цифра в числе. Давайте вместо суммы значений F счиатать, сколько чисел из интервала дадут вот такое вот значение? Ну просто по последней цифре сложно сказать, сколько там чисел, а вот если еще зафиксировать количество пропущенных в конце нулей, то уже становится понятно, как подсчитать это. Вот допустим, вы считаете последнюю цифру d и там должно быть 3 нуля. Тогда вы ищети числа вида "xxxd000". Или их можно представить в виде d*1000+x*10000 для произвольного неотрицательного x. И вот вам надо подсчитать сколько таких чисел в интервале [p,q]. Ну решите 2 уравнения: d*1000+x*10000 >= p и d*1000+x*10000 <= q

Таким образом вы за несколько арифметических действий и одну проверку можете подсчитать, сколько чисел вида "xxxd000" будут в интервале. Осталось циклом перебрать d от 1 до 9 и количество нулей от 0 до длины q. И вот у вас решение за O(log(q)).

Edit:
Вот код быстрого решения:
int S(int p, int q) {
  int sum = 0;
  for (int d = 1; d < 10; ++d) {
    for (int tens = 1; tens <= q; tens *= 10) {
      int left = p - d*tens;
      if (left < 0) left = 0;
      else left = (left + 10*tens-1)/(10*tens);
      int right = q - d*tens;
      if (right < 0) right = -1;
      else right /= 10*tens;
      sum += d*(right - left + 1);      
     }
  }
  return sum;
}
Ответ написан
mayton2019
@mayton2019
Bigdata Engineer
Здесь медленным является скорее всего вычисление функции S.

int S(int p, int q) {
    if (p == q) {
        return F(p);
    } else {
        return F(p) + S(p + 1, q);
    }
}


Вот для входных параметров p = 0 и q = 0xFFFF_FFFF например нам придется
вращать пустой цикл 4 миллиарда раз (или 4 млр раз проваливаться в рекурсию)
и все просто для того чтобы посчитать сумму

F(p) + F(q)

Можно убрать эти холостые вычисления и таким образом ускорить прохождение тестов.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы