Hiểu bài toán

Bài toán yêu cầu tìm số lớn nhất có thể tạo thành bằng cách nối ba chữ số a, b, c (cho trước) theo một chu kỳ nhất định trên tam giác. Cụ thể, xuất phát từ một đỉnh bất kỳ, ta đi theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ để tạo thành một số 3 chữ số. Về cơ bản, điều này tương đương với việc tạo ra tất cả các số 3 chữ số từ các cách sắp xếp khác nhau của bộ ba chữ số a, b, c, và tìm số lớn nhất trong đó. Do có 3 chữ số, có tất cả $3! = 6$ cách sắp xếp.

Các cách tiếp cận

Cách Brute Force (Liệt kê tất cả permutations)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int d1, d2, d3;
    if(!(cin >> d1 >> d2 >> d3)) return 0;

    vector<int> n;
    n.push_back(100*d1 + 10*d2 + d3);
    n.push_back(100*d1 + 10*d3 + d2);

    n.push_back(100*d2 + 10*d3 + d1);
    n.push_back(100*d2 + 10*d1 + d3);

    n.push_back(100*d3 + 10*d1 + d2);
    n.push_back(100*d3 + 10*d2 + d1);

    cout << *max_element(n.begin(), n.end()) << "\n";
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Phương pháp này đơn giản nhất. Ta nhập ba số d1, d2, d3. Sau đó, ta tính toán và lưu trữ tất cả 6 số có thể tạo thành bằng cách hoán vị thứ tự của chúng vào một vector. Cuối cùng, ta sử dụng hàm max_element để tìm giá trị lớn nhất trong vector đó và in ra. Vì số lượng phần tử là cố định (6), độ phức tạp thời gian và bộ nhớ là hằng số O(1).

Cách Logic Sắp Xếp (Sorting Logic)

#include <iostream>
using namespace std;
int main() 
{
    int a,b,c;
    cin>>a>>b>>c;
    int sln=max(a,max(b,c));
    int snn=min(a,min(b,c));
    int sg;
    if(sln==a && snn==b || sln==b && snn==c) sg=c;
    if(sln==a && snn==c || sln==c && snn==a) sg=b;
    if(sln==b && snn==c || sln==c && snn==b) sg=a;
    cout<<sln<<sg<<snn;
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Để tạo ra số lớn nhất, ta cần sắp xếp các chữ số theo thứ tự giảm dần từ trái sang phải. Do đó, ta chỉ cần tìm số lớn nhất (sln), số nhỏ nhất (snn) và số còn lại là số giữa (sg). Sau đó in ra kết quả theo thứ tự sln, sg, snn. Code sử dụng các câu lệnh điều kiện phức tạp để tìm số ở giữa, nhưng về bản chất chỉ là cách tìm số còn lại sau khi đã xác định max và min.

Cách Sử dụng Permutation với Sort

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    vector<int> v = {a, b, c};
    int best = 0;
    // xét cả 6 cách xếp 3 chữ số thành một số 3-chữ-số
    sort(v.begin(), v.end());
    do {
        int num = v[0] * 100 + v[1] * 10 + v[2];
        best = max(best, num);
    } while (next_permutation(v.begin(), v.end()));
    cout << best;
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Cách tiếp cận này sử dụng thư viện chuẩn C++. Ta lưu ba chữ số vào một vector, sắp xếp chúng tăng dần. Sau đó, ta sử dụng vòng lặp do-while với hàm next_permutation để duyệt qua tất cả các cách hoán vị của vector. Với mỗi cách hoán vị, ta tính giá trị số 3 chữ số tương ứng và cập nhật giá trị lớn nhất. Hàm next_permutation trả về false khi không còn cách hoán vị mới nào hợp lệ, kết thúc vòng lặp.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán quy về tìm số lớn nhất tạo thành từ 3 chữ số cho trước.
• Để số lớn nhất, các chữ số cần nằm ở các hàng lớn nhất (trăm, chục, đơn vị) theo thứ tự giảm dần.
• Vì chỉ có 3 số, số lượng cách sắp xếp là rất ít (6 cách), nên các thuật toán phức tạp đều chạy rất nhanh.

Lỗi thường gặp

• Quên xử lý các trường hợp các số giống nhau (ví dụ 1 1 1).
• Sai logic khi tìm số ở giữa trong phương pháp Logic Sắp Xếp.
• In sai thứ tự các số (ví dụ in số lớn nhất ở hàng chục thay vì hàng trăm).