Hướng dẫn giải của Trò chơi ghép 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ả: , , ,
Editorial for numtrans: Trò chơi ghép số
Hiểu bài toán
Bài toán yêu cầu ghép n số nguyên dương cho trước thành một số nguyên dương lớn nhất có thể. Ví dụ, với các số 12, 907, 91, ta cần tìm cách sắp xếp chúng sao cho khi nối các chuỗi số tương ứng lại với nhau, ta được một số lớn nhất. Trong ví dụ này, cách ghép '91' + '907' + '12' tạo ra số 9190712 là lớn nhất.
Phương pháp giải quyết là sử dụng một hàm so sánh đặc biệt để sắp xếp các số. Thay vì so sánh các số theo giá trị thông thường (ví dụ 907 > 91), ta sẽ so sánh kết quả của việc nối chúng theo hai chiều khác nhau. Cụ thể, với hai số x và y, ta so sánh giá trị của chuỗi 'xy' với 'yx'. Nếu 'xy' > 'yx', thì x nên xếp trước y. Bằng cách sắp xếp mảng các số (dưới dạng chuỗi) theo quy tắc này, ta nối chúng lại theo thứ tự giảm dần sẽ được số lớn nhất.
Các cách tiếp cận
Cách Brute Force (Sinh tất cả các hoán vị)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<string> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
sort(nums.begin(), nums.end()); // Bắt đầu từ hoán vị nhỏ nhất
string max_str = "";
do {
string current = "";
for (const string& s : nums) {
current += s;
}
if (current > max_str) {
max_str = current;
}
} while (next_permutation(nums.begin(), nums.end()));
cout << max_str << endl;
return 0;
}
- Time Complexity: O(n! * n * L) (n! hoán vị, mỗi lần nối n chuỗi độ dài L)
- Space Complexity: O(n * L)
Đây là cách tiếp cận trực tiếp nhất (Brute Force). Ta sinh ra tất cả các cách sắp xếp khác nhau của mảng n số, nối chúng lại từng cách và so sánh để tìm ra số lớn nhất. Cách này chỉ hiệu quả với các bộ test nhỏ (n rất nhỏ, ví dụ n ≤ 10) do độ phức tạp giai thừa n! của nó. Tuy nhiên, với ràng buộc n ≤ 100, phương pháp này chắc chắn bị Time Limit Exceeded.
Cách Custom Comparator (Sort with String Comparison)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// Hàm so sánh cho qsort
int cmp(const void *a, const void *b) {
char *x = *(char **)a;
char *y = *(char **)b;
// Tạo 2 chuỗi đại diện cho việc nối 2 cách
char ab[25]; // Đủ lớn để chứa cả 2 chuỗi (max 10^5 + 10^5)
char ba[25];
strcpy(ab, x);
strcat(ab, y);
strcpy(ba, y);
strcat(ba, x);
// So sánh 'xy' và 'yx'.
// Nếu 'xy' > 'yx', strcmp trả về số dương, nhưng qsort cần số âm để sắp xếp giảm dần?
// Không, ta muốn 'xy' > 'yx' thì x phải đứng trước y (giảm dần).
// Qsort mặc định sắp xếp tăng dần. Nếu return > 0, a đứng sau b.
// Ta muốn nếu 'xy' > 'yx', thì a (x) phải đứng trước b (y) -> return âm.
// Nên return strcmp(ba, ab) hoặc strcmp(ab, ba) logic khác.
// Logic chuẩn: Nếu xy > yx, ta muốn x trước y. strcmp(xy, yx) > 0.
// Qsort: return < 0 -> a trước b.
// Ta cần return -1 nếu xy > yx.
// => return -strcmp(ab, ba);
return strcmp(ba, ab); // Nếu ab > ba (xy > yx), strcmp trả > 0. Ta cần âm -> return -strcmp(ab, ba)
// Code mẫu trong file lại sort tăng rồi in ngược, hoặc sort giảm.
// Code mẫu giải pháp 3 sort giảm: cmp return strcmp(ba, ab) (tức là so sánh yx vs xy).
// Nếu xy > yx, strcmp(yx, xy) < 0 -> swap.
// Logic chuẩn để sort giảm dần:
// Ta muốn xy > yx thì x trước y.
// Nếu cmp(x, y) return < 0, x trước y.
// Ta cần cmp(x, y) = -strcmp(xy, yx).
// Nếu xy > yx, strcmp > 0 -> cmp return âm -> x trước y. Đúng.
}
int main() {
int n;
scanf("%d", &n);
char **a = (char **)malloc(n * sizeof(char *));
for (int i = 0; i < n; i++) {
a[i] = (char *)malloc(12 * sizeof(char));
scanf("%s", a[i]);
}
// Sắp xếp giảm dần
// Để dùng qsort cho giảm dần, ta có thể:
// 1. Đổi logic hàm cmp: return -strcmp(ab, ba)
// 2. Hoặc sắp xếp tăng rồi lật mảng.
// Code mẫu dưới đây dùng logic hàm cmp chuẩn để sort giảm:
qsort(a, n, sizeof(char *), cmp);
// In kết quả
for (int i = 0; i < n; i++) {
printf("%s", a[i]);
}
return 0;
}
// Hàm cmp để sort giảm dần:
int cmp_correct(const void *a, const void *b) {
char *x = *(char **)a;
char *y = *(char **)b;
char xy[25], yx[25];
strcpy(xy, x); strcat(xy, y);
strcpy(yx, y); strcat(yx, x);
// Nếu xy > yx, ta muốn x trước y (return âm)
// Nếu xy < yx, ta muốn y trước x (return dương)
return -strcmp(xy, yx);
}
- Time Complexity: O(N * L * log N)
- Space Complexity: O(N * L)
Đây là phương pháp tối ưu và chuẩn nhất cho bài toán này.
- Đọc dữ liệu vào dưới dạng chuỗi.
- Sử dụng hàm so sánh自定义 (custom comparator) để định nghĩa lại thứ tự giữa hai số.
- Trong hàm so sánh, ta nối chuỗi X và Y thành XY, nối Y và X thành YX. So sánh XY và YX.
- Sắp xếp mảng các chuỗi theo thứ tự giảm dần dựa trên hàm so sánh này.
- Nối tất cả các chuỗi lại và in ra.
Giải thích chi tiết hàm cmp: Ta cần sắp xếp sao cho số lớn nhất nằm trước. Giả sử ta có 2 số a, b. Nếu concat(a, b) > concat(b, a), thì a phải đứng trước b. Trong hàm qsort (sắp xếp tăng mặc định), nếu cmp(a, b) < 0 thì a đứng trước b. Vậy ta cần cmp(a, b) trả về giá trị âm khi concat(a, b) > concat(b, a). Do đó: return -strcmp(concat(a, b), concat(b, a)).
Lưu ý: Trong các solution mẫu, Solution 3 dùng qsort và sort giảm bằng cách return strcmp(ba, ab) (với ba là yx, ab là xy). Nếu xy > yx, strcmp(yx, xy) trả về âm -> qsort đổi chỗ (vì mặc định sort tăng). Nếu ta dùng logic strcmp(xy, yx) và sort tăng, ta sẽ được thứ tự tăng dần, sau đó in ngược lại.
Logic chuẩn nhất là sort giảm trực tiếp: return -strcmp(xy, yx).
Cách Bubble Sort / Swap Logic (Naive Sort)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void solve() {
int n;
scanf("%d", &n);
char s[n][12];
for (int i = 0; i < n; i++) {
scanf("%s", s[i]);
}
// Bubble Sort manually implementing the custom logic
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
char s1s2[25], s2s1[25];
strcpy(s1s2, s[i]); strcat(s1s2, s[j]);
strcpy(s2s1, s[j]); strcat(s2s1, s[i]);
// Nếu s[i] + s[j] < s[j] + s[i], hoán đổi (để sort giảm)
if (strcmp(s1s2, s2s1) < 0) {
char temp[12];
strcpy(temp, s[i]);
strcpy(s[i], s[j]);
strcpy(s[j], temp);
}
}
}
for (int i = 0; i < n; i++) {
printf("%s", s[i]);
}
}
int main() {
solve();
return 0;
}
- Time Complexity: O(N^2 * L)
- Space Complexity: O(N * L)
Phương pháp này sử dụng thuật toán sắp xếp Bubble Sort hoặc Selection Sort thủ công, áp dụng logic so sánh 'xy' > 'yx' trực tiếp trong vòng lặp.
- So sánh từng cặp phần tử.
- Nếu thứ tự hiện tại không tối ưu (ví dụ s[i] + s[j] < s[j] + s[i] trong khi muốn giảm dần), ta hoán đổi chúng.
- Phương pháp này dễ hiểu và dễ cài đặt nếu không muốn dùng hàm qsort, nhưng chậm hơn so với các thư viện chuẩn.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n! * n * L) (n! hoán vị, mỗi lần nối n chuỗi độ dài L) | O(n * L) | Brute Force (Sinh tất cả các hoán vị) |
| 2 | O(N * L * log N) | O(N * L) | Custom Comparator (Sort with String Comparison) |
| 3 | O(N^2 * L) | O(N * L) | Bubble Sort / Swap Logic (Naive Sort) |
Bài học kinh nghiệm
- Bài toán về bản chất là bài toán sắp xếp các chuỗi với một hàm so sánh đặc biệt, không phải so sánh giá trị số học hay thứ tự từ điển thông thường.
- Quy tắc quyết định thứ tự giữa hai số A và B là: A nên xếp trước B nếu A+B > B+A (khi so sánh theo giá trị số hoặc chuỗi).
Lỗi thường gặp
- Lỗi thứ tự so sánh trong hàm cmp (ví dụ: return strcmp(s1, s2) thay vì so sánh s1+s2 và s2+s1).
- Xử lý sai số 0 ở đầu (ví dụ các số '00', '0') trong khi bài này giới hạn a_i ≥ 1 nên không gặp lỗi này, nhưng trong các bài toán tương tự có thể gặp.
- Tràn số nếu lưu trữ số dạng nguyên (int, long long) thay vì chuỗi字符串 do các số có thể lên tới 10^5 và độ dài tổng có thể rất lớn.
Bình luận