Editorial for rect: Hình chữ nhật

Hiểu bài toán

Cho một thanh sắt có chiều dài là số nguyên dương chẵn L. Nhiệm vụ là uốn thanh sắt thành một hình chữ nhật sao cho các cạnh có độ dài là số nguyên, chu vi bằng L và diện tích là lớn nhất. Cần tìm giá trị diện tích lớn nhất đó.

Các cách tiếp cận

Cách Brute Force (Duyệt toàn bộ)

#include<stdio.h>
#define ll long long

int main(){
    ll n;
    scanf("%lld",&n);
    ll max = 0;
    for (ll i = 1; i <= n/2; i++){
        ll sum = i*(n/2 - i);
        if (sum > max) max = sum;
    }
    printf("%lld",max);
    return 0;
}

• Time Complexity: O(L)
• Space Complexity: O(1)

Đây là cách tiếp cận đơn giản nhất. Ta duyệt qua tất cả các giá trị chiều dài i từ 1 đến L/2. Với mỗi i, chiều rộng sẽ là (L/2 - i). Ta tính diện tích và cập nhật giá trị lớn nhất. Với L lớn (lên tới 10^9), phương pháp này sẽ quá thời gian chạy (Time Limit Exceeded). Tuy nhiên, nó phù hợp với các test nhỏ và giúp kiểm tra tính đúng đắn của bài toán.

Cách Toán học (Công thức)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){
    long long n;
    scanf("%lld",&n);
    long long x = n/4;
    long long y = n/2 - x;
    printf("%lld",x*y);
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là phương pháp tối ưu nhất. Ta có chu vi P = 2(a + b) = L => a + b = L/2. Diện tích S = a * b. Để S đạt max, a và b phải càng gần nhau càng tốt. Điều này xảy ra khi a và b xấp xỉ bằng nhau, tức là a ≈ b ≈ (L/2) / 2 = L/4. Do L là số chẵn, L/2 là số nguyên. Nếu L chia hết cho 4, ta chọn a = b = L/4. Nếu L không chia hết cho 4 (ví dụ L=18, L/2=9), ta chọn a = floor(L/4) = 2 và b = 7 (hoặc a=3, b=6). Thực tế, để hai số có tổng cố định tích lớn nhất, chúng phải gần nhau nhất. Nếu L/2 chẵn (L chia hết cho 4), tích max là (L/4)^2. Nếu L/2 lẻ (L chia hết cho 2 nhưng không chia hết cho 4), tích max là (L/4)(L/2 - L/4) = floor(L/4) * ceil(L/4). Code tính x = n/4 (chia lấy nguyên) và y = n/2 - x. Ví dụ L=18: x=4, y=9-4=5 => 45=20. Ví dụ L=20: x=5, y=10-5=5 => 55=25.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán quy về tìm hai số a, b nguyên dương sao cho a + b = L/2 và tích a * b là lớn nhất.
• Hai số có tổng không đổi thì tích lớn nhất khi chúng gần nhau nhất (xấp xỉ bằng nhau).

Lỗi thường gặp

• Sử dụng biến kiểu int而导致 tràn số (overflow) khi L lên tới 10^9, vì diện tích có thể lên tới ~2.5 * 10^17. Cần dùng kiểu dữ liệu 64-bit (long long).
• Quên chia 2 cho chu vi: Chu vi L = 2*(a+b) nên a+b = L/2. Nhiều người nhầm tưởng a+b = L.