Hiểu bài toán

Bài toán yêu cầu tìm số bước di chuyển ít nhất của một con robot trên một bảng vô hạn để đến được một ô có giá trị là n. Robot bắt đầu tại ô (1, 1). Tại mỗi ô (i, j), giá trị ghi trên ô đó là i * j. Robot chỉ có thể di chuyển sang các ô kề cạnh (trên, dưới, trái, phải). Số bước di chuyển giữa hai ô (x1, y1) và (x2, y2) là khoảng cách Manhattan: |x1 - x2| + |y1 - y2|. Vì robot bắt đầu tại (1, 1), số bước để đến ô (i, j) là (i - 1) + (j - 1) = i + j - 2. Ta cần tìm cặp số nguyên dương (i, j) sao cho i * j = n và i + j - 2 là nhỏ nhất.

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

Cách Brute Force (Duyệt các thừa số)

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

int main() {
    long long n;
    cin >> n;
    long long ans = LLONG_MAX;
    // Duyệt qua tất cả các số i từ 1 đến căn bậc hai của n
    for (long long i = 1; i * i <= n; i++) {
        // Nếu i là thừa số của n
        if (n % i == 0) {
            long long j = n / i;
            // Tính số bước di chuyển
            ans = min(ans, i + j - 2);
        }
    }
    cout << ans << endl;
    return 0;
}

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

Để đến được ô có giá trị n, tọa độ của nó phải là một cặp (i, j) sao cho i * j = n. Số bước di chuyển từ (1, 1) đến (i, j) là i + j - 2. Để tìm số bước ít nhất, ta cần tìm cặp (i, j) sao cho i + j là nhỏ nhất trong số tất cả các cặp (i, j) mà i * j = n. Hàm i + j được tối thiểu hóa khi i và j gần nhau nhất, tức là i và j là các thừa số của n và gần căn bậc hai của n nhất. Do đó, ta chỉ cần duyệt i từ 1 đến sqrt(n). Với mỗi i là thừa số của n, ta tính j = n / i và cập nhật kết quả. Độ phức tạp thời gian là O(sqrt(n)), đủ nhanh cho n lên tới 10^12.

Cách BFS / Simulation (Thực tế)

// Lời giải này chỉ mang tính minh họa lý do tại sao BFS không khả thi.
// Thực tế không có submitted solution dùng BFS cho n lớn.
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    // BFS không khả thi do bảng vô hạn và n quá lớn.
    // Chỉ có thể giải thích bằng toán học.
    // Công thức: Min steps = min(i + j - 2) for i * j = n.
    // Thuật toán tối ưu là duyệt các thừa số.
    return 0;
}

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

Một cách tiếp cận trực quan là mô phỏng chuyển động của robot bằng thuật toán BFS (Tìm đường đi ngắn nhất trên lưới). Tuy nhiên, bảng ô vuông là vô hạn và giá trị n có thể lên tới 10^12. Việc lưu trữ các trạng thái (tọa độ) là không thể. Tuy nhiên, nếu ta phân tích bài toán, ta thấy rằng để đến ô có giá trị n, tọa độ (i, j) phải thỏa mãn i * j = n. Số bước di chuyển là i + j - 2. Vấn đề trở thành bài toán tìm thừa số tối ưu.

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

Bài học kinh nghiệm

• Bài toán có thể quy về bài toán tìm cặp thừa số (i, j) của n sao cho i + j là nhỏ nhất.
• Số bước di chuyển từ (1, 1) đến (i, j) là công thức Manhattan: i + j - 2.
• Giá trị i + j được tối thiểu hóa khi i và j gần nhau nhất, tức là i và j xung quanh căn bậc hai của n.

Lỗi thường gặp

• Quên trừ 2 trong công thức tính số bước (i + j - 2).
• Sử dụng kiểu dữ liệu int导致 overflow khi n = 10^12. Cần dùng long long.
• Duyệt quá nhiều hoặc sai điều kiện dừng vòng lặp (ví dụ: i <= n thay vì i * i <= n).