Не проходит лимит по времени (считаем числа с определёной суммой цифр и делимостью)
Подсчитать сколько целых чисел в диапазоне [a, b] делятся на 11 и имеют сумму цифр в диапазоне [c, d]. Ограничения 1 ≤ a ≤ b < 10^18, 1 ≤ с ≤ d < 163. Время расчета не более двух секунд.
Пример:
Вход: a = 11, b = 40, c = 3, d = 6 Выход: 2
Python:
a, b = map(int, input().split())
c, d = map(int, input().split())
count = 0
i = a
while i % 11 != 0:
i = i + 1
first = i
for k in range(first, b+1, 11):
s = sum(map(int, str(k)))
if c <= s <= d:
#print (k, s)
count = count + 1
print(count)
C++:
#include <iostream>
using namespace std;
int digitsSum(int n) {
int sum = 0;
while (n != 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
int main() {
long int a, b, c, d, kil = 0;
cin >> a >> b;
cin >> c >> d;
int first = a;
while (first % 11 != 0) {
first++;
}
for (int i = first; i <= b+1; i = i + 11) {
if (i % 11 == 0 && c <= digitsSum(i) && digitsSum(i) <= d) {
kil = kil + 1;
}
}
cout << kil;
return 0;
}
Ответы (2 шт):
Ваша попытка решить задачу правильная, но не достаточно быстрая. На моей машине простейший цикл на Питоне делает 24 миллиона итераций в секунду. В худшем случае нам нужно сделать 10^18 / 11 итераций.
(10^18 / 11) / (24 * 10^6) ~= 4 * 10^9 секунд ~= 123 года
Быстрые оценки показывают, что пробему не решить заменой языка программирования. Даже если C++ в сто раз быстрее Питона вы получите один год работы, а требуется две секунды. Делайте прикидки чтобы не тратить зря время.
Пусть F(A, r) - множество элементов множества A которые при делении на 11 дают остаток r.
Обозначим через A + x множество каждый элемент которого есть сумма элемента из A и числа x.
Свойство F(A, r) + x = F(A + x, (r + x) mod 11) проверяется непосредственно.
Пусть G(A, s) - множество элементов множества A у которых сумма цифр меньше s.
Вычислим G([0, n), s). Пусть десятичная запись n имеет вид dXX...X, где d - цифра в старшем разряде. Имеем n = dXX...X = 100...0 + (d-1)XX...X.
Полуинтервал [0, dXX...X) разобьём на два [0, 100...0) + [100...0, dXX...X) (здесь + - объединение множеств).
Тогда G([0, dXX...X), s) = G([0, 100...0), s) + G([100...0, dXX...X), s).
Свойство G([100...0, dXX...X), s) = G([0, (d-1)XX...X), s - 1) + 100...0 проверяется непосредственно.
Обозначим Н(A, s, r) = F(G(A, s), r).
H([0, dXX...X), s, r) =
= F(G([0, dXX...X), s), r) =
= F(G([0, 100...0), s) + G([100...0, dXX...X), s), r) =
= F(G([0, 100...0), s), r) + F(G([100...0, dXX...X), s), r) =
= H([0, 100...0), s, r) + F(G([0, (d-1)XX...X), s - 1) + 100...0, r) =
= H([0, 100...0), s, r) + (F(G([0, (d-1)XX...X), s - 1), (r - 100...0) mod 11) + 100...0) =
= H([0, 100...0), s, r) + (H([0, (d-1)XX...X), s - 1, (r - 100...0) mod 11) + 100...0).
Обозначим h(n, s, r) = |H([0, n), s, r)|. Получаем:
h(dXX...X, s, r) =
= h(100...0, s, r) + h((d-1)XX...X, s - 1, (r - 100...0) mod 11).
Ещё одно тождество, которое будет нужно:
h(100...0, s, r) =
= h(10...0, s, r) + h(90...0, s - 1, (r - 10...0) mod 11).
Оба тождества объединяются вместе. По n вычисляем m - максимальная степень 10 меньшая n. Тогда
h(n, s, r) = h(m, s, r) + h(n - m, s - 1, (r - m) mod 11).
База.
h(n<=0, ?, ?) = 0
h(?, s<=0, ?) = 0
h(n=1, s>0, r!=0) = 0
h(n=1, s>0, r=0) = 1
Функцию h нужно кешировать, иначе повторяющиеся вычисления убьют всю скорость.
Последнии шаг. Мы имеем вычислять h на прямоугольниках [0, n)*[0, s). А нам нужны [n1, n2)*[s1, s2).
h([n1, n2)*[s1, s2)) =
= h([n1, n2)*[0, s2)) - h([n1, n2)*[0, s1)) =
= (h([0, n2)*[0, s2)) - h([0, n1)*[0, s2))) -
-(h([0, n2)*[0, s1)) - h([0, n1)*[0, s1))) =
= h(n2, s2) - h(n1, s2) - h(n2, s1) + h(n1, s1)
Теперь код:
import functools
def ten_pow_below(n):
m = 1
while 10 * m < n:
m *= 10
return m
@functools.lru_cache(None)
def h(n, s, r):
if n <= 0:
return 0
if s <= 0:
return 0
if n == 1:
if r == 0:
return 1
return 0
m = ten_pow_below(n)
return h(m, s, r) + h(n - m, s - 1, (r - m) % 11)
def hh(n1, n2, s1, s2):
return h(n2 + 1, s2 + 1, 0) - h(n1, s2 + 1, 0) - h(n2 + 1, s1, 0) + h(n1, s1, 0)
a, b = map(int, input().split())
c, d = map(int, input().split())
print(hh(a, b, c, d))
$ echo -e "11 40\n3 6" | python digital_sum.py 2
P.S. Вывод формулы слишком сложный. Но без него я делал заход за заходом не получая нужный результат. Если у вас есть идеи как объяснить проще, я с удовольствием поплюсую ваш ответ.
Та же идея, что и у Станислава, только сначала вычисляется H(...) для всех степеней 10, возможных сумм цифр и модулей, что потом переиспользуется в вычислении.
И, конечно, без возмутительной элегантности питона.
#include <vector>
#include <cmath>
#include <iostream>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
unsigned short mod11(int value)
{
short mod = value % 11;
if (mod < 0)
{
mod += 11;
}
return mod;
}
size_t sum_array[19][163][11] = {};
template <typename T>
T myPow(T x, int p)
{
if (p == 0)
return 1;
if (p == 1)
return x;
return myPow(x, p - 1) * x;
}
int len(size_t x)
{
int result = 1;
for (; x >= 10; ++result)
{
x /= 10;
}
return result;
}
int left_digit(size_t x)
{
return x / myPow(10UL, len(x) - 1);
}
size_t remove_left_digit(size_t x)
{
return x - left_digit(x) * myPow(10UL, len(x) - 1);
}
int update_mod(int old_mod, int first_digit, int deg)
{
return mod11(old_mod + first_digit * myPow(-1, deg % 2));
}
void initialize_pow_of_10(size_t (&sum_array)[19][163][11])
{
for (int sum = 0; sum < 163; ++sum)
{
sum_array[0][sum][0] = 1;
}
for (int deg = 1; deg < 19; ++deg)
{
for (int sum = 0; sum < 163; ++sum)
{
for (unsigned short mod = 0; mod < 11; ++mod)
{
for (int first_digit = 0; first_digit <= min(sum, 9); ++first_digit)
{
int new_mod = update_mod(mod, first_digit, deg);
sum_array[deg][sum][mod] += sum_array[deg - 1][sum - first_digit][new_mod];
}
}
}
}
}
size_t count_below_sum_below_x_mod11(int sum, int mod, unsigned long x)
{
int n_digits = len(x);
int first_digit = left_digit(x);
if (n_digits == 1)
{
return mod <= x && mod <= sum ? 1 : 0;
}
size_t result = 0;
for (int start_digit = 0; (start_digit < first_digit) && (start_digit <= sum); ++start_digit)
{
int new_mod = update_mod(mod, start_digit, n_digits);
result += sum_array[n_digits - 1][sum - start_digit][new_mod];
}
int new_mod = update_mod(mod, first_digit, n_digits);
result += count_below_sum_below_x_mod11(sum - first_digit, new_mod, remove_left_digit(x));
return result;
}
size_t count_divisible_by_11(unsigned long a, unsigned long b, int sum_min, int sum_max)
{
return count_below_sum_below_x_mod11(sum_max, 0, b) + count_below_sum_below_x_mod11(sum_min - 1, 0, a - 1) -
count_below_sum_below_x_mod11(sum_min - 1, 0, b) - count_below_sum_below_x_mod11(sum_max, 0, a - 1);
}
int main()
{
initialize_pow_of_10(sum_array);
int sum_min, sum_max;
size_t a, b;
cin >> a >> b;
cin >> sum_min >> sum_max;
cout << count_divisible_by_11(a, b, sum_min, sum_max) << endl;
}