Hiểu bài toán

Bài toán yêu cầu tìm số trang ít nhất cần lật để đến được trang p trong một cuốn sách n trang. Cuốn sách có thể được mở từ đầu (trang 1) hoặc từ cuối (trang n). Khi mở từ đầu, trang 1 luôn nằm ở bên phải. Khi mở từ cuối, trang n có thể nằm ở bên phải hoặc bên trái. Số trang lật được tính từ vị trí bắt đầu (mở từ đầu hoặc mở từ cuối) đến trang p.

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

Cách Công thức trực tiếp

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        long long n, p;
        cin >> n >> p;

        long long front = p / 2;
        long long back = n / 2 - p / 2;

        cout << min(front, back) << "\n";
    }

    return 0;
}

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

Hãy chia cuốn sách thành các cặp trang (2k-1, 2k). Khi mở từ đầu, để đến trang p, ta cần lật ⌊p/2⌋ trang (mỗi lần lật đi qua một cặp trang). Khi mở từ cuối, ta cần lật ⌊n/2⌋ - ⌊p/2⌋ trang. Số trang lật ít nhất là min(⌊p/2⌋, ⌊n/2⌋ - ⌊p/2⌋).

Cách Phân tích chi tiết các trường hợp

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t, n, p;
    cin >> t;
    while(t--) {
        cin >> n >> p;
        int a = p / 2;
        int b = n / 2 - p / 2;
        cout << min(a, b) << "\n";
    }
    return 0;
}

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

Cách tiếp cận này cũng dựa trên công thức trực tiếp nhưng có thể được hiểu như sau: Số trang lật từ đầu là ⌊p/2⌋. Số trang lật từ cuối là tổng số cặp trang trừ đi số cặp trang từ đầu đến p, tức là ⌊n/2⌋ - ⌊p/2⌋. So sánh hai giá trị này và lấy giá trị nhỏ hơn.

Cách Xử lý trực tiếp theo logic

#include <bits/stdc++.h>
using namespace std;
int t,n,p;
int main() 
{
    cin >> t;
    while (t--) 
    {
        cin >> n >> p;
        int from_front = p / 2;
        int from_back = n / 2 - p / 2;
        cout << min(from_front, from_back) << endl;
    }
    return 0;
}

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

Giải pháp này là một cách viết khác của cách tiếp cận đầu tiên, nhấn mạnh vào việc tính toán số trang lật từ cả hai phía (từ đầu và từ cuối) rồi chọn giá trị nhỏ nhất. Logic tính toán hoàn toàn tương tự: từ đầu là ⌊p/2⌋, từ cuối là ⌊n/2⌋ - ⌊p/2⌋.

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

Bài học kinh nghiệm

• Cuốn sách có thể được chia thành các cặp trang (trang lẻ và trang chẵn liên tiếp). Số trang lật tương ứng với số cặp trang đã đi qua.
• Khi mở từ đầu, để đến trang p, ta đi qua ⌊p/2⌋ cặp trang.
• Khi mở từ cuối, để đến trang p, ta đi qua ⌊n/2⌋ - ⌊p/2⌋ cặp trang.
• Kết quả luôn là giá trị nhỏ hơn của hai trường hợp trên.

Lỗi thường gặp

• Quên chia số trang cho 2 khi tính toán (sử dụng phép chia nguyên ⌊/⌋).
• Sử dụng biến có kiểu dữ liệu quá nhỏ (ví dụ: int thay vì long long) cho n và p, nhưng trong bài này n ≤ 10^5 nên int là đủ.
• Không xử lý đúng số trang lật khi p ở vị trí đầu hoặc cuối cuốn sách (ví dụ: p=1 hoặc p=n). May mắn là công thức vẫn đúng cho các trường hợp này.