Ghép Số
Đề bài
Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 128 megabyte
Cho hai số nguyên dương $x$, $y$, ta xây dựng số $z$ bằng cách ghép các chữ số của $x$ và $y$ sao cho thứ tự các chữ số của $x$ và $y$ vẫn giữ nguyên trên $z$. Tìm giá trị bé nhất và lớn nhất của $z$.
Dữ liệu vào: một dòng gồm 2 số nguyên dương $x$, $y$.
Dữ liệu ra: dòng thứ nhất ghi giá trị bé nhất của $z$ và dòng thứ hai ghi giá trị lớn nhất của $z$.
- Subtask 1 (50% điểm): $1 \le x, y \le 10^8$.
- Subtask 2 (50% điểm): $1 \le x, y \le 10^{10000}$ (độ dài tối đa $10^4$ chữ số).
Dữ liệu đảm bảo không có các chữ số 0 vô nghĩa của $x$ và $y$.
13 261236
2613Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
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 nhanh nếu bạn nào xem đề chưa hiểu: hãy ghép các chữ số của $x$ và $y$ lại tạo thành số $z$ sao cho trong $z$ các chữ số của $x$ và $y$ vẫn giữ nguyên thứ tự như ban đầu. Nhìn ví dụ mẫu $x = 13$, $y = 26$ thì Min = 1236 và Max = 2613. Khi Min = 1236 thì 1 vẫn đứng trước 3 giống như trong $x$, và 2 vẫn đứng trước 6 giống như trong $y$; tương tự với Max. Còn nếu kết quả là 3261 thì sai vì 3 lại đứng trước 1, hay 6132 thì 6 lại đứng trước 2.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
50%Subtask 1: vét cạn bằng dãy nhị phân – O(N · 2^N)
Subtask 1 có thể giải quyết bằng đệ quy quay lui, hoặc tối ưu hơn nếu kết hợp kỹ thuật 2 con trỏ. Tuy nhiên mình sẽ giới thiệu đến các bạn thuật toán tệ nhất, đó là vét cạn xét tất cả mọi trường hợp có thể 😜
Tại sao mình lại quyết định như vậy? Vì với quan điểm của mình, nếu đến cách tệ nhất mà các bạn còn không làm được thì đừng xem những cách tối ưu hơn, vì có xem các bạn cũng sẽ không hiểu được đâu. Bạn học viên gửi đề này cho mình không thể giải quyết theo bất kỳ cách nào dù là tệ nhất, và mình thử gửi đề cho một số bạn khác thì một số cũng y như vậy, nên mình quyết định hướng dẫn cách dễ nhất có thể (đồng nghĩa là tệ nhất đấy 😂). Thêm một lý do nữa: dù các bạn giải được theo cách tối ưu thì cũng hãy vẫn cài đặt cách vét cạn, vì ta sẽ dùng nó làm công cụ kiểm tra tính chính xác cho cách làm tối ưu – vét cạn chỉ chạy chậm thôi chứ luôn cho ra kết quả chính xác (tất nhiên phải cài đặt đúng). Bạn nào chưa biết về điều này thì xem bài viết Hạn chế lỗi Wrong Answer của mình nhé.
Vét cạn ở đây nghĩa là đưa ra tất cả các số hợp lệ khi ghép từng chữ số của $x$ với $y$ mà giữ đúng thứ tự, rồi tìm Min, Max. Với $x = 13$, $y = 26$ thì có các cách ghép: 1326, 1236, 1263, 2136, 2163, 2613, nên Min = 1236 và Max = 2613.
Cái khó là tìm ra tất cả các cách ghép hợp lệ. Bạn nào tinh ý sẽ thấy: chuỗi $z$ có độ dài x.length() + y.length(), và tại mỗi vị trí của $z$ (xét từ trái qua) ta chỉ quyết định nên lấy chữ số tiếp theo của chuỗi $x$ hay của chuỗi $y$. Ví dụ 2136 là: lấy ký tự đầu của $y$, rồi ký tự đầu của $x$, rồi ký tự tiếp theo của $x$, sau cùng là ký tự cuối của $y$.
length_x + length_y: bit 0 nghĩa là lấy chữ số tiếp theo của $x$, bit 1 nghĩa là lấy chữ số tiếp theo của $y$. Chỉ xét những dãy có đúng length_y bit 1 (khi đó số bit 0 cũng đúng bằng length_x).Ví dụ $x = 13$, $y = 26$, có $2^4 = 16$ dãy nhị phân độ dài 4, trong đó chỉ có 6 dãy có đúng 2 bit 0 và 2 bit 1 (ô xanh), mỗi dãy cho ra một cách ghép:
0000000100100011z = 132601000101z = 12360110z = 1263011110001001z = 21361010z = 216310111100z = 2613110111101111Chẳng hạn dãy 0101: bit 0 đầu lấy ký tự đầu của $x$ ⇒ z = 1, bit 1 lấy ký tự đầu của $y$ ⇒ z = 12, bit 0 lấy ký tự tiếp theo của $x$ ⇒ z = 123, bit 1 lấy ký tự tiếp theo của $y$ ⇒ z = 1236. Vậy để làm được bài này trước tiên các bạn phải làm được bài liệt kê các dãy nhị phân có chiều dài $N$ đã nhé.
Xem code vét cạn (subtask 1)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
string x, y;
cin >> x >> y;
int length_x = (int)x.length();
int length_y = (int)y.length();
int n = length_x + length_y;
int sz = (int)pow(2.0, n);
string Max = x + y, Min = x + y;
for(int i = 0; i < sz; ++i){
int a[n] = {0};
int j = n - 1;
int temp = i;
int cnt1 = 0;
while(temp != 0){
a[j] = temp % 2;
temp /= 2;
if(a[j] == 1){
cnt1++;
}
j--;
}
if(cnt1 == length_y){
string s;
int k = 0, l = 0;
for(j = 0; j < n; ++j){
if(a[j] == 0){
s.push_back(x[k++]);
}
else{
s.push_back(y[l++]);
}
}
Max = max(Max, s);
Min = min(Min, s);
}
}
cout << Min << endl
<< Max;
return 0;
}Giải thích một số chỗ trong code ở trên:
- Để cho đơn giản thì $x$, $y$ được đọc vào ở dạng chuỗi, từ đó lấy ra chữ số bất kỳ thông qua chỉ số index; chứ lưu ở dạng số thì muốn lấy từng chữ số từ trái qua phải cũng phức tạp.
- Khởi tạo Max, Min bằng
x + y(phép+nối chuỗi, "13" + "26" = "1326"), đây là 1 cách ghép hợp lệ. Dùng chuỗi rất tiện vì phép so sánh chuỗi của C++ so từng ký tự từ trái qua theo mã ASCII, mà các chuỗi đều cùng độ dài nên cũng chính là so sánh số. - Khi tính từng bit bằng cách chia lấy dư cho 2 trong vòng
while, biếncnt1đếm số bit 1; nếucnt1bằng độ dài chuỗi $y$ thì đó là dãy hợp lệ, không cần đếm bit 0. - Với dãy hợp lệ, biến
kduyệt theo chuỗi $x$, biếnlduyệt theo chuỗi $y$: gặp bit 0 thì đưax[k++]vào $z$, gặp bit 1 thì đưay[l++]vào $z$. - Có chuỗi $z$ rồi thì so sánh cập nhật Min, Max bằng hàm
min,maxcó sẵn của C++.
Đánh giá độ phức tạp: không gian $O(N)$ cho mảng bit; thời gian: xét $2^N$ dãy, mỗi dãy khởi tạo mảng $N$ phần tử, tìm nhị phân mất khoảng $N$ bước, dựng chuỗi $z$ thêm $N$ bước, tổng cộng $O(3 \cdot N \cdot 2^N)$, bỏ hằng số thì là $O(N \cdot 2^N)$. Với $x, y \le 10^8$ (tối đa 9 chữ số mỗi số) thì $N \le 18$, khoảng $3 \cdot 18 \cdot 2^{18} \approx 14$ triệu lần lặp, dưới ngưỡng $(3 \text{ đến } 5) \cdot 10^7$ của 1 giây nên yên tâm không TLE. Nếu đang trong phòng thi mà nhẩm ra được độ phức tạp ổn thì mình cũng quất cách này cho nhanh gọn, đảm bảo không sai được vì đã vét cạn mọi trường hợp. Nhưng nếu tổng độ dài lên tới khoảng 25 trở lên thì không dùng cách này được nữa.
100%Subtask 2: kỹ thuật 2 con trỏ (Two Pointers)
Với Subtask 2, độ dài tới $10^4$ chữ số thì $O(N \cdot 2^N)$ là con số cực lớn, chắc chắn TLE. Cách giải tối ưu là dùng kỹ thuật 2 con trỏ (Two Pointers). Bạn nào chưa biết thì cứ xem mình áp dụng vào bài này là sẽ rõ hen.
Giả sử $x$ = "8642", $y$ = "531". Vì các chữ số phải giữ nguyên vị trí tương đối, nên $z$ bản chất là lấy lần lượt từng chữ số của $x$, $y$ theo thứ tự từ trái qua phải ghép lại: muốn lấy chữ số 6 của $x$ thì trước đó phải lấy chữ số 8 rồi; muốn lấy chữ số 1 của $y$ thì trước đó phải lấy 5 và 3 rồi. Đáp án Max chính xác là "8654321":
| So sánh x[i], y[j] | Chọn | z |
|---|---|---|
| 8 > 5 | x[0] = 8 | 8 |
| 6 > 5 | x[1] = 6 | 86 |
| 4 < 5 | y[0] = 5 | 865 |
| 4 > 3 | x[2] = 4 | 8654 |
| 2 < 3 | y[1] = 3 | 86543 |
| 2 > 1 | x[3] = 2 | 865432 |
| 1 chuỗi đã hết | nối phần còn lại "1" | 8654321 |
Quy tắc: khởi tạo $i = 0$, $j = 0$ là index duyệt chuỗi $x$ và $y$. Lặp khi cả 2 chuỗi đều còn ký tự. Nếu đang tìm Max thì so sánh x[i] với y[j], thằng nào lớn hơn thì chọn (để chữ số lớn đứng trước); tìm Min thì thằng nào nhỏ hơn thì chọn. Chọn chuỗi nào thì index chuỗi đó tăng lên, chuỗi không được chọn giữ nguyên index. Khi 1 trong 2 chuỗi đã hết thì nối toàn bộ phần còn lại của chuỗi kia vào kết quả. Cách duyệt đồng thời 2 index rồi so sánh để quyết định chọn thằng nào như vậy chính là "kỹ thuật 2 con trỏ"; điển hình nhất là bài trộn 2 mảng tăng dần thành 1 mảng tăng dần mà nhiều bạn đã gặp khi học mảng 1 chiều.
Mọi thứ sẽ rất đơn giản nếu các chữ số đều khác nhau. Nhưng nếu x[i] bằng y[j] thì sao? À ha, lúc này vấn đề phức tạp mới bắt đầu đây, chọn sai thằng là sai nhé các bạn. Ví dụ $x$ = "12", $y$ = "134", tìm Max: so sánh x[0] và y[0] đều là 1, nếu chọn x[0] ⇒ z = "1", tiếp theo x[1] = 2 > y[0] = 1 nên chọn ⇒ z = "12", chuỗi $x$ hết, nối phần còn lại của $y$ ⇒ z = "12134". Trong khi đáp án đúng là "13412", có được nếu ngay từ đầu ta chọn y[0].
subX là chuỗi con của $x$ từ vị trí $i$ đến cuối, subY là chuỗi con của $y$ từ vị trí $j$ đến cuối. Nếu subX + subY lớn hơn subY + subX thì khi tìm Max ta chọn lấy theo $x$, ngược lại chọn theo $y$; khi tìm Min thì làm ngược lại. Nếu 2 chuỗi ghép bằng nhau thì chọn thằng nào cũng được ^^Như ví dụ trên, subX = "12", subY = "134" (trùng hợp là ký tự trùng nằm ngay index đầu tiên; thực tế nhiều khi chỗ trùng ở index phía sau). subX + subY = "12134", subY + subX = "13412" > "12134", nên tìm Max thì chọn y[j], tìm Min thì chọn x[i]. Các bạn có thể kiểm nghiệm quy luật này qua nhiều ví dụ khác nhau để thấy tính đúng đắn của nó.
Mô phỏng: em nhập $x$, $y$ rồi bấm Tiếp để xem 2 con trỏ $i$, $j$ chạy: mỗi bước chọn chữ số tốt hơn đặt vào $z$; khi 2 chữ số bằng nhau thì so sánh 2 cách ghép phần còn lại (tìm Min trước, rồi tìm Max):
#include <bits/stdc++.h>
using namespace std;
string findMin(string x, string y){
string z;
int length_x = (int)x.length();
int length_y = (int)y.length();
int i = 0, j = 0;
while(i < length_x && j < length_y){
if(x[i] < y[j]){
z += x[i++];
}
else if(y[j] < x[i]){
z += y[j++];
}
else{
string subX = x.substr(i);
string subY = y.substr(j);
if(subX + subY < subY + subX){
z += x[i++];
}
else{
z += y[j++];
}
}
}
if(j < length_y){
z += y.substr(j, length_y - j);
}
else{
z += x.substr(i, length_x - i);
}
return z;
}
string findMax(string x, string y){
string z;
int length_x = (int)x.length();
int length_y = (int)y.length();
int i = 0, j = 0;
while(i < length_x && j < length_y){
if(x[i] > y[j]){
z += x[i++];
}
else if(y[j] > x[i]){
z += y[j++];
}
else{
string subX = x.substr(i);
string subY = y.substr(j);
if(subX + subY > subY + subX){
z += x[i++];
}
else{
z += y[j++];
}
}
}
if(j < length_y){
z += y.substr(j, length_y - j);
}
else{
z += x.substr(i, length_x - i);
}
return z;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
string x, y;
cin >> x >> y;
cout << findMin(x, y) << endl;
cout << findMax(x, y);
return 0;
}import sys
def findMin(x, y):
z = []
length_x, length_y = len(x), len(y)
i = j = 0
while i < length_x and j < length_y:
if x[i] < y[j]:
z.append(x[i]); i += 1
elif y[j] < x[i]:
z.append(y[j]); j += 1
else:
subX = x[i:]
subY = y[j:]
if subX + subY < subY + subX:
z.append(x[i]); i += 1
else:
z.append(y[j]); j += 1
z.append(y[j:] if j < length_y else x[i:])
return "".join(z)
def findMax(x, y):
z = []
length_x, length_y = len(x), len(y)
i = j = 0
while i < length_x and j < length_y:
if x[i] > y[j]:
z.append(x[i]); i += 1
elif y[j] > x[i]:
z.append(y[j]); j += 1
else:
subX = x[i:]
subY = y[j:]
if subX + subY > subY + subX:
z.append(x[i]); i += 1
else:
z.append(y[j]); j += 1
z.append(y[j:] if j < length_y else x[i:])
return "".join(z)
x, y = sys.stdin.read().split()
print(findMin(x, y))
print(findMax(x, y))Giải thích một số chỗ trong code ở trên:
- Hàm
substr(sub string – chuỗi con) có sẵn trong string của C++:x.substr(i)trả về chuỗi con từ index $i$ đến cuối;x.substr(i, length_x - i)trả về chuỗi con bắt đầu tại $i$ và lấy đủlength_x - iký tự. - Phép
+của string tạo chuỗi mới là 2 chuỗi nối lại: "12" + "345" = "12345".
Đánh giá độ phức tạp: không gian $O(1)$ ngoài các chuỗi. Hàm substr có độ phức tạp $O(N)$ với $N$ là độ dài chuỗi con. Đẹp nhất là khi các chữ số của 2 chuỗi đều khác nhau, mỗi hàm chỉ duyệt khoảng max(length_x, length_y) bước, tức $O(\max(\text{length}_x, \text{length}_y))$. Xấu nhất là khi substr liên tục bị gọi, ví dụ 2 chuỗi toàn chữ số giống nhau: tổng chi phí khoảng $N + (N - 1) + \ldots + 1 = \frac{N(N + 1)}{2}$, tức $O(N^2)$; với $N = 10^4$ là khoảng $10^8$ thao tác so sánh ký tự (thực hiện bằng các lệnh copy, so sánh khối bộ nhớ rất nhanh) nên vẫn yên tâm không TLE. Mình chạy thử với 2 chuỗi $10^4$ chữ số toàn số 1, bản C++ chỉ mất khoảng 0.03 giây, bản Python khoảng 0.05 giây.
Viết gọn bằng con trỏ hàm
Đến đây lẽ ra xong rồi, nhưng mình nói thêm cái này để các bạn có thêm kiến thức. Nhìn lại thì 2 hàm findMin, findMax giống nhau hơn 90%, chỉ khác phép so sánh >, <. Trong phòng thi thì mình cứ copy ra rồi đổi dấu cho nhanh, nhưng khi không bị áp lực thời gian thì viết 2 hàm gần như y hệt nhìn thật chán, không có clean code gì hết. Ta có thể chỉ viết 1 hàm bằng con trỏ hàm (Function Pointer): hàm nhận thêm 1 tham số là hàm so sánh 2 chuỗi; khi cần tìm Min thì truyền checkMin, khi cần tìm Max thì truyền checkMax. Đây là ứng dụng phổ biến của con trỏ hàm (giống như chỉ viết 1 hàm sắp xếp mà sắp được cả tăng dần lẫn giảm dần).
Vì chỗ so sánh x[i] với y[j] là so sánh ký tự, còn subX + subY với subY + subX là so sánh chuỗi, nên để thống nhất mình tạo string xx = x[i], string yy = y[j] rồi so sánh 2 chuỗi 1 ký tự này; tất cả đều thành so sánh giữa 2 chuỗi.
Xem code dùng con trỏ hàm
#include <bits/stdc++.h>
using namespace std;
bool checkMin(string a, string b){
return a < b;
}
bool checkMax(string a, string b){
return a > b;
}
string findMaxMin(string x, string y, bool (*compare)(string, string)){
string z;
int length_x = (int)x.length();
int length_y = (int)y.length();
int i = 0, j = 0;
while(i < length_x && j < length_y){
string xx, yy;
xx += x[i];
yy += y[j];
if(compare(xx, yy)){
z += x[i++];
}
else if(compare(yy, xx)){
z += y[j++];
}
else{
string subX = x.substr(i);
string subY = y.substr(j);
if(compare(subX + subY, subY + subX)){
z += x[i++];
}
else{
z += y[j++];
}
}
}
if(j < length_y){
z += y.substr(j, length_y - j);
}
else{
z += x.substr(i, length_x - i);
}
return z;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
string x, y;
cin >> x >> y;
cout << findMaxMin(x, y, checkMin) << endl;
cout << findMaxMin(x, y, checkMax);
return 0;
}Độ phức tạp vẫn y như ở trên, có cái là code gọn hơn thôi hehe.
Mình đã kiểm tra cả 3 bản C++ (và bản Python mình viết thêm) với 300 cặp số ngẫu nhiên có nhiều chữ số trùng nhau, so với cách thử mọi cách ghép, đều cho cùng kết quả.
- 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