Hướng dẫn giải của Tích cực đại (Đề Quảng Trị 2021)
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
Cho số nguyên dương N (N ≤ 10000), hãy biểu diễn N thành tổng các số nguyên dương sao cho tích các số hạng là lớn nhất, và in ra tích lớn nhất đó. Tích có thể rất lớn nên cần cẩn thận khi N lớn.
Sub 1: Vét cạn — ~O(2^n)~ (thực tế là số cách phân hoạch), dùng khi ~n \le 50~
Liệt kê mọi cách viết N thành tổng các số nguyên dương (đệ quy, mỗi lần chọn số hạng tiếp theo không lớn hơn số hạng trước), tính tích từng cách rồi lấy max. Với N ≤ 50 số cách không quá lớn và tích vừa kiểu long long.
Nếu chỉ nộp sub này: đúng 8/20 test.
Sub 2: Quy hoạch động — ~O(n^2)~, dùng khi ~n \le 100~
Gọi dp[i] là tích lớn nhất khi viết i thành tổng. Ta có dp[i] = max(i, max over j of j · dp[i-j]) với 1 ≤ j < i: số hạng đầu tiên là j, phần còn lại là một cách viết i-j tối ưu. Với N ≤ 100, dp[N] ≤ ~2.5·10^16 nên vẫn vừa long long.
Nếu chỉ nộp sub 2 (khi ép chạy riêng): đúng mọi test có N ≤ 100 trong bộ test, tức 9/20 test.
Sub 3: Công thức — ~O(n^2)~ (phép nhân số lớn), dùng khi ~n \le 10000~
Với các số hạng nguyên dương, nên dùng càng nhiều số 3 càng tốt, vì 3 là số cho tích lớn nhất trên mỗi đơn vị tổng:
- N chia hết cho 3: đáp án là ~3^{N/3}~.
- N chia 3 dư 1: dùng một số 4 (4 = 2+2) và các số 3: đáp án là ~4 \cdot 3^{(N-4)/3}~.
- N chia 3 dư 2: dùng một số 2 và các số 3: đáp án là ~2 \cdot 3^{(N-2)/3}~.
- Trường hợp N = 1: đáp án là 1.
Bẫy: ~3^{3333}~ có khoảng 1600 chữ số, không lưu được trong long long. Ta lưu số lớn dưới dạng mảng chữ số, mỗi lần nhân với 3 (hoặc với 2, 4) rồi in ngược lại.
Chương trình hoàn chỉnh
main đọc N: nếu N ≤ 50 gọi sub1, nếu N ≤ 100 gọi sub2, còn lại gọi sub3. Sub sau đúng cho cả miền của nó, nên nếu thi chỉ làm được sub 1 hoặc 2 vẫn ăn điểm phần tương ứng.
#include <bits/stdc++.h>
using namespace std;
int n;
// Sub 1: vét cạn — liệt kê mọi cách viết n thành tổng các số nguyên dương, tính tích, lấy max. Dùng khi n <= 50.
long long best1;
void rec1(int remain, int maxPart, long long prod) {
if (remain == 0) {
best1 = max(best1, prod);
return;
}
for (int p = min(remain, maxPart); p >= 1; p--)
rec1(remain - p, p, prod * p);
}
void sub1() {
best1 = 0;
rec1(n, n, 1);
cout << best1 << "\n";
}
// Sub 2: quy hoạch động dp[i] = tích lớn nhất khi viết i thành tổng. Dùng khi n <= 100.
void sub2() {
vector<long long> dp(n + 1, 0);
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = i; // chỉ một số hạng
for (int j = 1; j < i; j++)
dp[i] = max(dp[i], j * dp[i - j]);
}
cout << dp[n] << "\n";
}
// Sub 3: công thức. Tách càng nhiều số 3 càng tốt; n%3==1 thì dùng một số 4 (= 2*2), n%3==2 thì dùng một số 2.
// Kết quả có thể rất lớn nên lưu số nguyên lớn dưới dạng mảng chữ số (đảo ngược).
void mulSmall(vector<int> &a, int m) {
long long carry = 0;
for (auto &d : a) {
long long cur = (long long)d * m + carry;
d = cur % 10;
carry = cur / 10;
}
while (carry) {
a.push_back(carry % 10);
carry /= 10;
}
}
void sub3() {
if (n == 1) {
cout << 1 << "\n";
return;
}
int k, extra;
if (n % 3 == 0) {
k = n / 3;
extra = 1;
} else if (n % 3 == 1) {
k = (n - 4) / 3;
extra = 4;
} else {
k = (n - 2) / 3;
extra = 2;
}
vector<int> a{1};
for (int i = 0; i < k; i++) mulSmall(a, 3);
mulSmall(a, extra);
for (int i = (int)a.size() - 1; i >= 0; i--) cout << a[i];
cout << "\n";
}
int main() {
freopen("CAU4.INP", "r", stdin);
freopen("CAU4.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
if (n <= 50) sub1(); // dữ liệu nhỏ: vét cạn cho chắc
else if (n <= 100) sub2(); // quy hoạch động
else sub3(); // công thức
return 0;
}
Bình luận