help bài #229. ROBOT - Di chuyển Robot

Thuật toán trong đoạn mã này thực hiện việc tìm kiếm các cặp ước số của một số nguyên n và tính giá trị tối thiểu của một công thức cụ thể. Cụ thể, mục tiêu là tìm ra cặp ước số i và j sao cho giá trị step = (i - 1) + (j - 1) là nhỏ nhất, với i và j là các ước số của n, và i * j = n.

Giải thích thuật toán:

1. Khởi tạo biến mS:

   • Biến mS được khởi tạo bằng LLONG_MAX, một giá trị rất lớn, dùng để tìm giá trị nhỏ nhất trong quá trình tính toán.

2. Duyệt qua tất cả các ước số của n:

   • Thuật toán lặp qua tất cả các số từ 1 đến sqrt(n) (tức là chỉ duyệt qua các ước số nhỏ hơn hoặc bằng căn bậc 2 của n).
   • Nếu i là một ước của n (n % i == 0), thì:
     • Tính ước số j thứ hai của n, với j = n / i.
     • Tính giá trị step = (i - 1) + (j - 1). Đây là công thức để tính số bước cần thiết (hoặc chi phí) khi xử lý cặp ước số i và j.

3. Tính giá trị nhỏ nhất của step:

   • Sau mỗi vòng lặp, giá trị của step được so sánh với mS. Nếu step nhỏ hơn mS, cập nhật giá trị mS thành step.

4. Kết quả:

   • Sau khi duyệt qua tất cả các ước số của n, giá trị tối thiểu của step được lưu trong biến mS và được trả về.

5. In kết quả cuối cùng:

   • Kết quả là giá trị nhỏ nhất của step sau khi tính toán xong tất cả các cặp ước số của n.

Thuật toán:

1. Nhập giá trị n.
2. Duyệt qua các ước số của n từ 1 đến sqrt(n).
3. Với mỗi ước số i, tính j = n / i và step = (i - 1) + (j - 1).
4. Tìm giá trị nhỏ nhất của step.
5. In kết quả.

Ví dụ:

Giả sử n = 12. Các ước số của 12 là: 1, 2, 3, 4, 6, 12.

• Khi i = 1, j = 12, step = (1-1) + (12-1) = 11.
• Khi i = 2, j = 6, step = (2-1) + (6-1) = 6.
• Khi i = 3, j = 4, step = (3-1) + (4-1) = 5.

Giá trị nhỏ nhất của step là 5.

Độ phức tạp:

• Thuật toán duyệt qua tất cả các ước số của n, do đó độ phức tạp của thuật toán là O(sqrt(n)).

Code mẫu #include <bits/stdc++.h>

using namespace std;

#define ll long long

ll Mstep(ll n) {

ll mS = LLONG_MAX;

for(ll i = 1 ; i <= sqrt(n) ; ++i) {

    if(n % i == 0) {
        ll j = n / i * 1ll;
        ll step = 1ll * (i - 1) + 1ll * (j - 1);
        mS = min(mS , step) * 1ll;

    }
}

return mS;

}

main() { ll n; cin >> n; cout << 1ll * Mstep(n) << '\n'; }