Digamos que tenemos un número entero no negativo que es "fuerte" (es decir, "pesado") si su valor de dígito promedio es mayor que 7.

El número 6959 es "fuerte" porque:

(6 + 9 + 5 + 9) / 4 = 7.5

El número 1234 no es porque:

(1 + 2 + 3 + 4) / 4 = 2.5

Escribe una función, en cualquier idioma,

HeftyDecimalCount(a, b)

que, cuando se proporcionan dos enteros positivos a y b, devuelve un entero que indica cuántos enteros "fuertes" están dentro del intervalo [a..b], inclusive.

Por ejemplo, dado a = 9480 yb = 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

Dos de los números en este rango son "fuertes" y, por lo tanto, la función debería devolver 2.

Algunas pautas:

• supongamos que ni aob supera los 200,000,000.
• una solución de n cuadrado funcionará, pero será lenta: ¿cuál es la forma más rápida en que podemos resolver esto?

El problema se puede resolver en O (polylog (b)).

Definimos f(d, n)como el número de enteros de hasta d dígitos decimales con una suma de dígitos menor o igual a n. Se puede ver que esta función viene dada por la fórmula

Derivemos esta función, comenzando con algo más simple.

La función h cuenta el número de formas de elegir d - 1 elementos de un conjunto múltiple que contiene n + 1 elementos diferentes. También es la cantidad de formas de dividir n en d bins, que se pueden ver fácilmente construyendo d - 1 cercas alrededor de n ones y resumiendo cada sección separada. Ejemplo 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

Entonces, h cuenta todos los números que tienen una suma de dígitos de n y d dígitos. Excepto que solo funciona para n menos de 10, ya que los dígitos están limitados a 0 - 9. Para arreglar esto para los valores 10-19, necesitamos restar el número de particiones que tienen un bin con un número mayor que 9, lo que llamaré bins desbordados de ahora en adelante.

Este término puede calcularse reutilizando h de la siguiente manera. Contamos el número de formas de particionar n - 10, y luego elegimos uno de los contenedores para colocar el 10, lo que resulta en el número de particiones que tienen un contenedor desbordado. El resultado es la siguiente función preliminar.

Continuamos de esta manera durante n menos o igual a 29, contando todas las formas de dividir n - 20, luego seleccionando 2 contenedores en los que colocamos los 10, contando así el número de particiones que contienen 2 contenedores desbordados.

Pero en este punto tenemos que tener cuidado, porque ya contamos las particiones que tienen 2 contenedores desbordados en el término anterior. No solo eso, sino que los contamos dos veces. Usemos un ejemplo y observemos la partición (10,0,11) con la suma 21. En el término anterior, restamos 10, calculamos todas las particiones de los 11 restantes y colocamos el 10 en uno de los 3 contenedores. Pero esta partición particular se puede alcanzar de una de dos maneras:

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

Como también contamos estas particiones una vez en el primer término, el recuento total de particiones con 2 contenedores desbordados asciende a 1 - 2 = -1, por lo que debemos contarlos una vez más agregando el siguiente término.

Pensando un poco más en esto, pronto descubrimos que la siguiente tabla puede expresar la cantidad de veces que una partición con un número específico de contenedores desbordados se puede expresar en la siguiente tabla (la columna i representa el término i, la fila j particiones con j desbordado contenedores).

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

Sí, es el triángulo de Pascal. El único recuento que nos interesa es el de la primera fila / columna, es decir, el número de particiones con cero contenedores desbordados. Y dado que la suma alterna de cada fila pero la primera es igual a 0 (por ejemplo, 1 - 4 + 6 - 4 + 1 = 0), así es como nos deshacemos de ellas y llegamos a la penúltima fórmula.

Esta función cuenta todos los números con d dígitos que tienen una suma de dígitos de n.

Ahora, ¿qué pasa con los números con suma de dígitos menor que n? Podemos usar una recurrencia estándar para binomios más un argumento inductivo, para mostrar que

cuenta el número de particiones con suma de dígitos como máximo n. Y de esto se puede derivar f usando los mismos argumentos que para g.

Con esta fórmula, por ejemplo, podemos encontrar el número de números pesados ​​en el intervalo de 8000 a 8999 1000 - f(3, 20), ya que hay miles de números en este intervalo, y tenemos que restar el número de números con una suma de dígitos menor o igual a 28 mientras se cuenta que el primer dígito ya contribuye 8 a la suma de dígitos.

Como un ejemplo más complejo, veamos el número de números pesados ​​en el intervalo 1234..5678. Primero podemos pasar de 1234 a 1240 en pasos de 1. Luego pasamos de 1240 a 1300 en pasos de 10. La fórmula anterior nos da la cantidad de números pesados ​​en 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))

Ahora vamos de 1300 a 2000 en pasos 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 en pasos de 1000:

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

Ahora tenemos que reducir el tamaño del paso nuevamente, pasando de 5000 a 5600 en pasos de 100, de 5600 a 5670 en pasos de 10 y finalmente de 5670 a 5678 en pasos de 1.

Un ejemplo de implementación de Python (que recibió ligeras optimizaciones y pruebas mientras tanto):

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 : reemplazó el código por una versión optimizada (que se ve aún más fea que el código original). También arreglé algunos casos de esquina mientras estaba en eso. heavy(1234, 100000000)toma alrededor de un milisegundo en mi máquina.

Recurrir y usar permutaciones.

Supongamos que definimos una función general que encuentra los valores entre ayb con un peso mayor que x:

heavy_decimal_count(a,b,x)

Con su ejemplo de a = 8675 a b = 8689, el primer dígito es 8, así que tírelo: la respuesta será la misma que 675 a 689, y nuevamente de 75 a 89.

El peso promedio de los primeros dos dígitos 86 es 7, por lo que los dígitos restantes necesitan un peso promedio de más de 7 para calificar. Por lo tanto, la llamada

heavy_decimal_count(8675,8689,7)

es equivalente a

heavy_decimal_count(75,89,7)

Por lo tanto, nuestro rango para el (nuevo) primer dígito es de 7 a 8, con estas posibilidades:

7: 5-9
8: 0-9

Para 7, todavía necesitamos un promedio de más de 7, que solo puede provenir de un dígito final de 8 o 9, lo que nos da 2 valores posibles.

Para 8, necesitamos un promedio de más de 6, que solo puede provenir de un dígito final de 7-9, lo que nos da 3 valores posibles.

Entonces, 2 + 3 produce 5 valores posibles.

Lo que sucede es que el algoritmo comienza con el número de 4 dígitos y lo divide en problemas más pequeños. La función se llamaría repetidamente con versiones más fáciles del problema hasta que tenga algo que pueda manejar.

Quizás pueda omitir muchos candidatos en el intervalo de a a b acumulando su "pesadez".

si conoce la longitud de su número, sabe que cada dígito puede cambiar la pesadez solo 1 / longitud.

Entonces, si comienzas en un número que no es pesado, deberías poder calcular el siguiente número que será pesado, si los aumentas en uno.

En su ejemplo anterior que comienza en 8680 avg = 5.5, que está a 7-5.5 = 1.5 puntos de distancia de su límite de pesadez, sabría que hay 1.5 / (1/4) = 6 números en el medio, que NO son pesados.

Eso debería ser el truco!

¿Qué tal una función recursiva simple? Para simplificar las cosas, calcula todos los números pesados ​​con digitsdígitos y una suma mínima de dígitos de 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'.

Implementé esto en Python y encontró todos los números pesados ​​de 9 dígitos en ~ 2 segundos. Un poco de programación dinámica podría mejorar esto.

Esta es una posible solución.

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 el intervalo [a, b] es 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;}

//el ejercicio

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

//Los resultados

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