Số ghép lớn nhất 2

Nguồn: CLUE OJ – Chương 14: Cửa sổ trượt + Tham lam Độ khó: Trung bình Tham lam unsigned long long

Đề 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 1\,000\,000$; $1 \le a_i \le 1\,000\,000\,000$.

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

Đây là phiên bản 2 của bài Số ghép lớn nhất. Đề giống hệt, chỉ khác phần giới hạn:

	Số ghép lớn nhất (bài 1)	Số ghép lớn nhất 2 (bài này)
$a_i$	$\le 10^{30}$ (tới 31 chữ số)	$\le 10^9$ (tới 10 chữ số)
$N$	$\le 10^6$	$\le 10^6$
Subtask	20% / 30% / 50%	Không có – mọi test (trừ ví dụ) đều có $n \ge 10^5$
Đáp án	tới 62 chữ số → bắt buộc dùng xâu	tới 20 chữ số → vừa unsigned long long, không vừa long long

Vì số nhỏ hơn nên ta tính được bằng số nguyên, code gọn hơn. Nhưng chính điều đó lại sinh ra một cái bẫy: $10^9$ ghép $10^9$ là $10\,000\,000\,001\,000\,000\,000$ $\approx 10^{19}$, vượt quá LLONG_MAX $\approx 9.22 \cdot 10^{18}$. Bộ test có đúng một test như vậy – và nó "bắt" rất nhiều bạn!

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²)Cách 2O(n)

Bộ testBộ test chính thức có gì?

Bộ test có 100 test. Đề không chia subtask, mình chia nhóm theo $n$:

Test	Nhóm	n	$a_i$	Đáp án
1	Ví dụ của đề	4	2 … 20	1.220
2–70	n = 10^5	100.000	1 … 999.997.919	999.614.931.999.064.301 … 999.997.919.999.793.098
71–90	n = 5·10^5	500.000	1 … 999.997.732	999.959.285.999.957.975 … 999.997.732.999.992.692
91–99	n = 10^6	1.000.000	1 … 999.999.671	999.987.030.999.719.292 … 999.999.671.999.985.097
100	n = 10^6, có hai số 10^9	1.000.000	1 … 1.000.000.000	10.000.000.001.000.000.000

Test 100 có hai số bằng đúng $10^9$ (ở vị trí 8 và 97593), nên đáp án là $10000000001000000000$ – 20 chữ số, lớn hơn LLONG_MAX $= 9223372036854775807$. Mọi test khác có đáp án tối đa 18 chữ số. Kết quả của từng cách theo nhóm test:

Nhóm test	Test	Cách 1 $O(n^2)$	Cách 2 nhưng long long	Cách 2 unsigned long long
Ví dụ	1–1	1/1	1/1	1/1
$n = 10^5$	2–70	0/69	69/69	69/69
$n = 5 \cdot 10^5$	71–90	0/20	20/20	20/20
$n = 10^6$	91–100	0/10	9/10	10/10

Ý tưởngSố ghép tăng theo số đứng trước

Gọi $d$ là số chữ số của $a_j$, số ghép là $\overline{a_i a_j}$ $= a_i \cdot 10^d + a_j$. Cố định $j$ thì biểu thức này tăng theo $a_i$, nên chỉ cần ghép $a_j$ với số lớn nhất đứng trước nó.

Tham lam

Duyệt $j = 2..n$, giữ mx = max của $a_1..a_{j-1}$. Ứng viên là mx * 10^d + a[j]; lấy max các ứng viên. Sau đó cập nhật mx = max(mx, a[j]). Độ phức tạp $O(n)$.

Cái bẫy: kiểu dữ liệu

Số ghép lớn nhất có thể là $10^9 \cdot 10^{10} + 10^9 \approx 1.0 \cdot 10^{19}$. long long chỉ chứa tới $\approx 9.22 \cdot 10^{18}$, còn unsigned long long (không dấu) chứa tới $\approx 1.84 \cdot 10^{19}$ – vừa đủ. Vì mọi số đều dương nên dùng kiểu không dấu là hợp lý.

Em nhập dãy rồi bấm Tiếp. Thanh bên dưới so sánh ứng viên với LLONG_MAX: vượt qua là long long sẽ bị tràn.

Dãy a:

Ví dụ nhanh:

Cách 1Thử mọi cặp $O(n^2)$

Cách "ngây thơ": hai vòng lặp thử mọi cặp $i < j$. Nhớ dùng unsigned long long ngay từ đầu.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi cặp i < j bằng unsigned 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

Vòng while tìm $p$ được gộp thành 1 bước cho đỡ dài.

Không gian$O(n)$

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

Kết quả chạy thật: bản C++ đúng 1/100 test (quá thời gian ở test 2–100), test đúng lâu nhất 0.00s; bản Python (chỉ chạy test 1–10) đúng 1/10 test (quá thời gian ở test 2–10), test đúng lâu nhất 0.02s. Với $n = 10^5$ đã có khoảng $5 \cdot 10^9$ cặp – không thể chạy kịp. Bài này không có subtask nhỏ nên cách vét cạn gần như không được điểm.

Cách 2Giữ số lớn nhất phía trước – Full điểm

Đọc tới đâu xử lý tới đó, không cần mảng: mx là số lớn nhất đã đọc, mỗi số mới x ghép với mx để tạo ứng viên.

C++▶ Chạy tay từng dòng codeCách 2: giữ mx = số lớn nhất phía trước, ghép mx với từng số mới – 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

1. while (p <= x) p *= 10; tìm $p = 10^d$ nhỏ nhất lớn hơn $x$. Với $x = 10^9$ thì $p = 10^{10}$, vẫn vừa kiểu dữ liệu.
2. Phải ghép (ans = max(ans, mx * p + x)) trước khi cập nhật mx, để không ghép $x$ với chính nó.
3. Python không lo tràn số, nhưng $10^6$ phép đổi xâu ra số và lũy thừa 10 khá chậm (bản đầu tiên của mình bị quá thời gian 1 test). Nên mình giữ luôn các số ở dạng bytes, nối xâu và so sánh theo (độ dài, từ điển) như bài 1, đọc cả input một lần bằng sys.stdin.buffer.read().split().

Không gian$O(1)$

Thời gian$O(n)$

Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng lâu nhất 0.10s; bản Python đúng 100/100 test, test đúng lâu nhất 0.74s.

Nếu dùng long long thay cho unsigned long long (chỉ đổi đúng kiểu dữ liệu, còn lại giữ nguyên): bản C++ đúng 99/100 test (sai kết quả ở test 100), test đúng lâu nhất 0.10s. Ở test đó, phép nhân mx * p $= 10^9 \cdot 10^{10}$ bị tràn, ra một số âm vô nghĩa, nên chương trình in ra 3065805681000000000 thay vì 10000000001000000000.

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 $O(n^2)$	C++	1/100	0.00s	Chỉ qua ví dụ; mọi test khác có n ≥ 10^5
	Python	1/10	0.02s	Chạy test 1–10
2'. Max phía trước, long long	C++	99/100	0.10s	Tràn số ở test 100
2. Max phía trước, unsigned long long	C++	100/100	0.10s	Full điểm
	Python	100/100	0.74s	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. Khi đề cho $a_i \le 10^9$, các bạn hãy luôn tự hỏi "kết quả lớn nhất là bao nhiêu?" – ở đây là gần $10^{19}$, nên phải dùng unsigned long long. Còn khi số lên tới $10^{30}$ như bài 1 thì phải chuyển sang xâu.

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 😇