Hiểu bài toán

Bài toán yêu cầu tìm tổng số điểm lớn nhất có thể đạt được sau 2 lượt chọn số, bắt đầu từ hai số nguyên dương ban đầu A và B. Ở mỗi lượt, người chơi chọn một trong hai số hiện có và cộng giá trị đó vào điểm, sau đó giảm giá trị của số đó đi 1. Chúng ta cần tính tổng điểm lớn nhất sau 2 lượt.

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

Cách Phân tích từng trường hợp (Case Analysis)

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("game.inp","r",stdin);
    freopen("game.out","w",stdout);
    int a,b;
    cin>>a>>b;
    if(a==b) cout<<2*a;
    else if(a>b) cout<<max(a,b) + max(a-1,b);
    else cout<<max(a,b) + max(a,b-1);
    return 0;
}

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

Hàm max(a, b) trả về số lớn hơn trong A và B. Nếu A == B, ta chọn A và B (hoặc B và A), được 2*A. Nếu A > B, ta chọn A trước (được A), sau đó so sánh A-1 và B, chọn số lớn hơn. Ngược lại làm tương tự. Ví dụ: A=5, B=3. Chọn 5 được 5 điểm. remaining: 4, 3. Chọn 4 được 4 điểm. Tổng 9. Công thức max(a,b) + max(a-1, b) (khi A>B) che phủ đúng logic này.

Cách Mô phỏng theo vòng lặp

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ifstream fi("game.inp");
    ofstream fo("game.out"); 
    int a, b; fi >> a >> b;
    int c = 0; 
    for (int i = 0; i < 2; i++){
        c += max(a, b);
        if (a==max(a,b)) a--;
        else b--; 
    } 
    fo << c; 
    fi.close(); fo.close(); 
    return 0; 
}

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

Giải pháp này mô phỏng chính xác quá trình chơi. Biến c lưu tổng điểm. Vòng lặp chạy 2 lần (tương ứng 2 lượt). Trong mỗi lượt, cộng giá trị lớn nhất hiện tại vào c. Sau đó, giảm giá trị của biến chứa số lớn nhất đó đi 1. Đây là cách tiếp cận trực quan và dễ hiểu nhất.

Cách Sử dụng mảng và sắp xếp

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

int main() {
    ifstream fin("game.inp");
    ofstream fout("game.out");

    int MA, MB;
    fin >> MA >> MB;

    vector<int> points = {MA, MA - 1, MB, MB - 1};
    sort(points.rbegin(), points.rend());

    int max_score = points[0] + points[1];

    fout << max_score << "\n";

    fin.close();
    fout.close();

    return 0;
}

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

Giả sử ta muốn chọn hai số để được tổng lớn nhất. Các số có thể chọn chỉ nằm trong tập hợp {A, A-1, B, B-1}. Ta tạo một mảng chứa 4 số này, sắp xếp giảm dần và lấy hai số đầu tiên cộng lại. Đây là cách tổng quát hóa của bài toán.

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

Bài học kinh nghiệm

• Bài toán chỉ xoay quanh việc chọn hai giá trị từ tập hợp {A, A-1, B, B-1} sao cho tổng lớn nhất.
• Luôn chọn số lớn nhất hiện có trong mỗi lượt là chiến lược tối ưu.

Lỗi thường gặp

• Quên kiểm tra điều kiện A == B, dẫn đến việc áp dụng công thức sai (ví dụ: max(A-1, B) có thể sai nếu A=B).
• Lỗi biên (off-by-one) khi tính A-1 hoặc B-1 nếu biến giảm giá trị trước khi cộng điểm.