Cắt gạch
Đề bài
Mô tả
Youssef là một thợ lát gạch người Ma-rốc chuyên làm tranh khảm. Anh có trong tay những viên gạch hình chữ nhật với rất nhiều kích thước, mọi kích thước đều là số nguyên xăng-ti-mét. Khi cần những viên gạch hình bình hành, anh cắt chúng từ số gạch sẵn có. Để việc này dễ hơn, anh đã chế tạo một máy cắt gạch đặt một lưới ô vuông cạnh cm lên mặt cắt để định hướng các nhát cắt. Do giới hạn của máy, yêu cầu thẩm mỹ và việc Youssef không thích lãng phí gạch, các nhát cắt phải tuân theo những quy tắc sau:
- Viên gạch hình chữ nhật cần cắt phải được đặt ở góc dưới bên trái của mặt cắt, các cạnh trùng với đường lưới.
- Lưỡi cắt có thể cắt theo đường thẳng nối hai điểm lưới khác nhau trên biên viên gạch, miễn là hai điểm đó nằm trên hai cạnh kề nhau của biên.
- Bốn đỉnh của viên gạch hình bình hành thu được phải nằm trên bốn cạnh của viên gạch hình chữ nhật ban đầu.
- Không cạnh nào của hình bình hành được nằm trên một cạnh của hình chữ nhật.
Hình dưới đây cho thấy cách khác nhau để cắt ra một viên gạch hình bình hành có diện tích cm² theo các quy tắc trên.

Youssef cần cắt gạch với mọi diện tích từ tới . Anh muốn biết: với diện tích nào trong đoạn này thì anh có thể cắt ra nhiều viên gạch khác nhau nhất?
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên chứa số nguyên , số bộ test. Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và , đoạn diện tích của các viên gạch.
Dữ liệu ra
Với mỗi bộ test , in ra giá trị trong đoạn từ tới sao cho số cách cắt ra một hình bình hành có diện tích là lớn nhất, cùng với số cách khác nhau để cắt ra hình bình hành như vậy. Nếu có nhiều giá trị thỏa mãn, in ra giá trị nhỏ nhất.
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 4 4 2 6 |
4 8 6 20 |
Bộ test thứ nhất: có cách cắt ra hình bình hành diện tích (như trong hình). Bộ test thứ hai: trong các diện tích từ tới , diện tích có nhiều cách cắt nhất, cách. |
| 2 14 15 1 1 |
14 108 1 0 |
Diện tích và đều có cách cắt, in diện tích nhỏ hơn. Không cắt được hình bình hành nào có diện tích . |
Bình luận