Ghép số

Tác giả:

Dạng bài

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Cho số tự nhiên \(A\) có \(N\) chữ số và số tự nhiên \(B\) có \(M\) chữ số \((2 ≤ N , M ≤ 200)\). Số nguyên dương \(C\) gồm các tính chất sau đây:

Có \(N\) + \(M\) chữ số;
Được tạo bởi từ các chữ số của \(A\) và \(B\);
Thứ tự trước sau các chữ số của \(B\) trong \(C\) không thay đổi.

Yêu cầu: Tìm số \(C\) nhỏ nhất và số \(C\) lớn nhất.

Input

Dòng đầu ghi số \(A\).
Dòng tiếp theo ghi số \(B\).

Output

Dòng đầu ghi số \(C\) nhỏ nhất
Dòng tiếp theo ghi số \(C\) lớn nhất

Example

Test 1

Input

20
4181

Output

204181
421810

Bình luận

0

quangminhez 6:43 a.m. 21 Tháng 11, 2024

```cpp

-2

sunflower 2:43 p.m. 9 Tháng 3, 2022

mình bị WA 2 test cuối nhưng khi copy input chạy trên máy thì ra kết quả đúng mà không hiểu sao khi nộp lại chạy ra 1 kq khác

2

minhtuanitk20 9:08 p.m. 6 Tháng 2, 2022 ← đã chỉnh sửa →

vậy đối với trường hợp mà số 0 vô nghĩa ở đầu thì ta không thể đổi bằng B ( vì B không được thay đổi và nếu mà chèn số lớn nhất hoặc nhỏ nhất của B vào thì 50 50 là sẽ thay đổi thứ tự của 😎 và nên mình phải chỉ có một cách là chèn vi tri so dau tien cua B trong day dk ad

1

Lê_Gia_Khánh 6:29 p.m. 24 Tháng 6, 2020

Sao vd test nhỏ nhỏ không phải 024181 mà là 204181 vậy 🤔

1 phản hồi

`Spoiler Alert`

Hint 1

Chỉ thứ tự các chữ số trong \(B\) không thay đổi trong \(C\)

Đọc kĩ đề nhé mấy bạn, số \(A\) mình có thể thay đổi vị trí bất kì đó

Ta sẽ tìm cách sắp xếp các chữ số \(A\) trong \(C\) sao cho phù hợp

Hint 2

Xét bài toán con: Giả sử mình đã có một cách sắp xếp các chữ số trong \(A\) phù hợp, và mình ghép tất cả chữ số của \(A\) và \(B\) vào nhau sao cho nó lớn nhất

Mình sẽ dùng kĩ thuật \(two-pointers\) để di chuyển 2 con trỏ \(ptr_A\) và \(ptr_B\) sang tới vị trí cuối cùng của 2 số và xuất ra sao cho tối ưu nhất

Khi này, mình có 2 hướng đi

Nếu \(ptr_A\) chưa ở cuối \(A\): xuất \(A[ptr_A]\) và di chuyển \(ptr_A\) sang phải

Nếu \(ptr_B\) chưa ở cuối \(B\): xuất \(B[ptr_B]\) và di chuyển \(ptr_B\) sang phải

Hint 3

Trong bài toán con trên: Ta sẽ ưu tiên chữ số lớn hơn được xuất trước

Nếu mình được chọn một trong hai số \(A[ptr_A]\) và \(B[ptr_B]\) để xuất ra số lớn nhất.

Mà chữ số được xuất trước lớn hơn thì cả số đó sẽ lớn hơn.

Nên mình sẽ xuất \(max(A[ptr_A], B[ptr_B])\) và di chuyển con trỏ có giá trị \(max\) sang phải

Và cũng từ đây mình rút ra: \(A\) càng lớn thì số được xuất ra càng lớn.

Vậy ta sẽ sắp xếp các chữ số trong \(A\) giảm dần

Hint 4

Trường hợp còn lại cũng tương tự cho đến khi bạn nhận ra \(C\) không chứa các số \(0\) vô nghĩa ở đầu

Sau khi sắp xếp \(A\) nhỏ dần, ta có thể cho một trong 2 số sau lên đầu số \(C\)

Chữ số đầu tiên nhỏ nhất khác \(0\) của \(A\)

Chữ số đầu tiên của \(B\) (phải khác \(0\) và không được chọn vị trí khác)

Vậy chữ số nào bé hơn và khác \(0\) thì ta sẽ chọn

Mà chữ số đầu của \(C\) theo cách chọn tối ưu trên sẽ không phụ thuộc cách sắp xếp \(A\)

Nên ta có swap vị trí chữ số bé nhất khác \(0\) của \(A\) lên đầu khi nó bé hơn chữ số đầu của \(B\)

Reference AC code | \(O(n \log_2 n)\) time | \(O(n)\) auxiliary space | Two-pointers, String

C++

int main()
{
    string s; /// so A bieu dien kieu string
    cin >> s;

    string t; /// so B bieu dien kieu string
    cin >> t;

    sort(all(s)); /// sap xep giam dan
    if (s.front() == '0') /// chu so dau A la so 0
    {
        for (char &c : s) /// tim trong A phan tu dau khac 0
        {
            if (c != '0') /// da tim ra phan tu do
            {
                if (c < t.front()) /// kiem tra xem no co nho hon chu so dau cua B khong
                {
                    swap(c, s.front()); /// neu co thi swap len A
                    break;              /// ta khong can tim them nua
                }
            }
        }
    }

    int n = s.size(), m = t.size();
    for (int ps = 0, pt = 0; ps < n && pt < m; ) /// 2 con tro ps, pt
    {
        if (s[ps] < t[pt] && (ps != 0 || pt != 0 || s[ps] != '0')) /// loai bo phan tu leading_zero
             cout << s[ps++]; /// Xuat s[ps] va di chuyen con tro sang phai
        else cout << t[pt++]; /// Xuat t[pt] va di chuyen con tro sang phai  
        if (pt == m) while (ps < n) cout << s[ps++]; /// Da in het B, nen xuat het A
        if (ps == n) while (pt < m) cout << t[pt++]; /// Da in het A, nen xuat het B
    }
    cout << eol;

    sort(all(s), greater<char>()); /// sap xep tang dan
    for (int ps = 0, pt = 0; ps < n && pt < m; ) /// 2 con tro ps, pt
    {
        if (s[ps] > t[pt]) /// chon phan tu co gia tri lon hon
             cout << s[ps++]; /// Xuat s[ps] va di chuyen con tro sang phai
        else cout << t[pt++]; /// Xuat t[pt] va di chuyen con tro sang phai  
        if (pt == m) while (ps < n) cout << s[ps++]; /// Da in het B, nen xuat het A
        if (ps == n) while (pt < m) cout << t[pt++]; /// Da in het A, nen xuat het B
    }
    return 0;
}

1 phản hồi

4
jumptozero 7:18 a.m. 18 Tháng 6, 2020 ← chỉnh sửa 5 →
Mình xin chia sẻ lời giải bài toán này như sau:

Đầu tiên ta có chú ý đó là: Vì \(C\) được tạo từ các chữ số của \(A\) và \(B\) và \(C\) có \(N+M\) chữ số. Nên nếu \(C\) có số \(0\) đứng đầu thì xem như số đó không thỏa mãn , vì nó không được tính là \(N+M\) chữ số.

Ví dụ: \(A=10,B=1\). Thì số \(C=011\) là không thỏa mãn yêu cầu bài toán vì số chữ số thực sự của nó chỉ là \(2\ne 3\).

Tiếp theo ta đến phần tìm \(C\) nhỏ nhất.

Vì thứ tự của chuỗi \(A\) ta có thể tùy ý thay đổi, còn chuỗi \(B\) thì không, do đó để số \(C\) nhỏ nhất thì ta làm một việc đó là :

Ta sẽ sắp xếp lại chuỗi \(A\) thỏa mãn tính chất sau:

Nếu trong chuỗi \(A\) không có kí tự nào bằng \(0\) thì ta sẽ sắp xếp chuỗi theo tự tăng dần, tức là \(A[0],A[1],...,A[N-1]\)(trong đó \(A[0]<=A[1]<=...<=A[N-1]\))

Nếu trong chuỗi \(A\) tồn tại kí tự bằng \(0\) thì ta sẽ sắp xếp chuỗi theo dạng sau: \(s,0,0,...,A[i],A[i+1],...,A[N-1]\) (trong đó s là kí tự nhỏ nhất khác '0' , còn các phần tử còn lại ta sắp xếp theo tự tăng dần).

Ví dụ: Giả sử có có \(A=36002102\). Thì khi đó ta sắp xếp lại \(A\) như sau: \(A=10002236\).

Việc sắp xếp như vậy, sẽ giúp ta dễ dàng tìm được \(C\) thông qua việc sử dụng một vòng while và hai con trỏ tương ứng với hai chuỗi \(A\) và \(B\).

Ý tưởng của vòng lặp rất đơn giản:

Ta so sánh \(A[i]\) và \(B[j]\) để tìm ra số nhỏ nhất, và cộng vào chuỗi \(res\) (chuỗi \(res\) khởi tạo ban đầu là rỗng).

Nếu \(A[i]>B[j]\) thì ta cộng \(B[j]\) vào \(res\), ngược lại nếu \(A[i]<B[j]\) thì ta cộng \(A[i]\) vào \(res\).

Điểm hay của bài toán này đó là khi \(A[i]=B[j]\) thì ta chọn \(A[i]\) hay \(B[j]\) để cộng vào \(res\) ???

Để giải quyết nút thắt này, ta cần phải so sánh \(A[i+1]\) và \(B[j+1]\).

Các bạn có thể xem đoạn xử lý dưới đây:

C++
if(s1[i]<s2[j]) {res+=s1[i];i++;} else if(s1[i]>s2[j]){res+=s2[j];j++;} else { if(s1[i+1]<s2[j+1]&&i+1<s1.size()&&j+1<s2.size()) {res+=s1[i];i++;continue;} if(s1[i+1]>s2[j+1]&&i+1<s1.size()&&j+1<s2.size()) {res+=s2[j];j++;continue;} if(i+1==s1.size()||j+1==s2.size()) {res+=s2[j];j++;continue;} if(s1[i+1]==s2[j+1]&&i+1<s1.size()&&j+1<s2.size()) {res+=s2[j];j++;continue;} } continue;

Như vậy ta đã giải quyết xong phần tìm \(C\) nhỏ nhất,

Tiếp theo đến phần tìm \(C\) lớn nhất. Phần này tương tự phần tìm \(C\) nhỏ nhất !

Như vậy là bài toán đã giải quyết xong.

Các bạn có thể tham khảo code của mình tại \(\href{https://ideone.com/5EhCY2}{đây}\)

Nếu có gì sai hoặc khó hiểu, các bạn cứ comment nhé!

P/s: Code mình hơi xấu !
2 phản hồi