Допустим, у нас есть неотрицательное целое число, которое является «здоровенным» (то есть «тяжелым»), если его среднее значение цифры больше 7.

Число 6959 "здоровенное", потому что:

(6 + 9 + 5 + 9) / 4 = 7,5

Число 1234 нет, потому что:

(1 + 2 + 3 + 4) / 4 = 2,5

Написать функцию на любом языке,

HeftyDecimalCount(a, b)

который, при наличии двух положительных целых чисел a и b, возвращает целое число, указывающее, сколько «здоровенных» целых чисел находится в интервале [a..b] включительно.

Например, учитывая а = 9480 и б = 9489:

9480   (9+4+8+0)/4 21/4 = 5.25 
9481   (9+4+8+1)/4 22/4 = 5.5
9482   (9+4+8+2)/4 23/4 = 5.75  
9483   (9+4+8+3)/4 24/4 = 6    
9484   (9+4+8+4)/4 25/4 = 6.25     
9485   (9+4+8+5)/4 26/4 = 6.5 
9486   (9+4+8+6)/4 27/4 = 6.75  
9487   (9+4+8+7)/4 28/4 = 7
9488   (9+4+8+8)/4 29/4 = 7.25   hefty 
9489   (9+4+8+9)/4 30/4 = 7.5    hefty

Два числа в этом диапазоне являются «здоровенными», поэтому функция должна возвращать 2.

Некоторые рекомендации:

• предположим, что ни a, ни b не превышают 200 000 000.
• n-квадратное решение будет работать, но будет медленным - что мы можем решить быстрее всего?

Проблема может быть решена в O (polylog (b)).

Мы определяем f(d, n)число целых чисел до d десятичных цифр с суммой цифр, меньшей или равной n. Видно, что эта функция задается формулой

Давайте выведем эту функцию, начиная с чего-то более простого.

Функция h считает количество способов выбора d - 1 элементов из множества, содержащего n + 1 различных элементов. Это также количество способов разбить n на d бинов, что легко увидеть, построив d - 1 заборы вокруг n и суммируя каждый отдельный раздел. Пример для n = 2, d = 3 ':

3-choose-2     fences        number
-----------------------------------
11             ||11          002
12             |1|1          011
13             |11|          020
22             1||1          101
23             1|1|          110
33             11||          200

Таким образом, h считает все числа, имеющие цифру-сумму из n и d цифр. За исключением того, что он работает только для n менее 10, так как цифры ограничены 0 - 9. Чтобы исправить это для значений 10 - 19, нам нужно вычесть количество разделов, имеющих один бин с числом больше 9, которое теперь я буду называть переполненными бинами.

Этот термин может быть вычислен путем повторного использования h следующим образом. Мы подсчитываем количество способов разбиения n - 10, а затем выбираем один из бинов, в который нужно поместить 10, в результате чего количество разделов имеет один переполненный бин. Результатом является следующая предварительная функция.

Мы продолжаем этот путь для n, меньшего или равного 29, подсчитывая все способы разбиения n - 20, затем выбирая 2 ячейки, в которые мы помещаем десятки, таким образом подсчитывая количество разделов, содержащих 2 переполненных ячейки.

Но в этот момент мы должны быть осторожны, потому что мы уже посчитали разделы, имеющие 2 переполненных бина в предыдущем семестре. Не только это, но на самом деле мы насчитали их дважды. Давайте рассмотрим пример и рассмотрим разбиение (10,0,11) с суммой 21. В предыдущем семестре мы вычли 10, вычислили все разделы из оставшихся 11 и поместили 10 в один из 3 лотков. Но этот конкретный раздел может быть достигнут одним из двух способов:

(10, 0, 1) => (10, 0, 11)
(0, 0, 11) => (10, 0, 11)

Поскольку мы также посчитали эти разделы один раз в первом члене, общее количество разделов с 2 переполненными ячейками составляет 1 - 2 = -1, поэтому нам нужно подсчитать их еще раз, добавив следующий член.

Подумав об этом немного подробнее, мы вскоре обнаружим, что число раз, которое раздел с определенным количеством переполненных бинов подсчитывается в определенном термине, может быть выражено следующей таблицей (столбец i представляет термин i, строка j разделов с j переполнением бункера).

1 0 0 0 0 0 . .
1 1 0 0 0 0 . .
1 2 1 0 0 0 . .
1 4 6 4 1 0 . .
. . . . . . 
. . . . . . 

Да, это треугольник Паскаля. Единственный интересующий нас счет - это число в первой строке / столбце, то есть количество разделов с нулевыми переполненными ячейками. А так как переменная сумма каждой строки, кроме первой, равна 0 (например, 1 - 4 + 6 - 4 + 1 = 0), мы избавляемся от них и получаем предпоследнюю формулу.

Эта функция считает все числа с d цифрами, имеющими сумму цифр n.

А как насчет чисел с цифрой-суммой меньше n? Мы можем использовать стандартное повторение для биномов плюс индуктивный аргумент, чтобы показать, что

подсчитывает количество разделов с цифрой-суммой не более n. И из этого f можно получить, используя те же аргументы, что и для g.

Используя эту формулу, мы можем, например, найти число тяжелых чисел в интервале от 8000 до 8999, поскольку 1000 - f(3, 20), поскольку в этом интервале есть тысячи чисел, мы должны вычесть число чисел с суммой цифр, меньшей или равной 28 принимая во внимание, что первая цифра уже вносит 8 в сумму цифр.

В качестве более сложного примера давайте посмотрим на число тяжелых чисел в интервале 1234..5678. Сначала мы можем перейти с 1234 до 1240 с шагом 1. Затем мы с 1240 до 1300 с шагом 10. Приведенная выше формула дает нам число тяжелых чисел в каждом таком интервале:

1240..1249:  10 - f(1, 28 - (1+2+4))
1250..1259:  10 - f(1, 28 - (1+2+5))
1260..1269:  10 - f(1, 28 - (1+2+6))
1270..1279:  10 - f(1, 28 - (1+2+7))
1280..1289:  10 - f(1, 28 - (1+2+8))
1290..1299:  10 - f(1, 28 - (1+2+9))

Теперь мы идем от 1300 до 2000 с шагом 100:

1300..1399:  100 - f(2, 28 - (1+3))
1400..1499:  100 - f(2, 28 - (1+4))
1500..1599:  100 - f(2, 28 - (1+5))
1600..1699:  100 - f(2, 28 - (1+6))
1700..1799:  100 - f(2, 28 - (1+7))
1800..1899:  100 - f(2, 28 - (1+8))
1900..1999:  100 - f(2, 28 - (1+9))

От 2000 до 5000 с шагом 1000:

2000..2999:  1000 - f(3, 28 - 2)
3000..3999:  1000 - f(3, 28 - 3)
4000..4999:  1000 - f(3, 28 - 4)

Теперь нам нужно снова уменьшить размер шага: с 5000 до 5600 с шагом 100, с 5600 до 5670 с шагом 10 и, наконец, с 5670 до 5678 с шагом 1.

Пример реализации Python (который получил небольшую оптимизацию и тестирование):

def binomial(n, k):
    if k < 0 or k > n:
        return 0
    result = 1
    for i in range(k):
        result *= n - i
        result //= i + 1
    return result

binomial_lut = [
    [1],
    [1, -1],
    [1, -2, 1],
    [1, -3, 3, -1],
    [1, -4, 6, -4, 1],
    [1, -5, 10, -10, 5, -1],
    [1, -6, 15, -20, 15, -6, 1],
    [1, -7, 21, -35, 35, -21, 7, -1],
    [1, -8, 28, -56, 70, -56, 28, -8, 1],
    [1, -9, 36, -84, 126, -126, 84, -36, 9, -1]]

def f(d, n):
    return sum(binomial_lut[d][i] * binomial(n + d - 10*i, d)
               for i in range(d + 1))

def digits(i):
    d = map(int, str(i))
    d.reverse()
    return d

def heavy(a, b):
    b += 1
    a_digits = digits(a)
    b_digits = digits(b)
    a_digits = a_digits + [0] * (len(b_digits) - len(a_digits))
    max_digits = next(i for i in range(len(a_digits) - 1, -1, -1)
                      if a_digits[i] != b_digits[i])
    a_digits = digits(a)
    count = 0
    digit = 0
    while digit < max_digits:
        while a_digits[digit] == 0:
            digit += 1
        inc = 10 ** digit
        for i in range(10 - a_digits[digit]):
            if a + inc > b:
                break
            count += inc - f(digit, 7 * len(a_digits) - sum(a_digits))
            a += inc
            a_digits = digits(a)
    while a < b:
        while digit and a_digits[digit] == b_digits[digit]:
            digit -= 1
        inc = 10 ** digit
        for i in range(b_digits[digit] - a_digits[digit]):
            count += inc - f(digit, 7 * len(a_digits) - sum(a_digits))
            a += inc
            a_digits = digits(a)
    return count

Редактировать : заменен код на оптимизированную версию (которая выглядит даже хуже, чем исходный код). Также исправил несколько угловых случаев, пока я был на нем. heavy(1234, 100000000)занимает около миллисекунды на моей машине.

Рекурсировать и использовать перестановки.

Предположим, мы определили общую функцию, которая находит значения между a и b с большей тяжестью, чем x:

heavy_decimal_count(a,b,x)

В вашем примере от a = 8675 до b = 8689, первая цифра 8, поэтому отбросьте ее - ответ будет таким же, как 675 до 689, и снова от 75 до 89.

Средний вес первых двух цифр 86 равен 7, поэтому для оценки оставшихся цифр требуется средний вес более 7. Таким образом, вызов

heavy_decimal_count(8675,8689,7)

эквивалентно

heavy_decimal_count(75,89,7)

Таким образом, наш диапазон для (новой) первой цифры составляет от 7 до 8, с этими возможностями:

7: 5-9
8: 0-9

Для 7 нам все еще нужно в среднем более 7, что может быть получено только из последней цифры 8 или 9, что дает нам 2 возможных значения.

Для 8 нам нужно в среднем более 6, что может быть получено только из последней цифры 7-9, что дает нам 3 возможных значения.

Таким образом, 2 + 3 дает 5 возможных значений.

Происходит то, что алгоритм начинается с 4-значного числа и делит его на более мелкие задачи. Функция будет вызывать себя неоднократно с более легкими версиями проблемы, пока у нее не будет чего-то, что она может обработать.

Возможно, вы можете пропустить много кандидатов в интервале от a до b, накапливая их «тяжесть».

если вы знаете длину своего номера, вы знаете, что каждая цифра может изменить вес только на 1 / длину.

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

В приведенном выше примере, начиная с 8680 ср = 5,5, что составляет 7-5,5 = 1,5 балла от границы тяжести, вы знаете, что между ними находится 1,5 / (1/4) = 6 чисел, которые НЕ являются тяжелыми.

Это должно в фокусе!

Как насчет простой рекурсивной функции? Для простоты вычисляются все тяжелые числа с digitsцифрами и минимальной суммой цифр min_sum.

int count_heavy(int digits,int min_sum) {
  if (digits * 9 < min_sum)//impossible (ie, 2 digits and min_sum=19)
    return 0; //this pruning is what makes it fast

  if (min_sum <= 0)
      return pow(10,digits);//any digit will do,
      // (ie, 2 digits gives 10*10 possibilities)

  if (digits == 1)
  //recursion base
    return 10-min_sum;//only the highest digits

  //recursion step
  int count = 0;
  for (i = 0; i <= 9; i++)
  {
     //let the first digit be i, then
     count += count_heavy(digits - 1, min_sum - i);
  }
  return count;
}

count_heavy(9,7*9+1); //average of 7,thus sum is 7*9, the +1 is 'exceeds'.

Реализовано это в python, и он нашел все 9-значные числа за ~ 2 секунды. Немного динамического программирования может улучшить это.

Это одно из возможных решений.

public int heavy_decimal_count(int A, int B)
{
    int count = 0;                       
    for (int i = A; i <= B; i++)
    {
        char[] chrArray = i.ToString().ToCharArray();
        float sum = 0f;
        double average = 0.0f;
        for (int j = 0; j < chrArray.Length; j++)
        {
            sum = sum + (chrArray[j] - '0');                   
        }
        average = sum / chrArray.Length;                
        if (average > 7)
            count++;
    }
    return count;
}

C, для интервала [a, b] это O (ba)

c(n,s,j){return n?c(n/10,s+n%10,j+1):s>7*j;}

HeftyDecimalCount(a,b){int r; for(r=0;a<=b;++a)r+=c(a,0,0); return r;}

//упражнение

main()
{
 printf("[9480,9489]=%d\n", HeftyDecimalCount(9480,9489));
 printf("[0,9489000]=%d\n", HeftyDecimalCount(9480,9489000));
 return 0;
}

//результаты

//[9480,9489]=2
//[0,9489000]=66575