Số ghép lớn nhất
Đề bài
Ta định nghĩa một "số ghép" đối với 2 số $u$ và $v$, là một số nguyên dương $T$ sao cho $T$ là giá trị $u$ và được ghép thêm các chữ số của số $v$ vào sau chữ $u$.
Ví dụ số ghép của 2 số 32 và 15 là số 3215.
Bạn được cho một dãy số nguyên dương $a$ có $N$ số nguyên, các số được đánh số từ 1 đến $N$ theo chiều từ trái sang phải. Bạn hãy tìm một "số ghép" có giá trị lớn nhất sao cho số ghép đó được tạo thành từ 2 số nguyên dương $a_i$ và $a_j$ và $i < j$.
Input:
- Dòng đầu tiên gồm một số nguyên dương $N$ là số lượng phần tử trong dãy $a$.
- Dòng thứ hai gồm $N$ số nguyên dương, số nguyên dương thứ $i$ tương ứng là giá trị $a_i$.
Ràng buộc: $1 \le N \le 10^6$; $1 \le a_i \le 10^{30}$.
Subtask:
- 20% số test đầu tiên có $n \le 10^2$, $a_i \le 10^9$;
- 30% số test tiếp theo có $n \le 10^3$;
- 50% số test còn lại không có giới hạn gì thêm.
Output: Một dòng duy nhất chứa một số nguyên dương là "số ghép" lớn nhất của tất cả các cặp số được tạo thành trong dãy $a$.
Giải thích ví dụ: có các cặp số sau: {2, 12}, {2, 3}, {2, 20}, {12, 3}, {12, 20}, {3, 20}. Cặp tạo thành "số ghép" lớn nhất là cặp {12, 20} vì số ghép đó là 1220.
4
2 12 3 201220Lời mở đầu
Bài này có "người anh em" là Số ghép lớn nhất 2 (cùng đề, nhưng $a_i \le 10^9$ và không chia subtask). Ở bài 1 này, $a_i$ lên tới $10^{30}$ – tức là 31 chữ số, không kiểu số nguyên nào của C++ chứa nổi. Vậy ta phải làm việc với số dưới dạng xâu. Mình sẽ đi từ cách thử mọi cặp (ăn 20%, rồi 50%), tới cách tham lam $O(n)$ chỉ cần nhớ số lớn nhất đứng trước.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test (test 1 là ví dụ của đề), chia nhóm như sau:
| Test | Subtask | n | Số chữ số của $a_i$ | Số chữ số của đáp án |
|---|---|---|---|---|
| 1–20 | 1 (20%) | 4 … 10 | 1 … 9 | 4 … 18 |
| 21–50 | 2 (30%) | 1.000 | 15 … 30 | 60 |
| 51–70 | 3 (50%) | 10.000 | 15 … 30 | 60 |
| 71–95 | 3 (50%) | 100.000 | 15 … 30 | 60 |
| 96–100 | 3 (50%) | 1.000.000 | 15 … 30 | 60 |
Subtask của đề khớp hoàn toàn với bộ test: test 1–20 có $n \le 10$, mọi $a_i$ có tối đa 9 chữ số; test 21–50 có $n = 1000$ nhưng $a_i$ đã dài 15–30 chữ số (nên đáp án dài tới 60 chữ số!); test 51–100 có $n$ từ $10^4$ đến $10^6$. Không có số nào bắt đầu bằng chữ số 0. Kết quả của từng cách theo subtask:
| Subtask | Đề ghi | Test | Cách 1 $O(n^2)$, long long | Cách 2 $O(n^2)$, xâu | Cách 3 max tiền tố |
|---|---|---|---|---|---|
| 1 (20%) | $n \le 100,\ a_i \le 10^9$ | 1–20 | 20/20 | 20/20 | 20/20 |
| 2 (30%) | $n \le 1000$ | 21–50 | 0/30 | 30/30 | 30/30 |
| 3 (50%) | còn lại | 51–100 | 0/50 | 0/50 | 50/50 |
Ý tưởngCố định số đứng sau, chọn số đứng trước lớn nhất
Gọi $d$ là số chữ số của $a_j$. Số ghép của $a_i$ và $a_j$ chính là
$$\overline{a_i a_j} = a_i \cdot 10^{d} + a_j.$$
Khi cố định $j$ thì $10^d$ và $a_j$ là hằng số, nên số ghép càng lớn khi $a_i$ càng lớn. Vậy với mỗi $j$, cặp tốt nhất là ghép số lớn nhất trong $a_1, \ldots, a_{j-1}$ với $a_j$.
mx = số lớn nhất đã gặp phía trước. Ứng viên của $j$ là "mx ghép a[j]"; đáp án là ứng viên lớn nhất. Xét xong $j$ thì cập nhật mx = max(mx, a[j]). Chỉ một lần duyệt – $O(n)$ phép so sánh số.Hai chỗ dễ nhầm:
- Không phải cứ lấy 2 số lớn nhất: ví dụ của đề có $20$ lớn nhất nhưng đứng cuối, nên không thể làm số đứng trước. Đáp án $1220$ đến từ $12$ (lớn nhất trong phần đứng trước $20$).
- Không được đổi thứ tự như bài "ghép các số thành số lớn nhất" quen thuộc: ở đây $a_i$ luôn phải đứng trước $a_j$ với $i < j$.
So sánh hai số lớn viết dạng xâu (không có chữ số 0 ở đầu): số nào nhiều chữ số hơn thì lớn hơn; nếu cùng số chữ số thì so sánh từ điển (từng ký tự từ trái sang) – với xâu cùng độ dài, thứ tự từ điển trùng với thứ tự giá trị. Chú ý: so sánh từ điển trực tiếp "9" > "12" là sai về giá trị, nên phải so độ dài trước!
Em nhập dãy rồi bấm Tiếp để xem mx và đáp án thay đổi thế nào:
Cách 1Thử mọi cặp với long long – Subtask 1
Ở subtask 1, $a_i \le 10^9$ nên số ghép có tối đa $9 + 9 = 18$ chữ số (nhỏ hơn $10^{18}$), vừa với long long (tới khoảng $9.2 \cdot 10^{18}$). Thử mọi cặp $i < j$: tìm $p = 10^d$ bằng cách nhân 10 cho tới khi $p > a_j$, rồi số ghép là a[i] * p + a[j].
Kết quả chạy thật: bản C++ đúng 20/100 test (sai kết quả ở test 21–22, 24–26, 28, 31, 33, 36, 38–39, 41–42, 44–45, 47–48, 50, 52–54, 56, 58, 60, 64–70; quá thời gian ở test 23, 27, 29–30, 32, 34–35, 37, 40, 43, 46, 49, 51, 55, 57, 59, 61–63, 71–100), test đúng lâu nhất 0.01s; bản Python (chỉ chạy test 1–50) đúng 50/50 test, test đúng lâu nhất 0.52s. Từ test 21, $a_i$ dài 15–30 chữ số nên cin không đọc nổi vào long long → sai kết quả ngay; các test lớn còn bị quá thời gian vì $O(n^2)$. Bản Python thì khác: số nguyên của Python không giới hạn độ dài nên vẫn đúng ở subtask 2, chỉ chậm ở test lớn.
Cách 2Thử mọi cặp, số lớn dạng xâu – Subtask 1, 2
Đọc mỗi số vào một string. Số ghép chỉ đơn giản là nối xâu a[i] + a[j]. Để so sánh hai số dạng xâu, mình viết hàm nho(x, y) trả về true nếu $x < y$: khác độ dài thì xâu ngắn hơn nhỏ hơn, cùng độ dài thì so sánh từ điển.
Kết quả chạy thật: bản C++ đúng 50/100 test (quá thời gian ở test 51–100), test đúng lâu nhất 0.05s; bản Python (chỉ chạy test 1–75) đúng 50/75 test (quá thời gian ở test 51–75), test đúng lâu nhất 0.35s. Ăn trọn subtask 1, 2. Với $n = 10^4$ đã có khoảng $5 \cdot 10^7$ cặp, mỗi cặp phải tạo một xâu dài tới 60 ký tự – không kịp 1 giây.
Cách 3Giữ số lớn nhất phía trước – Full điểm
Cài đặt đúng ý tưởng tham lam: không cần lưu cả mảng, đọc tới đâu xử lý tới đó. Biến mx giữ số lớn nhất trong các số đã đọc (ban đầu là $a_1$).
- Thứ tự hai lệnh
ifrất quan trọng: phải ghépmx + xtrước rồi mới cập nhậtmx, vì $a_j$ không được ghép với chính nó. - Mỗi bước chỉ nối và so sánh xâu dài tối đa 62 ký tự, tổng cộng cỡ $6 \cdot 10^7$ phép tính ký tự – rất nhanh.
- Bản Python giữ các số ở dạng
bytesvà so sánh theo (độ dài, từ điển) như C++; trước khi nối xâu thì kiểm tra độ dài trước để bỏ qua nhanh những ứng viên chắc chắn ngắn hơn đáp án.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng lâu nhất 0.13s; bản Python đúng 100/100 test, test đúng lâu nhất 0.85s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Test đúng lâu nhất | Ghi chú |
|---|---|---|---|---|
1. Mọi cặp, long long | C++ | 20/100 | 0.01s | Chỉ subtask 1; số 15–30 chữ số không vừa long long |
| Python | 50/50 | 0.52s | Chạy test 1–50; Python tự có số lớn nên đúng cả subtask 2 | |
| 2. Mọi cặp, so sánh xâu | C++ | 50/100 | 0.05s | Subtask 1, 2 |
| Python | 50/75 | 0.35s | Chạy test 1–75 | |
| 3. Max tiền tố (tham lam) | C++ | 100/100 | 0.13s | Full điểm |
| Python | 100/100 | 0.85s | Full điểm |
ios::sync_with_stdio(0); cin.tie(0);. Bài Số ghép lớn nhất 2 dùng đúng ý tưởng này, chỉ khác là số nhỏ hơn nên tính bằng số nguyên – nhưng lại có một cái bẫy tràn số, các bạn đọc tiếp nhé.
Nhận xét
Đăng nhận xét