Số ghép lớn nhất 2
Đề 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.
4
2 12 3 201220Lờ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à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. Đề 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ưnglong long | Cách 2unsigned 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ó.
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)$.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.
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.
while tìm $p$ được gộp thành 1 bước cho đỡ dài.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.
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.- Phải ghép (
ans = max(ans, mx * p + x)) trước khi cập nhậtmx, để không ghép $x$ với chính nó. - 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ằngsys.stdin.buffer.read().split().
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 |
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.
Nhận xét
Đăng nhận xét