Hướng dẫn giải của [200 đề thầy Đức] Bài 117: Những viên đá cuội
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
Hình chữ nhật có diện tích đúng ~N~ ô, cần chọn kích thước ~a \times b~ với ~a \cdot b = N~ sao cho chu vi ~2(a + b)~ nhỏ nhất.
Sub 1: Vét cạn mọi ước — ~O(N)~
Thử mọi ~a~ từ 1 đến ~N~, nếu ~a~ chia hết ~N~ thì ~b = N / a~ và cập nhật chu vi nhỏ nhất. Đạt 10/20 test, các test còn lại quá giờ (N tới 10^9 nên ~O(N)~ không kịp).
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// Vét cạn: thử mọi chiều dài a, nếu a là ước của n thì b = n / a
long long best = LLONG_MAX;
for (long long a = 1; a <= n; a++) {
if (n % a == 0) {
long long b = n / a;
best = min(best, 2 * (a + b));
}
}
cout << best << "\n";
return 0;
}
Sub 2: Chỉ thử ~a~ đến căn bậc hai của N — ~O(\sqrt{N})~
Với ~a \cdot b = N~, tổng ~a + b~ nhỏ nhất khi hai cạnh gần nhau nhất. Vì ta xét ~a \le b~ nên chỉ cần thử ~a~ đến ~\sqrt{N}~ (dùng ~a \cdot a \le N~ để tránh tính căn). Lưu ý dùng long long vì ~N \le 10^9~ và chu vi có thể lớn. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
// Với a*b = n, a + b nhỏ nhất khi a, b gần nhau nhất.
// Chỉ cần thử a từ 1 đến căn(n), mỗi ước a cho b = n / a.
long long best = LLONG_MAX;
for (long long a = 1; a * a <= n; a++) {
if (n % a == 0) {
long long b = n / a;
best = min(best, 2 * (a + b));
}
}
cout << best << "\n";
return 0;
}
Bình luận