Digamos que tenhamos um número inteiro não negativo que seja "robusto" (ou seja, "pesado") se o valor médio do dígito for maior que 7.

O número 6959 é "robusto" porque:

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

O número 1234 não é, porque:

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

Escreva uma função, em qualquer idioma,

HeftyDecimalCount(a, b)

que, quando fornecidos dois números inteiros positivos aeb retorna um número inteiro indicando quantos números inteiros "pesados" estão dentro do intervalo [a..b], inclusive.

Por exemplo, dado a = 9480 eb = 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

Dois dos números nesse intervalo são "pesados" e, portanto, a função deve retornar 2.

Algumas diretrizes:

• suponha que nem a ou b exceda 200.000.000.
• uma solução n-quadrado funcionará, mas será lenta - qual é a velocidade mais rápida que podemos resolver?

O problema pode ser resolvido em O (polylog (b)).

Definimos f(d, n)como o número de inteiros de até d dígitos decimais com soma de dígitos menor ou igual a n. Pode-se ver que essa função é dada pela fórmula

Vamos derivar essa função, começando com algo mais simples.

A função h conta o número de maneiras de escolher elementos d - 1 de um conjunto múltiplo contendo n + 1 elementos diferentes. É também o número de maneiras de particionar n em compartimentos d, o que pode ser facilmente visto construindo cercas d-1 em torno de n e somando cada seção separada. Exemplo para 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

Portanto, h conta todos os números com uma soma de dígitos de n e d dígitos. Exceto que ele só funciona para n menos de 10, pois os dígitos são limitados de 0 a 9. Para corrigir isso para os valores de 10 a 19, precisamos subtrair o número de partições com um compartimento com um número maior que 9, que chamarei de compartimentos transbordados a partir de agora.

Este termo pode ser calculado reutilizando h da seguinte maneira. Contamos o número de maneiras de particionar n - 10 e, em seguida, escolhemos um dos compartimentos para colocar os 10, o que resulta no número de partições com um compartimento transbordado. O resultado é a seguinte função preliminar.

Continuamos dessa maneira por n menor ou igual a 29, contando todas as maneiras de particionar n - 20 e, em seguida, escolhendo 2 posições onde colocamos os 10's, contando assim o número de partições contendo 2 posições excedentes.

Mas, neste ponto, temos que ter cuidado, porque já contamos as partições com 2 posições transbordadas no termo anterior. Não só isso, mas na verdade contamos duas vezes. Vamos usar um exemplo e examinar a partição (10,0,11) com a soma 21. No termo anterior, subtraímos 10, calculamos todas as partições dos 11 restantes e colocamos os 10 em um dos 3 compartimentos. Mas essa partição específica pode ser alcançada de duas maneiras:

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

Como também contamos essas partições uma vez no primeiro termo, a contagem total de partições com 2 compartimentos excedidos é de 1 - 2 = -1, portanto, precisamos contá-las mais uma vez adicionando o próximo termo.

Pensando um pouco mais sobre isso, descobrimos em breve que o número de vezes que uma partição com um número específico de posições transbordadas é contada em um termo específico pode ser expressa pela tabela a seguir (a coluna i representa o termo i, partições de linha j com j transbordada caixas).

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

Sim, é o triângulo Pascal. A única contagem em que estamos interessados ​​é a da primeira linha / coluna, ou seja, o número de partições com zero compartimentos excedidos. E como a soma alternada de cada linha, exceto a primeira, é igual a 0 (por exemplo, 1 - 4 + 6 - 4 + 1 = 0), é assim que nos livramos deles e chegamos à penúltima fórmula.

Esta função conta todos os números com dígitos d com uma soma de dígitos de n.

Agora, e os números com soma de dígitos menor que n? Podemos usar uma recorrência padrão para binômios mais um argumento indutivo, para mostrar que

conta o número de partições com soma de dígitos no máximo n. E disso f pode ser derivado usando os mesmos argumentos que para g.

Usando esta fórmula, podemos, por exemplo, encontrar o número de números pesados ​​no intervalo de 8000 a 8999 1000 - f(3, 20), pois , porque existem milhares de números nesse intervalo, e temos que subtrair o número de números com soma de dígitos menor ou igual a 28 enquanto deduz que o primeiro dígito já contribui com 8 para a soma do dígito.

Como um exemplo mais complexo, vejamos o número de números pesados ​​no intervalo 1234..5678. Podemos primeiro ir de 1234 a 1240 nas etapas de 1. Em seguida, vamos de 1240 a 1300 nas etapas de 10. A fórmula acima nos fornece o número de números pesados ​​em cada intervalo:

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))

Agora vamos de 1300 a 2000 em etapas de 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))

De 2000 a 5000 em etapas de 1000:

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

Agora temos que reduzir o tamanho da etapa novamente, passando de 5000 para 5600 nas etapas de 100, de 5600 para 5670 nas etapas de 10 e, finalmente, de 5670 para 5678 nas etapas de 1.

Um exemplo de implementação do Python (que recebeu algumas otimizações e testes enquanto isso):

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

Editar : substituiu o código por uma versão otimizada (que parece ainda mais feia que o código original). Também consertei alguns casos de canto enquanto eu estava nisso. heavy(1234, 100000000)leva cerca de um milissegundo na minha máquina.

Recupere e use permutações.

Suponha que definamos uma função geral que encontre os valores entre aeb com um peso maior que x:

heavy_decimal_count(a,b,x)

Com o seu exemplo de a = 8675 eb = 8689, o primeiro dígito é 8, então jogue-o fora - a resposta será igual a 675 a 689 e novamente de 75 a 89.

O peso médio dos dois primeiros dígitos 86 é 7, portanto os dígitos restantes precisam de um peso médio superior a 7 para se qualificar. Assim, a chamada

heavy_decimal_count(8675,8689,7)

é equivalente a

heavy_decimal_count(75,89,7)

Portanto, nosso alcance para o (novo) primeiro dígito é de 7 a 8, com estas possibilidades:

7: 5-9
8: 0-9

Para 7, ainda precisamos de uma média superior a 7, que só pode vir de um dígito final de 8 ou 9, fornecendo 2 valores possíveis.

Para 8, precisamos de uma média superior a 6, que só pode vir de um dígito final de 7-9, fornecendo 3 valores possíveis.

Assim, 2 + 3 produz 5 valores possíveis.

O que está acontecendo é que o algoritmo está começando com o número de 4 dígitos e dividindo-o em problemas menores. A função se chamaria repetidamente com versões mais fáceis do problema até que ele tenha algo com que possa lidar.

Talvez você possa pular muitos candidatos no intervalo de a para b acumulando seu "peso".

se você souber o comprimento do seu número, sabe que todos os dígitos podem alterar o peso em apenas 1 / comprimento.

Portanto, se você começar com um número que não é pesado, poderá calcular o próximo número que será pesado, se você os aumentar em um.

No exemplo acima, iniciando com 8680 avg = 5,5, que fica a 7-5,5 = 1,5 ponto da sua borda de peso, você saberia que existem 1,5 / (1/4) = 6 números no meio, que NÃO são pesados.

Isso deve ser o truque!

Que tal uma função recursiva simples? Para simplificar, calcula todos os números pesados ​​com digitsdígitos e uma soma mínima de dígitos 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'.

Implementou isso em python e encontrou todos os números pesados ​​de 9 dígitos em ~ 2 segundos. Um pouco de programação dinâmica poderia melhorar isso.

Esta é uma solução possível.

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, para o intervalo [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;}

//o exercício

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

//os resultados

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