Powiedzmy, że mamy nieujemną liczbę całkowitą, która jest „mocna” (to znaczy „ciężka”), jeśli jej średnia wartość cyfry jest większa niż 7.

Liczba 6959 jest „duża”, ponieważ:

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

Liczba 1234 nie jest, ponieważ:

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

Napisz funkcję w dowolnym języku,

HeftyDecimalCount(a, b)

która, pod warunkiem, że dwie dodatnie liczby całkowite aib zwracają liczbę całkowitą wskazującą, ile „mocnych” liczb całkowitych znajduje się w przedziale [a..b], włącznie.

Na przykład, biorąc pod uwagę a = 9480 ib = 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

Dwie liczby w tym zakresie są „mocne”, więc funkcja powinna zwrócić 2.

Niektóre wytyczne:

• zakładamy, że ani a ani b nie przekracza 200 000 000.
• n-kwadratowe rozwiązanie będzie działać, ale będzie wolne - co najszybciej możemy rozwiązać?

Problem można rozwiązać w O (polilog (b)).

Definiujemy f(d, n)liczbę całkowitą do d cyfr dziesiętnych z sumą cyfr mniejszą lub równą n. Można zauważyć, że tę funkcję pełni formuła

Wyprowadźmy tę funkcję, zaczynając od czegoś prostszego.

Funkcja h zlicza liczbę sposobów wyboru d - 1 elementów z zestawu wielu zawierającego n + 1 różnych elementów. Jest to także liczba sposobów podziału n na przedziały d, które można łatwo zobaczyć, budując d - 1 ogrodzenie wokół n i sumując każdą oddzielną sekcję. Przykład dla 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

Zatem h zlicza wszystkie liczby posiadające sumę cyfr cyfr nid. Tyle że działa tylko dla n mniej niż 10, ponieważ cyfry są ograniczone do 0 - 9. Aby to naprawić dla wartości 10–19, musimy odjąć liczbę partycji mających jeden pojemnik z liczbą większą niż 9, którą od tej pory będę nazywał przepełnione pojemniki.

Termin ten można obliczyć, ponownie wykorzystując h w następujący sposób. Bieżemy liczbę sposobów podziału n-10, a następnie wybieramy jeden z pojemników, w które należy wstawić 10, co powoduje, że liczba partycji ma jeden przepełniony pojemnik. Wynikiem jest następująca funkcja wstępna.

Kontynuujemy tę drogę dla n mniejszej lub równej 29, licząc wszystkie sposoby podziału n - 20, a następnie wybierając 2 pojemniki, w których umieszczamy 10, licząc w ten sposób liczbę partycji zawierających 2 przepełnione pojemniki.

Ale w tym momencie musimy być ostrożni, ponieważ już policzyliśmy partycje posiadające 2 przepełnione kosze w poprzednim okresie. Nie tylko to, ale faktycznie policzyliśmy je dwa razy. Użyjmy przykładu i spójrzmy na partycję (10,0,11) z sumą 21. W poprzednim okresie odjęliśmy 10, obliczyliśmy wszystkie partycje pozostałych 11 i umieściliśmy 10 w jednym z 3 przedziałów. Ale do tej konkretnej partycji można dotrzeć na dwa sposoby:

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

Ponieważ te partycje policzyliśmy również raz w pierwszym semestrze, całkowita liczba partycji z 2 przepełnionymi pojemnikami wynosi 1 - 2 = -1, więc musimy je policzyć jeszcze raz, dodając następny termin.

Myśląc o tym trochę więcej, wkrótce odkrywamy, że liczba razy, w której partycja z określoną liczbą przepełnionych pojemników jest liczona w określonym terminie, może być wyrażona w poniższej tabeli (kolumna i reprezentuje termin i, partycje j wiersza z przepełnieniem j pojemniki).

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

Tak, to trójkąt paskalowy. Interesuje nas tylko liczba w pierwszym rzędzie / kolumnie, czyli liczba partycji z zerowymi przepełnionymi pojemnikami. A ponieważ na przemian suma każdego rzędu, ale pierwszy równa się 0 (np. 1 - 4 + 6 - 4 + 1 = 0), w ten sposób pozbywamy się ich i dochodzimy do przedostatniej formuły.

Ta funkcja zlicza wszystkie liczby z cyframi d o sumie cyfr n.

A co z liczbami o sumie cyfr mniejszej niż n? Możemy zastosować standardową powtarzalność dla dwumianów plus argument indukcyjny, aby to pokazać

zlicza liczbę partycji z cyfrą co najwyżej n. I z tego można uzyskać f przy użyciu tych samych argumentów, co dla g.

Korzystając z tego wzoru, możemy na przykład znaleźć liczbę liczb ciężkich w przedziale od 8000 do 8999 1000 - f(3, 20), ponieważ, ponieważ w tym przedziale jest tysiąc liczb, i musimy odjąć liczbę liczb z sumą cyfr mniejszą lub równą 28 jednocześnie przyjmując do wiadomości, że pierwsza cyfra już stanowi 8 w sumie cyfr.

Jako bardziej złożony przykład przyjrzyjmy się liczbie ciężkich liczb w przedziale 1234..5678. Możemy najpierw przejść od 1234 do 1240 w krokach 1. Następnie przechodzimy od 1240 do 1300 w krokach 10. Powyższa formuła podaje nam liczbę ciężkich liczb w każdym takim przedziale:

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

Teraz przechodzimy od 1300 do 2000 w krokach co 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))

Od 2000 do 5000 w krokach co 1000:

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

Teraz musimy ponownie zmniejszyć rozmiar kroku, przechodząc z 5000 do 5600 w krokach co 100, z 5600 do 5670 w krokach co 10, a na koniec z 5670 do 5678 w krokach co 1.

Przykładowa implementacja Pythona (która tymczasem otrzymała niewielkie optymalizacje i testy):

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

Edycja : zastąpiono kod zoptymalizowaną wersją (która wygląda jeszcze brzydiej niż kod oryginalny). Naprawiłem również kilka narożnych skrzynek, gdy byłem przy tym. heavy(1234, 100000000)trwa około milisekundy na moim komputerze.

Powtarzaj i używaj permutacji.

Załóżmy, że definiujemy funkcję ogólną, która znajduje wartości między aib o ciężkości większej niż x:

heavy_decimal_count(a,b,x)

Na przykładzie a = 8675 do b = 8689, pierwsza cyfra to 8, więc wyrzuć ją - odpowiedź będzie taka sama jak 675 do 689, a ponownie od 75 do 89.

Średnia waga pierwszych dwóch cyfr 86 wynosi 7, więc pozostałe cyfry wymagają średniej masy większej niż 7, aby się zakwalifikować. Tak więc połączenie

heavy_decimal_count(8675,8689,7)

jest równa

heavy_decimal_count(75,89,7)

Tak więc nasz zakres (nowej) pierwszej cyfry wynosi od 7 do 8, z następującymi możliwościami:

7: 5-9
8: 0-9

Dla 7 nadal potrzebujemy średnio więcej niż 7, co może pochodzić tylko z ostatniej cyfry 8 lub 9, co daje nam 2 możliwe wartości.

Dla 8 potrzebujemy średnio więcej niż 6, które mogą pochodzić tylko z ostatniej cyfry 7-9, co daje nam 3 możliwe wartości.

Zatem 2 + 3 daje 5 możliwych wartości.

Dzieje się tak, ponieważ algorytm zaczyna się od 4-cyfrowej liczby i dzieli ją na mniejsze problemy. Funkcja wywoływałaby się wielokrotnie z łatwiejszymi wersjami problemu, dopóki nie będzie w stanie poradzić sobie z tym problemem.

Może możesz pominąć wielu kandydatów w przedziale od a do b, kumulując ich „ciężkość”.

jeśli znasz długość swojego numeru, wiesz, że każda cyfra może zmienić ciężar tylko o 1 / długość.

Tak więc, jeśli zaczniesz od jednej liczby, która nie jest ciężka, powinieneś być w stanie obliczyć następną liczbę, która będzie ciężka, jeśli zwiększysz ją o jedną.

W powyższym przykładzie zaczynającym się od 8680 śr. = 5,5, czyli 7-5,5 = 1,5 punktu od granicy ciężkości, będziesz wiedział, że pomiędzy nimi jest 1,5 / (1/4) = 6 liczb, które NIE są ciężkie.

To powinno wystarczyć!

A może prosta funkcja rekurencyjna? Dla uproszczenia oblicza wszystkie ciężkie liczby z digitscyframi i minimalną sumę cyfr 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'.

Zaimplementowano to w pythonie i znaleziono wszystkie 9-cyfrowe ciężkie liczby w ~ 2 sekund. Trochę dynamicznego programowania może to poprawić.

To jedno z możliwych rozwiązań.

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, dla przedziału [a, b] jest to 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;}

//ćwiczenie

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

//wyniki

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