C++Công thức đếm - Đánh số nhà

Đề bài:

• Time limit per test : 0.25 seconds
• Memory limit per test : 32 megabytes

Bạn được giao nhiệm vụ đánh số nhà của $n$ ngôi nhà nằm cạnh nhau trên một con phố. Như các bạn đã biết, các ngôi nhà thuộc cùng một bên thì phải được đánh các số cùng chẵn hoặc cùng lẻ, và những ngôi nhà cạnh nhau được đánh các số liên tiếp nhau. Bạn được yêu cầu đánh số $k$ cho ngôi nhà đầu tiên, do đó $n$ ngôi nhà sẽ được đánh lần lượt các số $k, k + 2, ..., k + 2*(n - 1)$.

Giờ bạn đi đặt hàng in các chữ số để gắn lên tường. Vì vậy, bạn muốn biết rằng với dãy các số nhà cần đánh như trên, bạn cần in bao nhiêu lần mỗi chữ số.

Input:

• Gồm một dòng duy nhất với hai số $k$ và $n$ $(1 ≤ k, n ≤ 10^{18})$.

Output:

• Gồm một dòng với $10$ số nguyên $c_0, c_1, ..., c_9$, trong đó $c_i$ là số chữ số $i$ cần in.

Scoring:

• Subtask $1$ ($20$ điểm): $n = 1$
• Subtask $2$ ($30$ điểm): $n ≤ 10^6$
• Subtask $3$ ($50$ điểm): $n ≤ 10^{18}$

Examples:

//Input
7 4

//Output
0 3 0 1 0 0 0 1 0 1 

//Input
22 7

//Output
1 0 6 3 2 0 1 0 1 0 

//Input
19 97

//Output
10 77 16 29 10 29 10 29 10 30 

Thuật toán 1:

#include <bits/stdc++.h>
using namespace std;
int n, k;
int result[10];
int main() {
    cin >> k >> n;
    for (int i = k; i<= k + (n-1)*2; i+= 2) {
        int j  = i;
        while (j != 0) {
            result[j%10]++;
            j = j / 10;
        }
    }
    for (int i = 0; i<= 9; i++) cout << result[i] << " ";
    return 0;
}

Nhận xét:

• Ta chạy lần lượt các số từ $k$ tới $k + (n-1)*2$, với mỗi số ta tách lần lượt từng chữ số của chúng và cộng thêm vào mảng $result$.
• Thuật toán trên sẽ giúp ta đạt được 2 subtask đầu. Trong trường hợp test lớn cỡ $10^{18}$ thì rõ ràng sẽ bị quá thời gian chạy là $0.25$s. Bởi vậy,ta cần một thuật toán chạy nhanh hơn, hiệu quả hơn trong khi không cần phải chạy lần lượt từng số.
• Để đơn giản hoá bài toán, ta chia quá trình giải thành ba phần:
  • Phần thứ nhất: Tìm số chữ số cần dùng từ $0$ đến $k - 2$
  • Phần thứ hai: Tìm số chữ số cần dùng từ $0$ đến $k + (n-1)*2$
  • Phần thứ ba: Lấy kết quả của phần thứ hai trừ đi kết quả của phần thứ nhất và in ra kết quả.
• Như vậy, ta chuyển bài toán trở về dạng tìm số chữ số cần dùng trong đoạn từ $0$ đến $a$.
• Xét số $a$, và các số từ $0$ đến $a$, ta có thể thể chia chúng ra làm 2 phần:
  • Các số có số chữ số nhỏ hơn $a$. Đối với các số này, mỗi số đều có thể chọn thoải mái từ 0 đến 9, thoả mãn số đầu tiên khác 0 là được.
  • Các số có số chữ số bằng $a$. Đối với các số này, ta cần xét lần lượt từng vị trí và xét từng cách chọn thoả mãn.

Xét phần thứ nhất (số có số chữ số nhỏ hơn số chữ số của số đã cho)

• Ví dụ, xét số $a$ có $6$ chứ số: $563244$
  • Phần 1: Các số có $1$ chứ số, luôn thoả mãn điều kiện nhỏ hơn $a$. Các số có $2, 3, 4, 5$ chữ số cũng thoả mãn điều kiện này.
• Với các số có số chữ số nhỏ hơn, ví dụ có $4$ chữ số và ta xét số lẻ, ta có số lượng số cần xét là : $9×10×10×5 = 4500$ số
  • Ở chữ số hàng nghìn, các số từ $1$ đến $9$ có số lần xuất hiện là $10×10×5$ hay $4500/9$
  • Ở chữ số hàng trăm và hàng chục, các số từ $0$ đến $9$ có số lần xuất hiện là $9×10×5×2$ hay $2×4500/10$
  • Ở chữ số hàng đơn vị, các số $1,3,5,7,9$ có số lần xuất hiện là $9×10×10$ hay $4500/5$
• Trường hợp số có số chữ số là $1$ thì số lần xuất hiện của $1, 3, 5, 7, 9$ được cộng thêm $1$ đơn vị.

Tổng quát phần thứ nhất:

• Gọi số chữ số của số đã cho là n, số chữ số của số đang xét là k.
• Với $1 < k < n$, gọi $C = 9×10^{k-2}×5$ là số số cần xét, ta có:
  • Các số $1, 3, 5, 7, 9$ có số lần xuất hiện là: $C/9 + (k-2)×C/10 + C/5$
  • Số $0$ có số lần xuất hiện là: $(k-2)×C/10$
  • Số $2, 4, 6, 8$ có số lần xuất hiện là: $C/9 + (k-2)×C/10$
• Với $k = 1$, số lần xuất hiện của các số $1, 3, 5, 7, 9$ được cộng thêm $1$ đơn vị.

Xét phần thứ hai (số có số chữ số bằng số chữ số của số đã cho)

• Ví dụ, xét số $a$ có $6$ chứ số: $563244$
• Ta xét các số có dạng $563abc$
  • $a$ có $2$ cách chọn $1$ số trong các số $0, 1$, $b$ có $10$ cách chọn $1$ số trong các số từ $0$ đến $9$, $c$ có $5$ cách chọn $1$ số trong các số $1, 3, 5, 7, 9$. Như vậy, số số cần xét là $2×10×5 = 100 = C$ số.
  • Các số $5, 6, 3$ ở chữ số hàng trăm nghìn, chục nghìn, nghìn mỗi số có $100$ lần xuất hiện.
  • Các số $0, 1, 2$ có số lần xuất hiện là $10×5 = 50 = C/2$ lần.
  • Các số $0, 1, ..., 9$ có số lần xuất hiện là $2×5 = 10 = C/10$ lần.
  • Các số $1, 3, 5, 7, 9$ có số lần xuất hiện là $2×10 = 20 = C/5$ lần.
• Trường hợp trên được áp dụng khi số ẩn trong số đang xét nhỏ hơn số chữ số của số đã cho và lớn hơn 1.
• Ta xét các số có dạng $abcdef$
  • $a$ có $4$ cách chọn $1$ số trong số các số từ $1$ đến $4$, không tính số $0$ bởi chữ số đầu tiên phải khác $0$. $b, c, d, e$ mỗi ẩn có $10$ cách chọn $1$ số trong số các số từ $0$ đến $9$. $f$ có $5$ cách chọn $1$ số trong các số $1, 3, 5, 7, 9$. Như vậy, số số cần xét là $4×10^4×5 = 200000$ số.
  • Xét ẩn $a$, các số từ $1$ đến $4$ có số lần xuất hiện là $10^4×5 = 50000 = C/4$ lần.
  • Xét các ẩn $b, c, d, e$, tổng hợp lại các số từ $0$ đến $9$ có số lần xuất hiện là $4×C/10$ lần.
  • Các số $1, 3, 5, 7, 9$ có số lần xuất hiện là $C/5$ lần.
• Ta xét các số có dạng $56324a$, các số thoả mãn là $563240$, $563242$, $563244$. Ta có thể đếm được dễ dàng số lần xuất hiện của các số.