CẮT HÌNH CHỮ NHẬT
Xem dạng PDF
Gửi bài giải
Điểm:
0,50 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Có một hình chữ nhật kích thước M × N, mỗi lần ta được phép cắt hình chữ nhật theo chiều ngang hoặc chiều dọc thành hai hình chữ nhật con và lại tiếp tục cắt các hình chữ nhật con cho đến khi được tất cả các hình vuông thì dừng.
Hỏi có thể cắt hình chữ nhật M × N thành ít nhất bao nhiêu hình vuông.
Dữ liệu vào:
đọc từ file văn bản HCN.INP gồm một số dòng, mỗi dòng là một test là một cặp số M, N (1 ≤ M, N ≤ 100). Số dòng không quá 1000.
Kết quả:
ghi ra file văn bản HCN.OUT gồm một số dòng là kết quả tương ứng với dữ liệu vào.
Ví dụ:
HCN.INP HCN.OUT
10 2 5
2 10 5
Bình luận
làm rõ đề bài
Có một hình chữ nhật kích thước M × N, mỗi lần ta được phép cắt hình chữ nhật theo chiều ngang hoặc chiều dọc thành hai hình chữ nhật con và lại tiếp tục cắt các hình chữ nhật con cho đến khi được tất cả các hình vuông thì dừng.
Hỏi có thể cắt hình chữ nhật M × N thành ít nhất bao nhiêu hình vuông.