Katakanlah kita memiliki bilangan bulat non-negatif yang "kekar" (yaitu, "berat") jika nilai digit rata-rata lebih besar dari 7.

Angka 6959 adalah "kekar" karena:

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

Angka 1234 tidak, karena:

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

Tulis fungsi, dalam bahasa apa pun,

HeftyDecimalCount(a, b)

yang, ketika memberikan dua bilangan bulat positif a dan b mengembalikan bilangan bulat yang menunjukkan berapa banyak bilangan bulat "kekar" dalam interval [a..b], inklusif.

Misalnya, diberi a = 9480 dan b = 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

Dua angka dalam rentang ini adalah "kekar" dan karenanya fungsi harus mengembalikan 2.

Beberapa pedoman:

• berasumsi bahwa a atau b tidak melebihi 200.000.000.
• solusi n-squared akan bekerja, tetapi akan lambat - apa yang tercepat yang bisa kita selesaikan ini?

Masalahnya dapat diselesaikan di O (polylog (b)).

Kami mendefinisikan f(d, n)jumlah bilangan bulat hingga d angka desimal dengan jumlah digit kurang dari atau sama dengan n. Dapat dilihat bahwa fungsi ini diberikan oleh rumus

Mari kita turunkan fungsi ini, dimulai dengan sesuatu yang lebih sederhana.

Fungsi h menghitung jumlah cara untuk memilih elemen d-1 dari multi-set yang berisi n + 1 elemen berbeda. Ini juga merupakan sejumlah cara untuk mem-partisi n menjadi d bin, yang dapat dengan mudah dilihat dengan membangun pagar d-1 di sekitar n dan menyimpulkan setiap bagian yang terpisah. Contoh untuk 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

Jadi, h menghitung semua angka yang memiliki jumlah digit n dan d. Kecuali itu hanya bekerja untuk n kurang dari 10, karena digit terbatas pada 0 - 9. Untuk memperbaikinya untuk nilai 10 - 19, kita perlu mengurangi jumlah partisi yang memiliki satu bin dengan angka lebih besar dari 9, yang akan saya sebut nampan berlebih mulai sekarang.

Istilah ini dapat dihitung dengan menggunakan kembali h dengan cara berikut. Kami menghitung jumlah cara untuk mempartisi n - 10, dan kemudian memilih salah satu nampan untuk memasukkan 10, yang menghasilkan jumlah partisi yang memiliki satu nampan berlebih. Hasilnya adalah fungsi pendahuluan berikut.

Kami melanjutkan cara ini untuk n kurang atau sama dengan 29, dengan menghitung semua cara mempartisi n - 20, lalu memilih 2 nampan tempat kami menempatkan 10, ke dalam, dengan demikian menghitung jumlah partisi yang berisi 2 nampan berlebih.

Tetapi pada titik ini kita harus berhati-hati, karena kita sudah menghitung partisi memiliki 2 nampan berlebih pada periode sebelumnya. Bukan hanya itu, tetapi sebenarnya kami menghitungnya dua kali. Mari kita gunakan contoh dan lihat partisi (10,0,11) dengan jumlah 21. Dalam istilah sebelumnya, kita kurangi 10, hitung semua partisi dari sisa 11 dan masukkan 10 ke dalam salah satu dari 3 tempat sampah. Tetapi partisi khusus ini dapat dicapai dengan satu dari dua cara:

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

Karena kami juga menghitung partisi ini sekali dalam jangka waktu pertama, jumlah total partisi dengan 2 nampan berlebih berjumlah 1 - 2 = -1, jadi kami perlu menghitungnya sekali lagi dengan menambahkan istilah berikutnya.

Berpikir tentang ini sedikit lebih, kami segera menemukan bahwa berapa kali sebuah partisi dengan jumlah tertentu dari tempat sampah yang berlebih dihitung dalam istilah tertentu dapat diekspresikan oleh tabel berikut ini (kolom i mewakili istilah i, baris j partisi dengan j overflown sampah).

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

Ya, itu segitiga Pascal. Satu-satunya penghitungan yang kami minati adalah yang ada di baris / kolom pertama, yaitu jumlah partisi dengan nol tempat sampah berlebih. Dan karena jumlah bolak-balik dari setiap baris tetapi yang pertama sama dengan 0 (misalnya 1 - 4 + 6 - 4 + 1 = 0), itulah cara kita menyingkirkannya dan sampai pada rumus kedua dari belakang.

Fungsi ini menghitung semua angka dengan d digit memiliki jumlah digit n.

Sekarang, bagaimana dengan angka dengan jumlah digit kurang dari n? Kita dapat menggunakan perulangan standar untuk binomial ditambah argumen induktif, untuk menunjukkannya

menghitung jumlah partisi dengan digit-sum paling banyak n. Dan dari sini f dapat diturunkan dengan menggunakan argumen yang sama seperti untuk g.

Dengan menggunakan rumus ini, misalnya kita dapat menemukan jumlah angka berat dalam interval dari 8000 hingga 8999 sebagai 1000 - f(3, 20) , karena ada ribuan angka dalam interval ini, dan kita harus mengurangi jumlah angka dengan jumlah digit kurang dari atau sama dengan 28 sambil memperhitungkan bahwa digit pertama sudah memberikan kontribusi 8 ke jumlah digit.

Sebagai contoh yang lebih kompleks mari kita lihat jumlah angka berat dalam interval 1234..5678. Pertama-tama kita dapat beralih dari 1234 ke 1240 dalam langkah-langkah 1. Kemudian kita beralih dari 1240 hingga 1300 dalam langkah-langkah 10. Rumus di atas memberi kita jumlah angka berat dalam setiap interval seperti itu:

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

Sekarang kita beralih dari 1300 ke 2000 dalam langkah 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))

Dari 2000 hingga 5000 dalam langkah 1000:

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

Sekarang kita harus mengurangi ukuran langkah lagi, dari 5000 menjadi 5600 di langkah 100, dari 5600 ke 5670 di langkah 10 dan akhirnya dari 5670 menjadi 5678 di langkah 1.

Contoh implementasi Python (yang menerima sedikit optimisasi dan pengujian sementara itu):

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

Sunting : Mengganti kode dengan versi yang dioptimalkan (yang terlihat lebih jelek dari kode aslinya). Juga memperbaiki beberapa kasus sudut saat saya berada di sana. heavy(1234, 100000000)membutuhkan waktu sekitar satu milidetik pada mesin saya.

Perulangan, dan gunakan permutasi.

Misalkan kita mendefinisikan fungsi umum yang menemukan nilai antara a dan b dengan bobot lebih dari x:

heavy_decimal_count(a,b,x)

Dengan contoh Anda dari a = 8675 ke b = 8689, angka pertama adalah 8, jadi buanglah - jawabannya akan sama dengan 675 hingga 689, dan lagi dari 75 menjadi 89.

Berat rata-rata dari dua digit pertama 86 adalah 7, sehingga digit yang tersisa membutuhkan berat rata-rata lebih dari 7 untuk memenuhi syarat. Demikian panggilan

heavy_decimal_count(8675,8689,7)

setara dengan

heavy_decimal_count(75,89,7)

Jadi rentang kami untuk digit pertama (baru) adalah 7 hingga 8, dengan kemungkinan ini:

7: 5-9
8: 0-9

Untuk 7, kita masih membutuhkan rata-rata lebih dari 7, yang hanya bisa berasal dari angka akhir 8 atau 9, memberi kita 2 nilai yang mungkin.

Untuk 8, kita membutuhkan rata-rata lebih dari 6, yang hanya bisa berasal dari digit akhir 7-9, memberi kita 3 nilai yang mungkin.

Jadi, 2 + 3 menghasilkan 5 nilai yang mungkin.

Apa yang terjadi adalah bahwa algoritma tersebut dimulai dengan angka 4 digit dan membaginya menjadi masalah yang lebih kecil. Fungsi ini akan menyebut dirinya berulang kali dengan versi masalah yang lebih mudah sampai memiliki sesuatu yang dapat ditangani.

Mungkin Anda dapat melewati banyak kandidat dalam interval dari a ke b dengan mengumpulkan "berat" mereka.

jika Anda tahu panjang angka Anda, Anda tahu bahwa setiap digit dapat mengubah berat hanya 1 / panjang.

Jadi, jika Anda mulai dari satu angka yang tidak berat Anda harus dapat menghitung angka berikutnya yang akan berat, jika Anda menambahnya dengan satu.

Dalam contoh Anda di atas mulai dari 8680 rata-rata = 5,5, yang 7-5,5 = 1,5 poin dari Anda batas berat, Anda akan tahu bahwa ada 1,5 / (1/4) = 6 angka di antaranya, yang TIDAK berat.

Itu seharusnya untuk trik!

Bagaimana dengan fungsi rekursif sederhana? Untuk menjaga hal-hal sederhana, ini menghitung semua angka berat dengan digitsdigit, dan jumlah digit minimal 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'.

Diimplementasikan ini dalam python dan menemukan semua angka berat 9 digit dalam ~ 2 detik. Sedikit pemrograman dinamis dapat meningkatkan ini.

Ini adalah salah satu solusi yang mungkin.

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, untuk interval [a, b] itu adalah 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;}

//Latihan

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

//hasil

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