Hiểu bài toán

Bài toán yêu cầu xây dựng một máy tính đơn giản xử lý biểu thức với 2 số nguyên A và B, và một phép toán được biểu diễn dưới dạng chuỗi. Các phép toán cơ bản: +, -, *, /, ^. Hai phép toán đặc biệt là '!' (giai thừa) và 'sqrt' (căn bậc hai) chỉ áp dụng cho số A và có thể kết hợp với phép toán khác (ví dụ: 'a! * b' hoặc 'sqrt a + b'). Đầu vào gồm 3 dòng: số A, chuỗi phép toán, số B. Đầu ra là kết quả của phép tính. Chú ý: phép chia là phép chia nguyên (floor division), sqrt làm tròn xuống, và pow(a, b) cần in ra số nguyên.

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

Cách Phân tích chuỗi

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

long long f(int n) {
    long long r = 1;
    for (int i = 2; i <= n; ++i) r *= i;
    return r;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    long long a, b;
    string op;
    cin >> a >> op >> b;

    if (op[0] == '!') {
        a = f(a);
    } else if (op.substr(0, 4) == "sqrt") {
        a = (int)sqrt(a);
    }

    char final_op = op.back();
    if (final_op == '+') cout << a + b;
    else if (final_op == '-') cout << a - b;
    else if (final_op == '*') cout << a * b;
    else if (final_op == '/') cout << a / b;
    else if (final_op == '^') cout << (long long)pow(a, b);

    return 0;
}

• Time Complexity: O(1) hoặc O(A) (phụ thuộc vào phép tính giai thừa, nhưng A nhỏ <= 10^5)
• Space Complexity: O(1)

Cách tiếp cận này dựa vào quan sát rằng chuỗi phép toán 'op' có độ dài giới hạn. Nếu bắt đầu bằng '!' hoặc 'sqrt', ta thực hiện phép toán đơn vị trước lên A. Sau đó, ký tự cuối cùng của chuỗi 'op' luôn là phép toán nhị phân (+, -, *, /, ^). Ta chỉ cần trích xuất ký tự cuối cùng này để thực hiện phép tính giữa A (đã được xử lý trước) và B. Ví dụ: 'sqrt' -> độ dài 4, ký tự cuối là 't' (thật ra là ký tự cuối của chuỗi gốc, ví dụ 'sqrt+' thì cuối là '+'). Các tác vụ giai thừa hoặc căn bậc hai được thực hiện trước, sau đó thực hiện phép toán nhị phân.

Cách Xử lý logic dựa trên độ dài chuỗi

#include<bits/stdc++.h>
using namespace std;
long long giaithua(long long a){
    vector<long long> dp(a+1);
    dp[0]=1;
    dp[1]=1;
    for(long long i=2;i<=a;i++){
        dp[i]=i*dp[i-1];
    }
    return dp[a];
}
void tinhtoan(char c, long long a, long long b){
    if(c=='+') cout << a+b;
    else if(c=='-') cout << a-b;
    else if(c=='^') cout << pow(a,b);
    else if(c=='/') cout << a/b;
    else if(c=='*') cout << a*b;
}
int main(){
    long long a,b;
    string s;
    cin >> a >> s >> b;
    if(s.size()>1){
        if(s.size()!=5){
            a=giaithua(a);
            tinhtoan(s[1],a,b);
        } else {
            a=sqrt(a);
            tinhtoan(s[4],a,b);
        }
    }
    tinhtoan(s[0],a,b);
    return 0;
}

• Time Complexity: O(A) (do giai thừa) hoặc O(1)
• Space Complexity: O(1)

Phương pháp này kiểm tra độ dài của chuỗi phép toán để xác định loại phép toán.

• Nếu độ dài là 1: Chuỗi chỉ chứa toán tử (+, -, *, /, ^).
• Nếu độ dài > 1: Có thể là '!+' hoặc 'sqrt+'.
  • Code kiểm tra s.size() != 5. Nếu đúng (ví dụ độ dài 2), thực hiện giai thừa A và lấy ký tự tại s[1] làm toán tử.
  • Nếu sai (ví dụ độ dài 5), thực hiện căn bậc hai A và lấy ký tự tại s[4] làm toán tử. Cách này phân loại dựa trên giả định về độ dài chuỗi đầu vào.

Cách Xử lý chuỗi tổng quát (String Parsing)

#include<bits/stdc++.h>
using namespace std;
long long gt(long long n)
{
    long long t=n;
    for (int i=2;i<n;i++)
    {
        t*=i;
    }
    return t;
} 
long long a,b;
string c; 
int main()
{
    cin>>a>>c>>b;
    if (c[0]=='s')
    {
        a=sqrt(a);
        c.erase(0,4);
    }
    if (c[0]=='!')
    {
        a=gt(a);
        c.erase(0,1);
    }
    if (c=="+") cout<<a+b;
    if (c=="-") cout<<a-b;
    if (c=="*") cout<<a*b;
    if (c=="/") cout<<a/b;
    if (c=="^") cout<<fixed<<setprecision(0)<<pow(a,b);
}

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

Đây là cách tiếp cận linh hoạt và đúng đắn nhất.

1. Đọc A, chuỗi C, B.
2. Kiểm tra ký tự đầu tiên của C:
   • Nếu là 's' (sqrt): Tính a = sqrt(a), sau đó xóa 4 ký tự đầu tiên khỏi C (c.erase(0, 4)). Bây giờ C chỉ còn lại toán tử nhị phân.
   • Nếu là '!' (factorial): Tính a = gt(a), sau đó xóa 1 ký tự đầu tiên (c.erase(0, 1)).
3. Sau bước này, C chỉ chứa toán tử nhị phân (+, -, *, /, ^).
4. Thực hiện phép tính tương ứng giữa A và B. Cách này xử lý được các trường hợp một cách tuần tự và chính xác mà không cần giả định độ dài.

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

Bài học kinh nghiệm

• Luôn ưu tiên xử lý các phép toán đơn vị ('!', 'sqrt') trước khi thực hiện phép toán nhị phân.
• Ký tự cuối cùng của chuỗi phép toán sau khi loại bỏ phần đơn vị chính là toán tử nhị phân.
• Dữ liệu đầu vào A, B nhỏ (<= 10^5) nhưng kết quả tính toán (n giai thừa, a^b) có thể rất lớn, bắt buộc phải sử dụng long long (64-bit integer).
• Phép chia là chia nguyên, phép sqrt là làm tròn xuống.

Lỗi thường gặp

• Tràn số (Overflow): Tính 100000! hoặc 100000^100000 chắc chắn tràn long long. Tuy nhiên, đề bài và test data thường chỉ yêu cầu tính toán trong phạm vi vừa phải hoặc chỉ quan tâm đến logic đúng.
• Xử lý input: Cần đọc đúng thứ tự A, string op, B.
• Lỗi cú pháp truy cập string: op.back() hoặc op[0] cần kiểm tra độ dài string trước nếu không chắc chắn.