Số ghép lớn nhất

Nguồn: CLUE OJ – Chương 14: Cửa sổ trượt + Tham lam Độ khó: Trung bình Tham lam Số lớn dạng xâu

Đề 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.

Ví dụ – input

4
2 12 3 20

Ví dụ – output

1220

Lờ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ộp bài

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngmax phía trướcCách 1O(n²) long longCách 2O(n²) xâuCách 3O(n)

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$.

Tham lam

Duyệt $j = 2, 3, \ldots, n$ và luôn giữ 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:

Dãy a:

Ví dụ nhanh:

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].

C++▶ Chạy tay từng dòng codeCách 1: thử mọi cặp i < j, số ghép = a[i]·10^d + a[j] tính bằng long long – O(n²).

Dữ liệu vào (stdin) – sửa thoải mái4 2 12 3 20

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n)$

Thời gian$O(n^2)$

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.

C++▶ Chạy tay từng dòng codeCách 2: thử mọi cặp, số ghép là nối xâu, so sánh số lớn bằng hàm nho – O(n²·L).

Dữ liệu vào (stdin) – sửa thoải mái4 2 12 3 20

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n \cdot L)$

Thời gian$O(n^2 \cdot L)$, $L$ = số chữ số

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$).

C++▶ Chạy tay từng dòng codeCách 3: giữ mx = số lớn nhất phía trước, mỗi a[j] chỉ ghép với mx – O(n·L).

Dữ liệu vào (stdin) – sửa thoải mái4 2 12 3 20

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Thứ tự hai lệnh if rất quan trọng: phải ghép mx + x trước rồi mới cập nhật mx, vì $a_j$ không được ghép với chính nó.
2. 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.
3. Bản Python giữ các số ở dạng bytes và 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.

Không gian$O(L)$

Thời gian$O(n \cdot L)$

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

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình, giới hạn 1 giây. Bộ test rất nặng (gần 30 MB mỗi test lớn) nên nhớ thê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é.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇