Hướng dẫn giải của [VTT Q4 Contest 15] Bài 2: Tam giác vuông [LAKE]
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
Với mỗi chu vi ~P~, tìm tam giác vuông có ba cạnh nguyên, chu vi đúng ~P~ và diện tích lớn nhất (không có thì in 0). Có nhiều câu hỏi nên cần tiền xử lý.
Sub 1: Vét cạn — ~O(P^2)~ mỗi câu hỏi, dùng khi ~T \le 10, P \le 5000~
Duyệt hai cạnh góc vuông ~a \le b~, cạnh huyền ~c = P - a - b~, kiểm tra ~a^2 + b^2 = c^2~ và lấy diện tích ~\frac{ab}{2}~ lớn nhất. Nếu chỉ nộp sub này: đúng 29/100 test.
Sub 2: Duyệt một cạnh — ~O(P)~ mỗi câu hỏi, dùng khi ~T \le 10~
Từ ~a^2 + b^2 = (P - a - b)^2~ rút ra ~b = \frac{P(P - 2a)}{2(P - a)}~. Chỉ cần duyệt ~a~ rồi kiểm tra ~b~ có nguyên không. Nếu chỉ nộp sub này: đúng 90/100 test (10 test có ~T~ lớn bị quá thời gian).
Sub 3: Sinh bộ ba Pytago bằng công thức Euclid — tiền xử lý, trả lời ~O(1)~
Mọi tam giác vuông nguyên đều là bội ~k~ lần một bộ nguyên thủy ~(m^2 - n^2, 2mn, m^2 + n^2)~ với ~m > n~, khác tính chẵn lẻ, nguyên tố cùng nhau. Duyệt mọi cặp ~(m, n)~ có chu vi ~2m(m+n) \le 10^6~, rồi với mỗi bội ~k~ cập nhật best[k * chuvi] = max(..., k^2 * dientich). Tổng số bước cỡ ~10^6 \log~ (tổng điều hòa). Diện tích lớn nhất cỡ ~7 \cdot 10^{10}~ nên dùng long long. Nếu chỉ nộp sub này: đúng 100/100 test.
Chương trình hoàn chỉnh
main đọc hết các câu hỏi; nếu ~T \le 10~ và ~P \le 5000~ gọi sub1, nếu chỉ ~T \le 10~ gọi sub2, còn lại gọi sub3. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int T;
int P[100005];
const int MAXP = 1000000;
long long best[MAXP + 1];
// Sub 1: vét cạn hai cạnh góc vuông a <= b, cạnh huyền c = P - a - b, kiểm tra a^2 + b^2 = c^2
// ~O(P^2)~ mỗi câu hỏi, dùng khi T <= 10 và P <= 5000
void sub1() {
for (int i = 0; i < T; i++) {
long long p = P[i], ans = 0;
for (long long a = 1; a < p; a++)
for (long long b = a; a + b < p; b++) {
long long c = p - a - b;
if (a * a + b * b == c * c) ans = max(ans, a * b / 2);
}
cout << ans << "\n";
}
}
// Sub 2: từ a^2 + b^2 = (P-a-b)^2 suy ra b = P(P-2a) / (2(P-a)).
// Duyệt a, kiểm tra b nguyên: ~O(P)~ mỗi câu hỏi, dùng khi T <= 10
void sub2() {
for (int i = 0; i < T; i++) {
long long p = P[i], ans = 0;
for (long long a = 1; 2 * a < p; a++) {
long long num = p * (p - 2 * a), den = 2 * (p - a);
if (num % den == 0) {
long long b = num / den;
ans = max(ans, a * b / 2);
}
}
cout << ans << "\n";
}
}
// Sub 3: sinh mọi bộ ba Pytago nguyên thủy bằng công thức Euclid (m > n, khác tính chẵn lẻ, nguyên tố cùng nhau),
// mỗi bộ nhân với k cho mọi bội chu vi <= 10^6, lưu diện tích lớn nhất cho từng chu vi. Sau đó trả lời ~O(1)~.
void sub3() {
for (long long m = 2; 2 * m * (m + 1) <= MAXP; m++)
for (long long n = 1; n < m; n++) {
if ((m - n) % 2 == 0 || __gcd(m, n) != 1) continue;
long long a = m * m - n * n, b = 2 * m * n, c = m * m + n * n;
long long per = a + b + c, area = a * b / 2;
if (per > MAXP) break;
for (long long k = 1; k * per <= MAXP; k++)
best[k * per] = max(best[k * per], k * k * area);
}
for (int i = 0; i < T; i++) cout << best[P[i]] << "\n";
}
int main() {
freopen("LAKE.INP", "r", stdin);
freopen("LAKE.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> T;
int mx = 0;
for (int i = 0; i < T; i++) { cin >> P[i]; mx = max(mx, P[i]); }
if (T <= 10 && mx <= 5000) sub1();
else if (T <= 10) sub2();
else sub3();
}
Bình luận