Hiểu bài toán

Cho hai số nguyên dương $a$ và $b$. Ta cần tìm chiều cao nguyên dương $h$ nhỏ nhất sao cho tam giác có độ dài đáy là $b$ và chiều cao là $h$ có diện tích ít nhất là $a$. Diện tích tam giác được tính theo công thức $S = \frac{1}{2} \cdot \text{đáy} \cdot \text{chiều cao}$. Ta cần tìm số nguyên dương $h$ nhỏ nhất sao cho $\frac{1}{2} \cdot b \cdot h \geq a$. Biến đổi bất phương trình ta được $h \geq \frac{2a}{b}$. Vì $h$ phải là số nguyên dương, giá trị nhỏ nhất của $h$ là số nguyên nhỏ nhất lớn hơn hoặc bằng $\frac{2a}{b}$ (hay nói cách khác là làm tròn lên của $\frac{2a}{b}$).

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

Cách Sử dụng hàm làm tròn số thực (ceil)

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

int main() {
    unsigned long long b, a;
    cin >> b >> a;

    double h = (2.0 * a) / b;
    cout << (unsigned long long) ceil(h);
}

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

Cách tiếp cận này sử dụng phép toán số học kiểu số thực. Nó tính giá trị $h = \frac{2a}{b}$ dưới dạng số thực double, sau đó sử dụng hàm ceil để làm tròn lên đến số nguyên gần nhất. Cuối cùng, nó ép kiểu lại thành số nguyên để in ra. Đây là cách trực quan nhất để giải quyết bài toán.

Cách Phép chia nguyên với kiểm tra số dư

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

int main() {
    long long n, m;
    cin >> n >> m;
    long long kq;
    if(m * 2 % n == 0)
        kq = m * 2 / n;
    else
        kq = m * 2 / n + 1;
    cout << kq;
    return 0;
}

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

Phương pháp này hoàn toàn sử dụng số nguyên. Nó tính $2a$ và chia cho $b$ sử dụng phép chia nguyên. Nếu $2a$ chia hết cho $b$, kết quả là thương số. Nếu không, ta cần cộng thêm 1 vào thương số để có giá trị làm tròn lên. Đây là cách tiếp cận an toàn, tránh các vấn đề tràn số nếu 2*a quá lớn, nhưng với giới hạn $10^6$ thì long long là đủ.

Cách Công thức tính tròn lên của số nguyên

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long b, a;
    cin >> b >> a;
    long long h = (2 * a + b - 1) / b;
    cout << h << "\n";
    return 0;
}

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

Đây là một kỹ thuật phổ biến trong lập trình thi đấu để tính làm tròn lên của một phân số $\frac{x}{y}$ (với $x, y > 0$) mà không cần dùng số thực hay hàm ceil. Giá trị cần tìm là $\lceil \frac{2a}{b} \rceil$. Công thức tính là $\frac{2a + b - 1}{b}$. Lí do là nếu $2a$ chia hết cho $b$, phần bù $b-1$ không ảnh hưởng đến thương. Nếu không chia hết, phần bù này sẽ đẩy thương số lên 1 đơn vị so với phép chia nguyên thông thường.

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

Bài học kinh nghiệm

• Bài toán quy về tìm số nguyên dương nhỏ nhất $h$ sao cho $h \geq \frac{2a}{b}$.
• Giá trị cần tìm chính là kết quả của phép làm tròn lên (ceiling) của phân số $\frac{2a}{b}$.

Lỗi thường gặp

• Làm tròn sai chiều: Nếu dùng phép chia số thực rồi cast sang long long (floor), kết quả có thể bị sai nếu $h$ không phải là số nguyên. Phải dùng hàm ceil hoặc công thức toán học.
• Tràn số (Integer Overflow): Nếu tính 2*a trước mà không chọn kiểu dữ liệu đủ lớn (như long long), có thể gây tràn số với $a$ lớn (dù $10^6$ thì int vẫn đủ nhưng long long là an toàn hơn).