Trò Chơi Ghép Số (NUMTRANS)
Đề bài
NUMTRANS – Trò chơi ghép số
Tèo và Tí chơi thân với nhau, biết Tí học rất giỏi môn Toán nên một hôm Tèo đố Tí bài toán:
Cho $n$ số nguyên dương $a_1, a_2, \ldots, a_n$. Hãy ghép các số đó lại với nhau để được số nguyên dương lớn nhất.
Ví dụ: Với $3$ số $12$, $907$, $91$ ta có $6$ cách ghép được $6$ số là: $1290791$, $1291907$, $9071291$, $9079112$, $9112907$, $9190712$. Trong đó số lớn nhất là $9190712$.
Tất nhiên là bài toán này không thể làm khó Tí được nhưng vì còn bận học bài nên Tí muốn nhờ các bạn viết chương trình giải quyết bài toán trên.
Dữ liệu vào:
- Dòng đầu chứa số nguyên dương $n$;
- Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \ldots, a_n$. Hai số liên tiếp cách nhau một dấu cách.
Giới hạn: $1 \le n \le 10^5$; $1 \le a_i \le 10^5$.
Dữ liệu ra:
- Ghi ra số nguyên dương lớn nhất ghép được.
3
12 907 919190712Lời mở đầu
Các bạn luôn phải nhớ rằng mấy dạng bài kiểu này lúc nào cũng "không muốn" ta nhìn ra hướng giải quyết thực sự của nó, mà cố tình đánh lạc hướng chúng ta khỏi hướng làm tốt nhất. Thậm chí cả test ví dụ cũng cố tình đưa ra những trường hợp làm chúng ta lầm tưởng đi xử lý theo một hướng khác, nên các bạn phải tỉnh táo nhìn kỹ bản chất vấn đề nhé ☺️.
Với bài này, đề cố tình "lái" chúng ta liệt kê hết 6 cách ghép của 3 số – tức là đi theo hướng vét cạn hoán vị. Trong bài viết này mình sẽ đi từ hướng đó (để thấy vì sao không ổn), rồi tới nhận xét mấu chốt và lời giải tối ưu.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJMình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Ta có 3 số 12 907 91, ta được quyền xếp chúng theo thứ tự bất kỳ rồi viết liền nhau (không được tách hay đảo chữ số bên trong mỗi số). 3 số thì có $3! = 6$ thứ tự:
| Thứ tự ghép | Số tạo thành |
|---|---|
| 12 · 907 · 91 | 1290791 |
| 12 · 91 · 907 | 1291907 |
| 907 · 12 · 91 | 9071291 |
| 907 · 91 · 12 | 9079112 |
| 91 · 12 · 907 | 9112907 |
| 91 · 907 · 12 | 9190712 ← lớn nhất |
Để ý: $907$ là số lớn nhất nhưng lại không đứng đầu! Vì $91\ldots$ bắt đầu bằng "91" còn $907\ldots$ bắt đầu bằng "90", nên đặt $91$ lên trước sẽ được số lớn hơn. Đây chính là cái bẫy của bài.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Vét cạn tất cả hoán vị – O(N!·N)
Làm đúng theo những gì đề "gợi ý": thử hết tất cả các thứ tự ghép, với mỗi thứ tự thì nối các số lại thành một xâu, rồi giữ lại xâu lớn nhất. Với $N$ số ta có $N!$ hoán vị.
Nhưng phép tính giai thừa tăng khủng khiếp:
| N | 10 | 12 | 13 | 100 | $10^5$ |
|---|---|---|---|---|---|
| N! | 3 628 800 | 479 001 600 | ≈ 6,2 tỷ | 158 chữ số | không tưởng |
Giới hạn 1 giây tương ứng cỡ $(3 \text{ đến } 5) \cdot 10^7$, tối đa $10^8$ phép tính. Cỡ $12!$ thì may ra còn xoay xở, còn $13!$ là hơn 6 tỷ – vượt giới hạn rồi, nói chi $N$ tới $10^5$. Giả sử đề có cho 50% test với $N \le 10$ thì cách này vớt vát được 50% điểm, còn muốn 100% thì chắc chắn không thể chọn cách này.
next_permutation của STL cho gọn, chỉ để các bạn thấy ý tưởng và so sánh.Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<string> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i];
}
sort(a.begin(), a.end());
string best = "";
do{
string s = "";
for(int i = 0; i < n; ++i){
s += a[i];
}
if(s > best){
best = s;
}
}while(next_permutation(a.begin(), a.end()));
cout << best;
return 0;
}from itertools import permutations
n = int(input())
a = input().split()
best = ""
for p in permutations(a):
s = "".join(p)
if s > best:
best = s
print(best)Lưu ý next_permutation chỉ duyệt đủ mọi hoán vị nếu ta bắt đầu từ thứ tự tăng dần, nên phải sort trước. Các bạn xem nó chạy qua đủ 6 hoán vị của ví dụ đề trong khung dưới đây:
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N \cdot L)$ để lưu các xâu, với $L \le 6$ là số chữ số tối đa của một số.
- Thời gian: $N!$ hoán vị, mỗi hoán vị ghép mất $O(N \cdot L)$ ⇒ $O(N! \cdot N \cdot L)$. Chỉ dùng được khi $N$ cỡ 8–10.
Cách 2Tìm ra quy tắc so sánh + Interchange Sort – O(N²)
Hãy thử suy nghĩ: nếu các giá trị $a_i$ không nằm trong đoạn $1 \to 10^5$ mà chỉ nằm trong đoạn $1 \to 9$, tức là chỉ có 1 chữ số, thì bài này có phải rất đơn giản không? Chỉ việc sắp xếp mảng giảm dần. Ví dụ mảng $\{5, 3, 1, 9, 8, 5, 3\}$ sắp giảm dần thành $\{9, 8, 5, 5, 3, 3, 1\}$ và đáp án là $9855331$.
Nhưng nếu áp dụng y chang quy tắc đó cho ví dụ $\{12, 907, 91\}$ thì ta được $\{907, 91, 12\}$ → $9079112$, trong khi đáp án đúng là thứ tự $\{91, 907, 12\}$. Nghĩa là trong bài này, "91 lớn hơn 907", rồi "907 lớn hơn 12". Vậy ta phải nhìn ra được quy tắc tụi nó so sánh với nhau để biết thằng nào đứng trước, thằng nào đứng sau. Nhìn ra đúng quy tắc này là mấu chốt của cả bài.
Quy tắc thực ra làm đúng theo luật của bài thôi: có 2 số $a$, $b$ cần so sánh (hiện tại $a$ đứng trước $b$), ta thử cả hai cách ghép ab và ba:
- Nếu ab ≥ ba thì $a$ đứng trước $b$ là đúng rồi, không cần đổi chỗ.
- Nếu ba > ab thì phải đổi chỗ, cho $b$ ra trước $a$.
Thử áp dụng quy tắc này với thuật toán Interchange Sort (2 vòng lặp lồng nhau mà các bạn hay làm hồi học nhập môn lập trình) cho mảng $\{12, 907, 91\}$:
- So sánh $a[0] = 12$ với $a[1] = 907$: hai số ghép được là $12907$ và $90712$. Thấy $90712$ lớn hơn nên đổi chỗ → $\{907, 12, 91\}$.
- So sánh $a[0] = 907$ với $a[2] = 91$: $90791$ và $91907$. Thấy $91907$ lớn hơn nên đổi chỗ → $\{91, 12, 907\}$.
- So sánh $a[1] = 12$ với $a[2] = 907$: $12907$ và $90712$. Thấy $90712$ lớn hơn nên đổi chỗ → $\{91, 907, 12\}$.
Hết cặp để so sánh. Kết luận số lớn nhất là $9190712$. Đơn giản chưa nè 😁
Minh hoạ Interchange Sort với quy tắc ghép thử
Em nhập dãy số rồi bấm Tiếp để xem từng cặp $(i, j)$ được ghép thử và đổi chỗ thế nào:
Ở đây có một chỗ cần chọn: lưu các số dưới dạng số nguyên hay xâu?
- Nếu dùng số nguyên: muốn ghép $123$ với $45$ thành $12345$ thì phải tính $123 \cdot 10^2 + 45$, còn $45123 = 45 \cdot 10^3 + 123$ – tức là số này nhân với $10^{\text{(số chữ số của số kia)}}$ rồi cộng số kia. Phải viết thêm hàm đếm chữ số, và mỗi số tới $10^5$ (6 chữ số) nên ghép lại có thể tới 12 chữ số ⇒ phải dùng
long long, ép kiểu cẩn thận kẻo các phép nhân trung gian kiểuintbị tràn. - Nếu dùng xâu thì gọn hơn rất nhiều:
string a = "123", b = "45";thìa + b = "12345",b + a = "45123". Hai xâu ghép này cùng độ dài, nên so sánh xâu (từng ký tự từ trái qua phải, chỗ nào khác nhau thì ký tự lớn hơn thắng) cũng chính là so sánh hai số. Và C++ đã hỗ trợ sẵn các toán tử>,<,>=,<=,==,!=chostring.
a + b và b + a luôn có cùng độ dài, và không số nào có chữ số 0 ở đầu (do $a_i \ge 1$). Với hai xâu chữ số cùng độ dài, thứ tự từ điển trùng với thứ tự giá trị. Nhớ là chỉ so sánh được kiểu này khi cùng độ dài nhé: "9" > "100000" theo xâu nhưng $9 \lt 100000$ theo số!Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
string a[MAX];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; ++i){
cin >> a[i];
}
for(int i = 0; i < n - 1; ++i){
for(int j = i + 1; j < n; ++j){
if(a[j] + a[i] > a[i] + a[j]){
swap(a[i], a[j]);
}
}
}
for(int i = 0; i < n; ++i){
cout << a[i];
}
return 0;
}n = int(input())
a = input().split()
for i in range(n - 1):
for j in range(i + 1, n):
if a[j] + a[i] > a[i] + a[j]:
a[i], a[j] = a[j], a[i]
print("".join(a))Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N \cdot L)$ cho mảng xâu ($L \le 6$).
- Thời gian: 2 vòng lặp lồng nhau ⇒ $\dfrac{N(N-1)}{2}$ lần so sánh, mỗi lần ghép xâu tốn $O(L)$ ⇒ $O(N^2 \cdot L)$.
Cách 3Quy tắc ghép + sort trong STL – O(N log N)
Giải pháp là dùng hàm sort trong thư viện STL: vừa tối ưu chỉ $O(N \log N)$ lần so sánh, vừa gọn lẹ để gọi ra. Ta chỉ cần viết hàm cmp để quy định việc sắp xếp:
cmp(a, b) trả về true khi $a$ phải đứng trước $b$, tức là khi ghép a + b cho số lớn hơn b + a:return b + a < a + b;cmp cho sort phải là quan hệ "nhỏ hơn" chặt. Nếu viết b + a <= a + b thì khi hai số "bằng nhau" (vd $7$ và $77$, ghép kiểu nào cũng $777$) cmp trả true cả hai chiều – vi phạm yêu cầu của std::sort, có thể chạy sai hoặc thậm chí lỗi truy cập bộ nhớ.Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
bool cmp(const string &a, const string &b){
return b + a < a + b;
}
const int MAX = 1e5 + 5;
string a[MAX];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; ++i){
cin >> a[i];
}
sort(a, a + n, cmp);
for(int i = 0; i < n; ++i){
cout << a[i];
}
return 0;
}import sys
from functools import cmp_to_key
def cmp(a, b):
# a đứng trước b nếu ghép a + b lớn hơn b + a
if b + a < a + b:
return -1
if a + b < b + a:
return 1
return 0
data = sys.stdin.read().split()
n = int(data[0])
a = data[1:n + 1]
a.sort(key=cmp_to_key(cmp))
print("".join(a))Trong Python, sort nhận key chứ không nhận hàm so sánh trực tiếp, nên ta bọc cmp bằng functools.cmp_to_key (hàm trả số âm nghĩa là $a$ đứng trước $b$).
Thứ tự từng lần gọi cmp bên trong std::sort phụ thuộc vào cài đặt của thư viện, nên khung chạy tay dưới đây gom cả lệnh sort làm một bước, rồi cho các bạn thấy từng cặp kề nhau sau khi sắp đều đúng quy tắc:
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N \cdot L)$ cho mảng xâu, $L \le 6$.
- Thời gian:
sortthực hiện $O(N \log N)$ lần so sánh, mỗi lần ghép 2 xâu dài tối đa 12 ký tự tốn $O(L)$ ⇒ $O(N \log N \cdot L)$, với $L$ rất nhỏ thì xem như $O(N \log N)$. Đây là bước tốn thời gian nhất của cả bài.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét