Hướng dẫn giải của Tính tổng các chữ số
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: , , ,
Hiểu bài toán
Bài toán yêu cầu giải quyết hai việc với các số trong đoạn [A, B] (1 ≤ A ≤ B ≤ 10^15):
- Đếm số lượng số có tổng các chữ số bằng S (1 ≤ S ≤ 135).
- Tìm số nhỏ nhất trong đoạn [A, B] có tổng các chữ số bằng S. Dữ liệu đảm bảo luôn t tồn tại ít nhất một số hợp lệ.
Các cách tiếp cận
Cách Quy hoạch động dạng số (Digit DP) + Binary Search
#include <bits/stdc++.h>
using namespace std;
long long dp[20][165][2];
string num;
int target_sum;
// Hàm quy hoạch động đếm số số <= num có tổng chữ số bằng target_sum
long long f(int pos, int sum, bool tight) {
if (sum < 0) return 0;
if (pos == num.size()) return (sum == 0);
if (dp[pos][sum][tight] != -1) return dp[pos][sum][tight];
long long res = 0;
int limit = tight ? num[pos] - '0' : 9;
for (int digit = 0; digit <= limit; ++digit) {
res += f(pos + 1, sum - digit, tight && (digit == limit));
}
return dp[pos][sum][tight] = res;
}
// Đếm số số <= x có tổng chữ số bằng S
long long count_up_to(long long x, int s) {
if (x < 0) return 0;
num = to_string(x);
target_sum = s;
memset(dp, -1, sizeof(dp));
return f(0, s, true);
}
// Tìm số nhỏ nhất trong [A, B] có tổng chữ số bằng S
long long find_smallest(long long A, long long B, int S) {
long long lo = A, hi = B, ans = -1;
while (lo <= hi) {
long long mid = lo + (hi - lo) / 2;
// Nếu t tồn tại số <= mid trong [A, B] có tổng S (tức là count_up_to(mid, S) > count_up_to(A-1, S))
if (count_up_to(mid, S) > count_up_to(A - 1, S)) {
ans = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return ans;
}
int main() {
long long A, B;
int S;
if (cin >> A >> B >> S) {
// Câu 1: Đếm số lượng
long long cnt = count_up_to(B, S) - count_up_to(A - 1, S);
cout << cnt << "\n";
// Câu 2: Tìm số nhỏ nhất
cout << find_smallest(A, B, S) << "\n";
}
return 0;
}
- Time Complexity: O(log(B) * 20 * 135 * 2). Với B ~ 10^15, log(B) ~ 16. Thời gian chạy khoảng 10^5 phép tính, rất nhanh.
- Space Complexity: O(20 * 135 * 2) ~ O(5400) bytes, nhỏ hơn rất nhiều so với giới hạn memory.
Đây là cách tiếp cận chuẩn cho bài toán đếm số có đặc điểm dựa trên chữ số trong một đoạn.
Digit DP (Quy hoạch động dạng số):
- Biểu diễn số dưới dạng chuỗi để xử lý từng chữ số.
- Trạng thái DP:
dp[pos][sum][tight]là số cách điền các chữ số từ vị tríposđến hết sao cho tổng các chữ số còn lại làsum, với ràng buộctight(chặt chẽ hay không).pos: Vị trí chữ số đang xét (0 đến len-1).sum: Tổng các chữ số còn lại cần đạt được.tight: = 1 nếu các chữ số trước đó khớp hoàn toàn vớinum(ví dụ số 123 thì đang xét chữ số đầu là 1, nếu tight=1 thì chữ số tiếp theo không được vượt quá 2). Nếutight=0, ta có thể chọn tự do từ 0 đến 9.
- Hàm
count_up_to(x, s)tính số số <=xcó tổng chữ số bằngs.
Binary Search (Tìm kiếm nhị phân):
- Để tìm số nhỏ nhất trong [A, B], ta có thể dùng tìm kiếm nhị phân.
- Kiểm tra
mid: Nếu t tồn tại số <=mid(thuộc [A, B]) có tổngS, ta thử tìm số nhỏ hơn (dich sang trái). Ngược lại, phải tìm số lớn hơn. - Điều kiện kiểm tra:
count_up_to(mid, S) > count_up_to(A-1, S).
Ưu điểm: Giải quyết triệt để cả hai câu hỏi với độ phức tạplogarithmic.
Cách Tạo số thủ công (Constructive Algorithm)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
long long A, B;
int S;
// Hàm tạo số nhỏ nhất có tổng chữ số là sum và có ít nhất min_len chữ số
string construct_min(int sum, int min_len) {
string res = "";
// Nếu tổng lớn hơn 9*(min_len-1), ta phải dùng thêm chữ số
// Tính số lượng chữ số tối thiểu cần thiết
int needed_len = min_len;
while (needed_len * 9 < sum) needed_len++;
// Xây dựng số từ trái sang phải
int current_sum = sum;
for (int i = 0; i < needed_len; i++) {
int remaining_len = needed_len - i - 1;
// Chọn digit nhỏ nhất để lại t tổng khả thi cho phần còn lại
// Phần còn lại cần tối thiểu 0 (nếu là số 0 được phép ở đầu, nhưng số không được bắt đầu bằng 0)
// Nếu i==0, digit tối thiểu là 1. Nếu i > 0, digit tối thiểu là 0.
int min_digit = (i == 0) ? 1 : 0;
// Digit phải đủ lớn để phần còn lại có thể đạt được tổng current_sum - digit
// Phần còn lại tối đa là 9 * remaining_len
// Điều kiện: current_sum - digit <= 9 * remaining_len
// => digit >= current_sum - 9 * remaining_len
for (int d = min_digit; d <= 9; d++) {
if (current_sum - d <= 9 * remaining_len) {
res += (char)(d + '0');
current_sum -= d;
break;
}
}
}
return res;
}
// Kiểm tra xem số n có tổng chữ số bằng S không
int get_sum(long long n) {
int s = 0;
while (n > 0) {
s += n % 10;
n /= 10;
}
return s;
}
int main() {
cin >> A >> B >> S;
// Câu 1: Đếm số lượng (Dùng brute force nếu đoạn nhỏ, nhưng ở đây B-A có thể lớn.
// Tuy nhiên, giải pháp này tập trung vào câu 2 và tối ưu cho câu 1 nếu cần.
// Do bài này yêu cầu cả 2, Digit DP vẫn tốt hơn. Code này minh họa cho finding).
// Câu 2: Tìm số nhỏ nhất
// Ta cần tìm số X sao cho A <= X <= B và tổng X = S.
// Ta thử tạo số Y có tổng S sao cho Y >= A. Nếu Y <= B thì đó là đáp án.
// Cách 1: Tạo số nhỏ nhất >= A có tổng S.
long long ans = -1;
// Thử các độ dài số từ len(A) đến len(B)
string strA = to_string(A);
string strB = to_string(B);
int lenA = strA.length();
int lenB = strB.length();
// 1. Nếu tạo số có độ dài > lenA, số nhỏ nhất là tạo số có tổng S với độ dài đó (luôn >= A)
// 2. Nếu tạo số có độ dài == lenA, phải đảm bảo >= A
// Ưu tiên độ dài bằng lenA trước
// Duyệt các cấu hình chữ số từ phải sang trái hoặc dùng DFS/Backtracking
// Hàm tìm số nhỏ nhất >= lower_bound và <= upper_bound có tổng S
// khá phức tạp để code hoàn chỉnh trong ngắn gọn.
// Dưới đây là logic tìm số nhỏ nhất >= A có tổng S:
// Logic:
// Xét các độ dài từ len(A) đến len(B).
// Nếu độ dài > len(A): Số đó chắc chắn > A. Tạo số nhỏ nhất có tổng S và độ dài đó.
// Nếu độ dài == len(A): Tạo số >= A có tổng S.
// Quét từ trái sang phải, cố gắng giữ nguyên chữ số của A (để số nhỏ nhất).
// Nếu không thể (tổng quá lớn hoặc nhỏ), phải điều chỉnh.
// Code dưới đây chỉ giải quyết câu hỏi 2 một cách trực quan:
// Tạo số nhỏ nhất >= A có tổng S.
// DFS tìm số nhỏ nhất >= lower_bound
// Trạng thái: (pos, sum, tight)
string res = "-1";
// Chỉ giải quyết câu hỏi 2:
// Dùng DFS để tìm số nhỏ nhất >= A và <= B có tổng S
// Do code full cho constructive approach này khá dài, ta sẽ chỉ ghi concept:
// Dùng recursion thử các chữ số.
// Tuy nhiên, với dữ liệu lớn, Digit DP là lựa chọn tối ưu và an toàn nhất.
// Approach này thường dùng khi số lượng query lớn hoặc bài toán khác.
// Ví dụ đơn giản: Tạo số nhỏ nhất >= A có tổng S:
// 1. Tính tổng chữ số hiện tại của A (curSum).
// 2. Nếu curSum == S -> A là đáp án.
// 3. Nếu curSum < S: Ta cần cộng thêm (S - curSum). Cố gắng cộng vào các chữ số cuối.
// Ví dụ A=100, S=3 -> 102.
// 4. Nếu curSum > S: Khó hơn. Phải sửa các chữ số.
// Ví dụ A=199, S=10 -> 199 (sum=19) > 10. Phải sửa.
// Tăng A lên 200 (sum=2) -> 208 (sum=10).
// Kết luận: Digit DP là cách tốt nhất cho bài này.
// Approach này chỉ hiệu quả nếu bài toán yêu cầu tối ưu hóa thêm (vd: chỉ tìm số, không đếm).
// Hoặc dùng làm bước tiền xử lý.
return 0;
}
- Time Complexity: O(D * 10) ~ O(160) cho mỗi lần tạo số. Nếu chạy lặp (ví dụ tìm số đầu tiên), có thể lên tới O(10^15) nếu không có chiến lược tốt. Không khuyến khích brute force.
- Space Complexity: O(D) ~ O(16) để lưu chuỗi số.
Cách tiếp cận này (thường thấy trong các bài toán 'tìm số đẹp') tập trung vào việc tạo ra số trực tiếp thay vì đếm.
Tìm số nhỏ nhất >= A:
- Tính tổng chữ số của A.
- Nếu tổng < S: Ta chỉ cần cộng thêm (S - tổng) vào số A. Tuy nhiên, việc cộng có thể gây tràn số. Cụ thể, ta cộng vào các chữ số cuối cùng (phần số 0 ở cuối).
- Nếu tổng > S: Phải sửa đổi các chữ số. Thường là tăng số lên để tổng giảm, hoặc giảm số (nếu có thể).
- Phức tạp chính xác nằm ở việc xử lý "vượt số" (carry). Ví dụ A=199, S=10. A có tổng 19. Ta cần giảm 9. Không thể giảm 199 xuống 190 (tổng 10) vì 190 < 199.
- Giải pháp: Tăng số lên để reset các chữ số cuối, sau đó cộng thêm. Ví dụ 199 -> 200 (tổng 2). Cần thêm 8 -> 208.
Tìm số nhỏ nhất:
- Ta cần số X sao cho A <= X <= B và tổng X = S.
- Ta tìm số Y nhỏ nhất sao cho Y >= A và tổng Y = S.
- Nếu Y <= B thì Y là đáp án.
Đếm số lượng:
- Rất khó đếm bằng phương pháp này. Phải dùng quy hoạch động hoặc combinatorics.
Lưu ý: Code mẫu trong phần này là pseudocode/minh họa logic. Thực tế, bài toán này yêu cầu đếm số lượng, nên Digit DP là bắt buộc. Approach này chỉ có thể dùng để giải quyết câu hỏi 2 một cách riêng biệt nếu câu 1 không cần.
Cách Brute Force (Tìm kiếm tuần tự)
#include <iostream>
using namespace std;
// Chỉ dùng cho B-A nhỏ (ví dụ < 10^6)
// Bài này B-A có thể lên tới 10^15, code này sẽ chạy quá thời gian
int get_sum(long long n) {
int s = 0;
while (n > 0) {
s += n % 10;
n /= 10;
}
return s;
}
int main() {
long long A, B;
int S;
cin >> A >> B >> S;
long long count = 0;
long long first = -1;
// DANGER: Vòng lặp này chạy 10^15 lần, quá chậm
for (long long i = A; i <= B; i++) {
if (get_sum(i) == S) {
count++;
if (first == -1) first = i;
}
}
cout << count << endl;
cout << first << endl;
return 0;
}
- Time Complexity: O(B - A). Với B-A ~ 10^15, đây là số lớn không thể chấp nhận được.
- Space Complexity: O(1)
Đây là cách tiếp cận trực quan nhất: duyệt qua từng số trong đoạn [A, B], tính tổng chữ số và kiểm tra.
- Tại sao không dùng? Với giới hạn A, B lên đến 10^15, số lượng số cần kiểm tra quá lớn (có thể là 10^15 số). Mỗi phép chia cộng mất khoảng 20-30 chu kỳ, thời gian tính toán sẽ tính bằng hàng trăm năm hoặc hàng triệu năm, vượt quá giới hạn thời gian của bài toán (thường là 1-2 giây).
- Công dụng: Chỉ dùng để kiểm tra đáp án cho các test case nhỏ hoặc debug.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(log(B) * 20 * 135 * 2). Với B ~ 10^15, log(B) ~ 16. Thời gian chạy khoảng 10^5 phép tính, rất nhanh. | O(20 * 135 * 2) ~ O(5400) bytes, nhỏ hơn rất nhiều so với giới hạn memory. | Quy hoạch động dạng số (Digit DP) + Binary Search |
| 2 | O(D * 10) ~ O(160) cho mỗi lần tạo số. Nếu chạy lặp (ví dụ tìm số đầu tiên), có thể lên tới O(10^15) nếu không có chiến lược tốt. Không khuyến khích brute force. | O(D) ~ O(16) để lưu chuỗi số. | Tạo số thủ công (Constructive Algorithm) |
| 3 | O(B - A). Với B-A ~ 10^15, đây là số lớn không thể chấp nhận được. | O(1) | Brute Force (Tìm kiếm tuần tự) |
Bài học kinh nghiệm
- Bài toán thuộc dạng 'Digit DP' (Quy hoạch động trên các chữ số), rất phổ biến trong Competitive Programming khi xử lý các số lớn có ràng buộc về tổng/hiệu/số lượng chữ số.
- Quy hoạch động có 3 tham số chính: Vị trí đang xét (index), Tổng hiện tại/còn lại (Sum), và Ràng buộc (Tight - số trước đó có khớp với số gốc không).
- Câu hỏi 2 (Tìm số nhỏ nhất) có thể được suy biến thành bài toán tìm kiếm nhị phân trên giá trị số, sử dụng hàm đếm (Count function) từ Digit DP làm hàm kiểm tra (Check function).
Lỗi thường gặp
- Quên xử lý số 0 ở đầu (ví dụ số 05 thường không được tính là số 5 có 2 chữ số). Biased: Digit DP thường xử lý số 0 bằng cách xét riêng hoặc thêm tham số 'isZero'. Tuy nhiên, với bài này A >= 1 nên số 0 không ảnh hưởng.
- Sử dụng mảng DP không reset đúng cách giữa các lần gọi hàm (ví dụ: khi thay đổi giá trị S hoặc thay đổi số Bound).
Trong solutions, ta thấy
memset(dp, -1, ...)được gọi trước mỗi lần tínhcount_up_to. - Lỗi tràn số khi tính tổng hoặc dùng Binary Search (mid = (low + high) / 2).
Với số lớn 10^15, dùng
inthoặclong(trên một số hệ thống) gây overflow. Phải dùnglong longhoặcint64_t. - Lỗi Logic trong Binary Search: So sánh
count(mid) > count(A-1)thay vì chỉ checkcount(mid) > 0. Phải trừ đi số lượng số < A để đảm bảo số tìm thấy nằm trong [A, B].
Bình luận