Ghép số

View as PDF




Author:
Problem types
Points: 400 (p) Time limit: 1.0s Memory limit: 1023M Input: stdin Output: stdout

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

  • \(N\) + \(M\) chữ số;
  • Được tạo bởi từ các chữ số của \(A\)\(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

Comments


  • -2
    sunflower    2:43 p.m. 9 mar, 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 feb, 2022 edited

      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 jun, 2020

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

        1 reply

        • 5
          SPyofgame    8:05 a.m. 19 jun, 2020 edited

          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\)\(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\)\(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]\)\(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 reply

          • 4
            jumptozero    7:18 a.m. 18 jun, 2020 edit 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\)\(B\)\(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\)\(B\).
            • Ý tưởng của vòng lặp rất đơn giản:
            • Ta so sánh \(A[i]\)\(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]\)\(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 replies