Hướng dẫn giải của [VT Thiếu nhi] BÀI 17: MOVE
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Ô ~(i, j)~ có giá trị ~i \cdot j~. Từ ~(1,1)~ mỗi bước đi xuống hoặc sang phải, nên đến ô ~(i, j)~ cần ~(i-1) + (j-1)~ bước. Vậy cần tìm cặp ~(i, j)~ với ~i \cdot j = N~ sao cho ~i + j~ nhỏ nhất.
Sub 1: Vét cạn — ~O(N)~, dùng khi ~N \le 10^6~
Duyệt ~i~ từ ~1~ đến ~N~; nếu ~i~ là ước của ~N~ thì ~j = N / i~ và cập nhật ~i + j - 2~. Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Chỉ duyệt đến căn bậc hai — ~O(\sqrt{N})~
Chỉ cần xét ước ~i \le \sqrt{N}~, vì cặp ước ~(i, N/i)~ đối xứng. Với ~N \le 10^{12}~ thì ~\sqrt{N} \le 10^6~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc ~N~. Nếu ~N \le 10^6~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long N;
// Mo ta: o (i,j) co gia tri i*j. Di tu (1,1) xuong (i+1,j) hoac sang (i,j+1).
// O (i,j) co gia tri N thi can (i-1)+(j-1) buoc. Ta tim cap (i,j) co i*j = N
// va i+j nho nhat.
// Sub 1: vet can. Duyet i tu 1 den N, neu i chia het N thi j = N/i. O(N).
// Dung khi N <= 10^6.
void sub1() {
long long best = LLONG_MAX;
for (long long i = 1; i <= N; i++)
if (N % i == 0) {
long long j = N / i;
best = min(best, i + j - 2);
}
cout << best << "\n";
}
// Sub 2: cac uoc i <= sqrt(N) co cap uoc j = N/i >= i. Tong i + j nho nhat khi i gan sqrt(N) nhat.
// Chi can duyet i den sqrt(N) <= 10^6. O(sqrt(N)).
void sub2() {
long long best = LLONG_MAX;
for (long long i = 1; i * i <= N; i++)
if (N % i == 0) {
long long j = N / i;
best = min(best, i + j - 2);
}
cout << best << "\n";
}
int main() {
freopen("MOVE.INP", "r", stdin);
freopen("MOVE.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
if (N <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận