Số mảnh tối đa sau N lần cắt trong C++

Cho một hình vuông. Thực hiện đúng N lần cắt (mỗi lần cắt thẳng ngang hoặc dọc). Tìm số mảnh hình chữ nhật/vuông bằng nhau lớn nhất có được.

Ví dụ

N = 8 → 4 ngang + 4 dọc = 5x5 = 25 mảnh
N = 7 → 3 ngang + 4 dọc (hoặc ngược lại) = 4x5 = 20 mảnh

Toán học

Giả sử cắt h lần ngang và v lần dọc (h + v = N). Số mảnh = (h+1) * (v+1).

Để tối đa hóa tích với tổng cố định → hai số nên bằng nhau hoặc chênh nhau 1.

• N chẵn: h = v = N/2 → mảnh = (N/2 + 1)²
• N lẻ: h = N/2, v = N/2 + 1 → mảnh = (N/2 + 1) * (N/2 + 2)

Công thức chung: (N/2 + 1) * (N - N/2 + 1) (chia nguyên).

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

long long maxPieces(int N) {
    long long h = N / 2;      // Số cắt ngang
    long long v = N - h;      // Số cắt dọc
    return (h + 1) * (v + 1);
}

int main() {
    int N = 7;
    cout << "So manh toi da = " << maxPieces(N); // Output: 20
    return 0;
}

Kết quả

So manh toi da = 20