Hướng dẫn giải của Xếp số bằng que diêm 1
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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ập
Tác giả: Hiếu Nguyễn
, , ,
Editorial for xepso1: Xếp số bằng que diêm 1
Hiểu bài toán
Cho n que diêm, cần tìm số tự nhiên nhỏ nhất và lớn nhất có thể tạo được bằng cách sử dụng đúng n que diêm để vẽ các chữ số (theo quy tắc số que diêm cho mỗi chữ số từ 0 đến 9). Số được tạo ra không được phép có chữ số 0 ở đầu (trừ trường hợp số 0). Tuy nhiên, theo các ví dụ và ràng buộc, số 0 không bao giờ là câu trả lời (n >= 2). Ta cần tối ưu hóa cả số chữ số (số lượng chữ số nhiều thì số lớn nhất) và giá trị các chữ số (số lớn nhất ưu tiên chữ số 8, nhỏ nhất ưu tiên chữ số 1).
Các cách tiếp cận
Cách Quy hoạch động (Dynamic Programming) - Dùng cho số nhỏ nhất
#include <stdio.h>
#include <string.h>
int cost[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
char dp[40][100]; // dp[n] lưu số nhỏ nhất tạo từ n que
// Hàm so sánh 2 chuỗi số xem số nào nhỏ hơn
int is_smaller(const char* a, const char* b) {
if (strlen(a) != strlen(b)) return strlen(a) < strlen(b);
return strcmp(a, b) < 0;
}
void solve() {
// Khởi tạo dp rỗng
for (int i = 0; i < 40; i++) dp[i][0] = '\0';
// Base case: các số 0-9
// Lưu ý: dp[0] không dùng, hoặc coi như không hợp lệ nếu không có que
for (int n = 1; n <= 39; n++) {
char best[100] = "";
for (int d = 0; d <= 9; d++) {
int q = cost[d];
if (n < q) continue;
if (d == 0 && n == q) continue; // Không cho số 0 đơn độc
if (d == 0 && dp[n-q][0] == '\0') continue; // Phải nối được vào số có sẵn
char temp[100];
if (n == q) {
sprintf(temp, "%d", d);
} else {
if (dp[n-q][0] == '\0') continue;
sprintf(temp, "%d%s", d, dp[n-q]);
}
if (best[0] == '\0' || is_smaller(temp, best)) {
strcpy(best, temp);
}
}
if (best[0] != '\0') strcpy(dp[n], best);
}
// In kết quả cho các test case
int T; scanf("%d", &T);
while(T--) {
int n; scanf("%d", &n);
printf("%s ", dp[n]);
// Logic in số lớn nhất (đơn giản hơn)
}
}
- Time Complexity: O(n^2 * L) (với L là độ dài chuỗi, nhỏ)
- Space Complexity: O(n * L)
Sử dụng quy hoạch động để tìm số nhỏ nhất. dp[n] là chuỗi số nhỏ nhất dùng n que. Để tính dp[n], ta thử tất cả các chữ số d có thể là chữ số đầu tiên. Nếu chọn d, ta cần nối chuỗi dp[n - cost[d]] vào sau. So sánh tất cả để tìm chuỗi nhỏ nhất. Điều kiện dừng: n nhỏ hơn chi phí của bất kỳ chữ số nào hoặc dp[n] được tạo thành từ duy nhất chữ số 0 (bị cấm).
Cách Xây dựng tham lam (Greedy Construction)
#include <stdio.h>
#include <string.h>
// cost: 0-6, 1-2, 2-5, 3-5, 4-4, 5-5, 6-6, 7-3, 8-7, 9-6
void solve_min_max(int n) {
// --- TÌM SỐ LỚN NHẤT ---
// Chiến lược: Số lượng chữ số nhiều nhất (dùng que ít nhất -> chữ số 1, chi phí 2).
// Nếu chẵn: toàn 1. Nếu lẻ: thay 1 chữ số 1 bằng chữ số 7 (chi phí 3).
// VD: n=5 (lẻ) -> 11111 (10 que) sai. n=5 -> 11111 tốn 10 que.
// Thực tế: Số lớn nhất ưu tiên chữ số 8 (chi phí 7) nếu có đủ que.
// Nhưng để số lớn nhất, ta cần nhiều chữ số nhất, nên dùng chữ số 1 (chi phí 2).
// Nếu n lẻ, ta phải dùng ít nhất 1 chữ số chi phí lẻ (như 7 chi phí 3) để tổng chẵn.
char max_res[50] = "";
int rem = n;
if (rem % 2 != 0) {
strcat(max_res, "7");
rem -= 3;
}
while (rem >= 2) {
strcat(max_res, "1");
rem -= 2;
}
printf("%s ", max_res);
// --- TÌM SỐ NHỎ NHẤT ---
// Số nhỏ nhất: Ít chữ số nhất (vì 100..0 > 99..9).
// Chữ số càng lớn càng tốt (8 tốn 7 que).
// Ta cần tìm số chữ số k sao cho k*7 >= n (vì tối đa 7 que/chữ số).
// Số chữ số tối thiểu k = ceil(n/7).
// Sau đó ta cần phân bổ que vào các chữ số sao cho tổng = n.
// Chữ số đầu không được là 0 (chi phí 6).
// Ta chia n thành k phần, mỗi phần từ 2 đến 7 (vì 1 tốn 2 que, nhưng để tạo số nhỏ nhất).
// Thực ra: Ta dùng DP hoặc cẩn thận hơn.
// Đơn giản: Dùng mảng k phần, khởi tạo tất cả là 1 (tốn 2k que).
// Chừa lại que (n - 2k) để tăng giá trị các chữ số.
// Tăng từ trái sang phải (để chữ số đầu tăng nhiều nhất).
int min_res[50];
int k = (n + 6) / 7; // Số chữ số tối thiểu
if (n < 2) k = 1; // Base case
// Khởi tạo tất cả là 1
for (int i = 0; i < k; i++) min_res[i] = 1;
int current_cost = 2 * k;
int extra = n - current_cost;
for (int i = 0; i < k; i++) {
int max_inc = 7 - min_res[i]; // 1 -> 8 (tăng 6) hoặc 1->9 (tăng 5) ...
// Cost của digit 1 là 2, 8 là 7 (tăng 5 que).
// Digit 9 cost 6 (tăng 4 que).
// Để số nhỏ nhất, ta muốn digit lớn nhất có thể.
// Tăng digit 1 lên 8 tốn thêm 5 que (7-2).
// Tăng digit 1 lên 9 tốn thêm 4 que (6-2).
// Tăng digit 1 lên 7 tốn thêm 1 que (3-2).
// Ta ưu tiên tăng lớn nhất (8).
int add = extra;
if (i == 0) {
// Chữ số đầu không được là 0.
// Có thể tăng lên 9 (thêm 4), 8 (thêm 5), 7 (thêm 1).
// Nếu extra >= 5, tăng lên 8.
// Nếu extra >= 4, tăng lên 9.
// Nếu extra >= 1, tăng lên 7.
// Ưu tiên 8 > 9 > 7.
if (extra >= 5) { min_res[i] = 8; extra -= 5; }
else if (extra >= 4) { min_res[i] = 9; extra -= 4; }
else if (extra >= 1) { min_res[i] = 7; extra -= 1; }
} else {
// Các chữ số sau có thể là 0.
// 0 cost 6. Từ 1 (cost 2) lên 0 (cost 6) tốn thêm 4.
// Ưu tiên 0 (để số nhỏ nhất).
// Nếu extra >= 4, tăng lên 0.
// Sau đó mới tới 8, 9, 7.
if (extra >= 4) { min_res[i] = 0; extra -= 4; }
else if (extra >= 5) { min_res[i] = 8; extra -= 5; }
else if (extra >= 4) { min_res[i] = 9; extra -= 4; }
else if (extra >= 1) { min_res[i] = 7; extra -= 1; }
}
}
for (int i = 0; i < k; i++) printf("%d", min_res[i]);
printf("\n");
}
- Time Complexity: O(n)
- Space Complexity: O(1)
Đây là cách tiếp cận tham lam tối ưu.
- Số lớn nhất: Muốn nhiều chữ số nhất nên dùng chữ số 1 (chi phí 2). Nếu n lẻ, dùng 1 chữ số 7 (chi phí 3) để bù lại.
- Số nhỏ nhất: Muốn ít chữ số nhất nên dùng chữ số 8 (chi phí 7). Số lượng chữ số k = ceil(n/7). Sau đó phân bổ que còn lại để tăng giá trị các chữ số, ưu tiên chữ số đầu tiên để tạo số lớn nhất về mặt giá trị (vì số ít chữ số hơn luôn nhỏ hơn). Cụ thể: Khởi tạo k chữ số đều là 1. Que thừa dùng để tăng giá trị. Ưu tiên tăng chữ số đầu lên 8 (nếu đủ que), tiếp theo là 9, sau đó là 0 (ở các chữ số sau) vì 0 giúp số nhỏ đi rất nhiều.
Cách Tối ưu hóa Tham lam (Công thức chi tiết)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int cost[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
string find_min(int n) {
// Số nhỏ nhất: Ít chữ số nhất, chữ số đầu lớn nhất
// Số chữ số k = ceil(n / 7.0)
// Nếu n < 2? n >= 2 theo đề.
int k = (n + 6) / 7;
if (k == 0) return "";
string res = "";
int rem = n;
// Xác định chữ số đầu tiên
// Cần thỏa mãn: rem - cost[d] >= 2*(k-1) (các chữ số sau tối thiểu là 1, tốn 2 que)
// và rem - cost[d] <= 7*(k-1)
for (int d = 9; d >= 0; d--) {
if (d == 0) continue; // Chữ số đầu không được 0
int q = cost[d];
if (rem < q) continue;
int remaining_after = rem - q;
if (remaining_after >= 2 * (k - 1) && remaining_after <= 7 * (k - 1)) {
res += (char)(d + '0');
rem -= q;
k--;
break;
}
}
// Xác định các chữ số còn lại
while (k > 0) {
// Ưu tiên 0 vì chi phí 6, chỉ tốn nhiều hơn 1 (cost 2) 4 que,
// nhưng 0 là số nhỏ nhất.
// Tuy nhiên, 0 chỉ hợp lệ nếu rem - 6 >= 2*(k-1)
// Thử từ 0 -> 9
for (int d = 0; d <= 9; d++) {
int q = cost[d];
if (rem < q) continue;
int remaining_after = rem - q;
if (remaining_after >= 2 * (k - 1) && remaining_after <= 7 * (k - 1)) {
res += (char)(d + '0');
rem -= q;
k--;
break;
}
}
}
return res;
}
string find_max(int n) {
// Số lớn nhất: Nhiều chữ số nhất, chữ số lớn nhất
// Ưu tiên 1 (cost 2). Nếu lẻ, dùng 7 (cost 3).
if (n % 2 != 0) {
return "7" + string((n - 3) / 2, '1');
} else {
return string(n / 2, '1');
}
}
int main() {
int T; cin >> T;
while (T--) {
int n; cin >> n;
cout << find_min(n) << " " << find_max(n) << endl;
}
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(1)
Phiên bản tham lam trực tiếp. Số lớn nhất: Dễ dàng nhận thấy số 1 (2 que) là tối ưu nhất để có nhiều chữ số. Nếu n chẵn, toàn 1. Nếu n lẻ, thay 1 chữ số 1 bằng 7 (tốn 3 que) để tổng que chẵn. Số nhỏ nhất: Ta biết số chữ số tối thiểu k = ceil(n/7). Ta xây dựng số từ trái sang phải. Với mỗi vị trí, ta thử các chữ số từ lớn đến bé (9 về 0) để tìm chữ số lớn nhất có thể dùng sao cho các chữ số còn lại vẫn có thể tạo được (tức là số que còn lại >= 2(số chữ số còn lại) và <= 7(số chữ số còn lại)).
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n^2 * L) (với L là độ dài chuỗi, nhỏ) | O(n * L) | Quy hoạch động (Dynamic Programming) - Dùng cho số nhỏ nhất |
| 2 | O(n) | O(1) | Xây dựng tham lam (Greedy Construction) |
| 3 | O(n) | O(1) | Tối ưu hóa Tham lam (Công thức chi tiết) |
Bài học kinh nghiệm
- Chi phí que diêm (Cost): 0(6), 1(2), 2(5), 3(5), 4(4), 5(5), 6(6), 7(3), 8(7), 9(6).
- Số lớn nhất: Cố gắng tạo ra nhiều chữ số nhất. Chữ số 1 (2 que) là tiết kiệm nhất.
- Số nhỏ nhất: Cố gắng tạo ra ít chữ số nhất. Chữ số 8 (7 que) là "đắt" nhất, do đó ít que nhất cho một chữ số.
- Số nhỏ nhất (phân tích sâu): Với số chữ số k cố định, ta cần phân bổ que để tạo ra số có giá trị nhỏ nhất. Điều này có nghĩa là chữ số đầu tiên nên lớn nhất có thể (vì nó có trọng số cao nhất), các chữ số sau nên ưu tiên số 0 (nếu chi phí cho phép) vì 0 là số nhỏ nhất.
Lỗi thường gặp
- Bỏ qua ràng buộc 'không bắt đầu bằng 0'. Khi tính số nhỏ nhất, nếu chữ số đầu tiên là 0 thì số đó không hợp lệ.
- Xử lý sai số lẻ/trường hợp đặc biệt cho số lớn nhất (ví dụ: n=3 -> 7, n=5 -> 71).
- Lầm tưởng rằng số lớn nhất chỉ là lặp lại '8'. Ví dụ n=5: 8 tốn 7 que, không đủ.
- Quy hoạch động có thể tràn bộ nhớ hoặc quá chậm nếu không tối ưu chuỗi ký tự (vì độ dài số có thể lớn).
Bình luận