ABC

Nguồn: Bài tập học viên hỏi Độ khó: Dễ Sắp xếp Xâu Nhập môn

Đề bài

Bạn sẽ nhận được ba số nguyên $A$, $B$ và $C$. Các con số được đưa ra không được sắp xếp theo một thứ tự chính xác, nhưng chúng ta biết rằng $A$ nhỏ hơn $B$ và $B$ nhỏ hơn $C$. Yêu cầu sắp xếp lại chúng theo thứ tự nhất định.

Input:

• Dòng đầu tiên chứa ba số nguyên dương $A$, $B$ và $C$, không nhất thiết phải theo thứ tự đó. Tất cả ba số sẽ nhỏ hơn hoặc bằng $100$.
• Dòng thứ hai chứa ba chữ cái in hoa 'A', 'B' và 'C' (không có dấu cách giữa chúng) đại diện cho thứ tự mong muốn.

Output:

• $A$, $B$, $C$ theo thứ tự mong muốn trên một dòng duy nhất, cách nhau bởi khoảng trắng.

Ví dụ 1 – input

1 5 3
ABC

Ví dụ 1 – output

1 3 5

Ví dụ 2 – input

6 4 2
CAB

Ví dụ 2 – output

6 2 4

Lời mở đầu

Cuối tuần có một bạn học viên nhắn hỏi mình bài này: bạn ấy nghĩ một hồi mà vẫn chưa ra. Bạn đã có ý tưởng là tìm số lớn nhất, nhỏ nhất và số ở giữa trong 3 số, gán chúng tương ứng với A, B, C rồi in ra theo định dạng cho trước – nhưng lại vấp ở đúng chỗ "làm sao gán số vào kí tự", code thì cứ sai rồi lại lỗi tung lên 😅. Bài tuy nhập môn nhưng có một ý rất hay mà mình muốn các bạn mới học nắm thật chắc, nên mình viết lại thành bài giải chi tiết luôn nha 😇.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

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

Mình giải thích ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Đề nói ba số $A \lt B \lt C$ nhưng lại đưa vào lộn xộn. Vậy sau khi xếp tăng dần thì số nhỏ nhất chính là $A$, số ở giữa là $B$, số lớn nhất là $C$.

• Ví dụ 1: ba số 1 5 3 ⇒ $A = 1$, $B = 3$, $C = 5$. Chuỗi ABC nghĩa là in $A$, rồi $B$, rồi $C$ ⇒ 1 3 5.
• Ví dụ 2: ba số 6 4 2 ⇒ $A = 2$, $B = 4$, $C = 6$. Chuỗi CAB nghĩa là in $C$, rồi $A$, rồi $B$ ⇒ 6 2 4.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1min / mid / max + if-else từng ký tựCách 2Sắp xếp mảng + chỉ số x − 'A' (cách của mình)

Cách 1Đi tiếp hướng của bạn học viên: min, mid, max – O(1)

Đầu tiên mình đi theo đúng hướng bạn ấy đang làm để gỡ chỗ "kẹt". Giả sử 3 số cho là 6 4 2: em tìm ra $max = 6$, $min = 2$, $mid = 4$. Theo đề thì max hiểu là $C$, min hiểu là $A$, còn mid hiểu là $B$. Cái em đang kẹt là: làm sao để khi gặp ví dụ chuỗi "BCA" thì chương trình hiểu là phải in ra: mid, max, min?

Thật ra chỗ này đơn giản lắm: không cần "gán số vào ký tự" gì cả, chỉ cần duyệt từng ký tự của chuỗi và xét điều kiện cho nó thôi. Ví dụ chuỗi s = "BCA" thì chỉ số i chạy từ 0 đến 2:

• Xét s[0] là 'B' ⇒ thoả nhánh 'B' ⇒ in ra mid.
• Xét s[1] là 'C' ⇒ rơi vào nhánh else ⇒ in ra max.
• Xét s[2] là 'A' ⇒ thoả nhánh 'A' ⇒ in ra min.

Ý chính

for(int i = 0; i < 3; i++) xét từng s[i]:
if(s[i] == 'A') cout << min;
else if(s[i] == 'B') cout << mid;
else cout << max;
Vấn đề đơn giản đến mức không tưởng ha :))

Tìm mid thế nào cho gọn?

Có min và max rồi thì số ở giữa chính là tổng ba số trừ đi min và max: mid = a + b + c - mn - mx, khỏi phải if-else lằng nhằng. Lưu ý trong C++ mình đặt tên biến là mn, mx chứ không đặt là min, max, vì đặt trùng tên sẽ "che" mất hàm min(), max() của thư viện, gọi hàm là báo lỗi ngay.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    int a, b, c;
    string s;
    cin >> a >> b >> c >> s;
    int mn = min(a, min(b, c));
    int mx = max(a, max(b, c));
    int mid = a + b + c - mn - mx;
    for(int i = 0; i < 3; i++)
    {
        if(s[i] == 'A')
            cout << mn << " ";
        else if(s[i] == 'B')
            cout << mid << " ";
        else
            cout << mx << " ";
    }
    return 0;
}

a, b, c = map(int, input().split())
s = input().strip()
mn = min(a, b, c)
mx = max(a, b, c)
mid = a + b + c - mn - mx
for i in range(3):
    if s[i] == 'A':
        print(mn, end=' ')
    elif s[i] == 'B':
        print(mid, end=' ')
    else:
        print(mx, end=' ')

C++▶ Chạy tay từng dòng codeCách 1: tìm mn, mx, mid rồi duyệt chuỗi, mỗi ký tự in số tương ứng bằng if-else.

Dữ liệu vào (stdin) – sửa thoải mái6 4 2 CAB

Dữ liệu mẫu:

1#include <iostream>

2#include <string>

3#include <algorithm>

4using namespace std;

5

6int main()

7{

8 int a, b, c;

9 string s;

10 cin >> a >> b >> c >> s;

11 int mn = min(a, min(b, c));

12 int mx = max(a, max(b, c));

13 int mid = a + b + c - mn - mx;

14 for(int i = 0; i < 3; i++)

15 {

16 if(s[i] == 'A')

17 cout << mn << " ";

18 else if(s[i] == 'B')

19 cout << mid << " ";

20 else

21 cout << mx << " ";

22 }

23 return 0;

24}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ vài biến và chuỗi 3 ký tự ⇒ $O(1)$.
• Thời gian: vài phép so sánh và một vòng lặp đúng 3 lần ⇒ $O(1)$.

Không gian$O(1)$

Thời gian$O(1)$

Chạy đúng nhưng khó mở rộng

Thực ra ngay từ đầu, khi chọn hướng tạo 3 biến max, min, mid thì đó đã không phải là hướng tốt nhất rồi. Giờ các bạn tưởng tượng bài này không chỉ có 3 số mà có đến 5 số chẳng hạn, và chuỗi có thể xuất hiện thêm D, E… à ha, như vậy cách này sẽ khó rồi :)) vì không còn là tìm max, min, mid nữa ^^.

Cách 2Sắp xếp mảng + truy xuất chỉ số x − 'A' – O(1)

Còn nếu là mình gặp bài ở trên thì mình sẽ làm theo cách này, ngắn gọn hơn nhiều:

1. Đọc 3 số vào mảng a[3], rồi gọi hàm sort cho nó sắp tăng dần. Lúc này a[0] là $A$, a[1] là $B$, a[2] là $C$.
2. Đọc lần lượt từng ký tự x của chuỗi. Ký tự 'A' thì lấy a[0], 'B' lấy a[1], 'C' lấy a[2] – mà chỉ số này tính ngay được bằng x - 'A'.

Vì sao x − 'A' lại ra chỉ số?

Trong C/C++ ký tự thực chất được lưu bằng mã ASCII là số nguyên: 'A' = 65, 'B' = 66, 'C' = 67. Nên 'A' - 'A' = 0, 'B' - 'A' = 1, 'C' - 'A' = 2 – đúng bằng vị trí của số tương ứng trong mảng đã sắp xếp. Đây chính là lời giải cho câu hỏi "làm sao gán số vào kí tự" của bạn học viên: ta không gán, mà biến ký tự thành chỉ số mảng.

Cái hay của code này là khả năng mở rộng thoải mái. Nếu bài có 5 số và chuỗi có thêm D, E thì chỉ cần sửa cho mảng 5 phần tử, cho vòng lặp chạy đủ 5 lần, mỗi lần đọc 1 số vào mảng, sau đó gọi hàm sort cho nó sắp tăng dần. Rồi cứ thế đọc chuỗi vào, nếu là ký tự 'B' thì truy xuất đến index 1 lấy giá trị ra, nếu ký tự 'D' thì truy xuất đến index 3 lấy giá trị ra, cứ thế…

Minh hoạ

Em nhập 3 số và chuỗi thứ tự rồi bấm Tiếp để xem mảng được sắp xếp và từng ký tự "trỏ" vào ô nào:

Các số Chuỗi

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này (đây là code mình gửi bạn học viên, các bạn chạy thử nhé):

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a, a + 3);

    for (int i = 0; i < 3; ++i)
    {
        char x;
        cin >> x;
        cout << a[x - 'A'] << " ";
    }

    return 0;
}

a = list(map(int, input().split()))
a.sort()
s = input().strip()
for x in s:
    print(a[ord(x) - ord('A')], end=' ')

C++▶ Chạy tay từng dòng codeCách 2: sort mảng 3 số, mỗi ký tự x in a[x - 'A'].

Dữ liệu vào (stdin) – sửa thoải mái6 4 2 CAB

Dữ liệu mẫu:

1#include <iostream>

2#include <algorithm>

3using namespace std;

4

5int main()

6{

7 int a[3];

8 cin >> a[0] >> a[1] >> a[2];

9 sort(a, a + 3);

10

11 for (int i = 0; i < 3; ++i)

12 {

13 char x;

14 cin >> x;

15 cout << a[x - 'A'] << " ";

16 }

17

18 return 0;

19}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng 3 phần tử ⇒ $O(1)$.
• Thời gian: sắp xếp 3 phần tử và một vòng lặp 3 lần ⇒ $O(1)$. Tổng quát với $n$ số thì là $O(n \log n)$ cho bước sắp xếp và $O(n)$ cho bước in, vẫn rất nhẹ nhàng.

Không gian$O(1)$

Thời gian$O(1)$

Bài học rút ra

Khi thấy dữ liệu có dạng "ký tự liên tiếp ↔ vị trí liên tiếp" (A, B, C, … hoặc a, b, c, …), hãy nghĩ ngay đến mẹo x - 'A' (hoặc x - 'a') để đổi ký tự thành chỉ số mảng. Mẹo này các bạn sẽ còn gặp lại rất nhiều ở các bài mảng đánh dấu, đếm tần suất chữ cái nha.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 2 test của đề và 400 bộ test ngẫu nhiên (3 số khác nhau trong đoạn 1..100, chuỗi là hoán vị ngẫu nhiên của ABC), so với code vét cạn thử mọi cách gán A < B < C – khớp hết.

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 😇