Hướng dẫn giải của [200 đề thầy Đức] Bài 16: Căn phòng kì diệu
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
Cần chọn ~a_1 \ge a~, ~b_1 \ge b~ sao cho ~a_1 \cdot b_1 \ge 6n~ và tích ~a_1 \cdot b_1~ nhỏ nhất. Đề cho phép in lời giải tối ưu bất kỳ, nhưng máy chấm so khớp từng chữ nên cần quy ước chọn đáp án (xem phần cuối).
Sub 1: Vét cạn — ~O(6n)~, dùng khi ~6n \le 10^6~
Thử mọi ~a_1~ từ ~a~ đến ~\max(a, 6n)~; với mỗi ~a_1~, chiều còn lại nhỏ nhất là ~b_1 = \max(b, \lceil 6n / a_1 \rceil)~. Lấy cặp có diện tích nhỏ nhất. Nếu chỉ nộp sub này: đúng 13/33 test (các test lớn quá thời gian).
Sub 2: Chỉ thử quanh căn bậc hai — ~O(\sqrt{6n})~
Đặt ~s = \lceil \sqrt{6n} \rceil~. Nếu cả hai chiều cuối cùng đều lớn hơn ~s~ thì giảm bớt một chiều vẫn đủ diện tích, nên lời giải tối ưu có một chiều ~\le \max(\text{chiều ban đầu}, s)~. Vậy chỉ thử ~a_1 \in [a, \max(a,s)]~ và ~b_1 \in [b, \max(b,s)]~, chiều kia tính như trên. Dùng ~long long~ (diện tích tới ~10^{18}~). Nếu chỉ nộp sub này: đúng 33/33 test.
Chương trình hoàn chỉnh
Quy ước chọn đáp án khi có nhiều lời giải tối ưu (khớp tất cả test của máy chấm): đổi chỗ để ~a \le b~, chọn lời giải có ~a_1~ nhỏ nhất (khi diện tích bằng nhau), rồi đổi chỗ lại khi in. Chương trình đọc ~n, a, b~, nếu ~6n \le 10^6~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long n, a, b;
long long N; // diện tích tối thiểu cần: 6 * n
long long bestS, bestA, bestB; // lời giải tốt nhất tìm được (bestS = diện tích)
// Thử một cặp kích thước (x, y) đủ diện tích: ghi nhận nếu diện tích nhỏ hơn;
// bằng diện tích thì chọn x nhỏ hơn (quy ước chọn đáp án)
void consider(long long x, long long y) {
if (x * y < bestS || (x * y == bestS && x < bestA)) { bestS = x * y; bestA = x; bestB = y; }
}
// Với chiều x cố định, chiều y nhỏ nhất đủ diện tích là max(b, ceil(N / x))
long long needY(long long x) { return max(b, (N + x - 1) / x); }
long long needX(long long y) { return max(a, (N + y - 1) / y); }
// Sub 1: vét cạn — thử mọi chiều x trong [a, max(a, N)], lấy y nhỏ nhất tương ứng
// Dùng khi 6n <= 10^6 (N nhỏ)
void sub1() {
for (long long x = a; x <= max(a, N); x++) consider(x, needY(x));
}
// Sub 2: chỉ cần thử x trong [a, max(a, s)] và y trong [b, max(b, s)],
// với s = ceil(sqrt(N)). Lý do: nếu cả hai chiều đều lớn hơn s thì
// có thể giảm một chiều xuống <= s mà diện tích vẫn đủ, nên lời giải tối ưu nằm trong các trường hợp này.
void sub2() {
long long s = (long long)sqrtl((long double)N) + 2;
for (long long x = a; x <= max(a, s); x++) consider(x, needY(x));
for (long long y = b; y <= max(b, s); y++) consider(needX(y), y);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> a >> b;
N = 6 * n;
bestS = LLONG_MAX;
// Quy ước: đổi để a <= b, chọn lời giải có chiều (ứng với a) nhỏ nhất, in xong đổi lại
bool sw = a > b;
if (sw) swap(a, b);
if (N <= 1000000) sub1(); // n nhỏ: vét cạn cho chắc
else sub2(); // n lớn: chỉ thử các chiều quanh căn bậc hai
if (sw) swap(bestA, bestB);
cout << bestS << "\n" << bestA << " " << bestB << "\n";
return 0;
}
Bình luận