Phân tích

Bài toán này ban đầu có dạng một câu đố nhỏ: Có bao nhiêu số \(A\) mà diện tích \(A/2\) có thể tạo thành? Câu trả lời là có \(M \times N\) số như vậy, với mọi số nguyên \(0 < A \le MN\), chúng ta luôn có thể tìm thấy một tam giác với diện tích \(A/2\) được tạo bởi các điểm nguyên trên giấy kẻ ô vuông.

Nếu \(A > NM\), rõ ràng không thể tạo ra tam giác như vậy vì diện tích tối đa của một tam giác nằm trong hình chữ nhật \(N \times M\) là \(NM/2\). Ngược lại, nếu \(A \le NM\), chúng ta luôn có thể tìm được lời giải.

Hình ảnh dưới đây đưa ra bước then chốt trong chứng minh, cũng như cách giải quyết bài toán của chúng ta.

Giả sử phần nguyên của \(A/M\) là \(k\), ta có \(kM \le A \le (k+1)M\). Ký hiệu \(S(XYZ)\) là diện tích tam giác \(\Delta XYZ\). Theo công thức diện tích tam giác với các đỉnh \((0,0), (x_2, y_2), (x_3, y_3)\) là \(\frac{1}{2} |x_2 y_3 - x_3 y_2|\), ta có thể cố định một đỉnh tại \((0,0)\).

Đặt ba đỉnh là \((0, 0), (x_2, y_2), (x_3, y_3)\). Khi đó \(A = |x_2 y_3 - x_3 y_2|\).
Ta có thể chọn \(x_2 = \lceil A/M \rceil\) và \(y_3 = M\). Khi đó ta cần tìm \(x_3, y_2\) sao cho \(x_2 \cdot M - x_3 \cdot y_2 = A\).
Từ đó \(x_3 \cdot y_2 = x_2 \cdot M - A\).
Vì \(x_2 = \lceil A/M \rceil\), ta có \((x_2 - 1)M < A \le x_2 M\), do đó \(0 \le x_2 M - A < M\).
Chúng ta có thể chọn \(y_2 = x_2 M - A\) và \(x_3 = 1\).
Các tọa độ sẽ là \((0, 0), (x_2, 1), (1, M)\).
Kiểm tra lại diện tích: \(2S = |x_2 \cdot M - 1 \cdot (x_2 M - A)| = |x_2 M - x_2 M + A| = A\).

Vì \(x_2 = \lceil A/M \rceil\) và \(A \le NM\), nên \(x_2 \le N\). Các tọa độ \((0,0), (x_2, 1), (1, M)\) đều nằm trong phạm vi \(0 \le x \le N\) và \(0 \le y \le M\).

Cách cài đặt

1. Nếu \(A > N \times M\), in ra IMPOSSIBLE.
2. Tính \(x_2 = \lceil A/M \rceil\). Trong lập trình, có thể tính bằng (A + M - 1) / M.
3. Tính \(y_2 = x_2 \cdot M - A\).
4. Ba điểm cần tìm là \((0, 0), (x_2, 1), (1, M)\).

Độ phức tạp

Độ phức tạp cho mỗi bộ dữ liệu là \(O(1)\).

Bài tập mở rộng

(1) Đối với những độc giả cẩn thận, còn một điều nữa chúng ta chưa chứng minh. Không có cách nào để tạo thành một tam giác trên giấy kẻ ô vuông với diện tích lớn hơn \(MN/2\). Hãy tìm một lý do đơn giản cho điều này.

(2) Chúng ta đã lập luận rằng \(2S(ABC^*)\) phải chạm tới \(A\) vì nó sẽ chạm tới mọi số nguyên giữa \(kM\) và \((k+1)M\). Hãy lập luận trực tiếp rằng, trong khi \(C^*\) di chuyển lên trên, \(S(ABC^*)\) sẽ tăng thêm \(0.5\) mỗi khi \(C^*\) di chuyển lên cao thêm một đơn vị.

Dựa trên phân tích chính thức của Google Code Jam.