Hướng dẫn giải của [2526 KS2 THCS] Bài 2: Chia Sô cô la [BAI2]
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
Cắt thành k miếng hình chữ nhật theo đường kẻ ô. Miếng lớn nhất a x b đặt ở góc, phần còn lại phải cắt thành đúng k - 1 miếng.
Sub 1: Vét cạn, ~m, n \le 1000~ ~O(m \cdot n)~
Thử mọi kích thước a x b, kiểm tra khả thi (k = 1; k = 2 cần phần còn lại là hình chữ nhật; k >= 3 cần mn - ab >= k - 1). Chạy riêng subtask này đạt 16/24 test.
Sub 2: Công thức, ~m, n \le 10^6~ ~O(m)~
Với k >= 3, với mỗi a chọn b lớn nhất sao cho ab <= mn - (k-1). Chạy riêng subtask này đạt 24/24 test.
Chương trình hoàn chỉnh
Nếu m, n <= 1000 dùng sub 1, ngược lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m, n, k;
// Mieng lon a x b dat o goc; phan con lai (m*n - a*b o) phai cat duoc thanh dung k-1 mieng hinh chu nhat
bool feasible(ll a, ll b) {
ll R = m * n - a * b;
if (k == 1) return R == 0;
if (R < k - 1) return false;
if (k == 2) return R >= 1 && (a == m || b == n); // con dung 1 mieng thi phai la hinh chu nhat
return true; // k >= 3: cat duoc thanh k-1 mieng
}
// Sub 1: vet can O(m*n), dung khi m, n <= 1000: thu moi kich thuoc a x b
void sub1() {
ll best = 0;
for (ll a = 1; a <= m; a++)
for (ll b = 1; b <= n; b++)
if (feasible(a, b)) best = max(best, a * b);
cout << best << "\n";
}
// Sub 2: cong thuc O(m): tim a <= m, b <= n sao cho a*b <= m*n - (k-1)
void sub2() {
ll best = 0;
if (k == 1) best = m * n;
else if (k == 2) {
if (n >= 2) best = max(best, m * (n - 1));
if (m >= 2) best = max(best, (m - 1) * n);
} else {
ll T = m * n - (k - 1);
for (ll a = 1; a <= min(m, T); a++) best = max(best, a * min(n, T / a));
}
cout << best << "\n";
}
int main() {
cin >> m >> n >> k;
if (m <= 1000 && n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận