DPCUTREC - Cắt hình chữ nhật
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Người ta dùng máy cắt để cắt một hình chữ nhật có kích thước ~M×N~ thành một số "ít nhất các hình vuông" có kích thước nguyên dương và có các cạnh song song với cạnh hình chữ nhật ban đầu. Máy cắt khi cắt luôn cắt theo phương song song với một trong hai cạnh của hình chữ nhật và chia hình chữ nhật thành hai phần.
Input
- Một dòng duy nhất chứa hai số nguyên dương ~M~ và ~N~ cách nhau bởi một dấu cách.
Giới hạn:
- ~1 ≤ M, N ≤ 1000~.
Output
- Một số nguyên duy nhất là số hình vuông ít nhất cắt được.
Sample
Input #1
5 6
Output #1
5
Hint
- Ta dùng ~4~ lần cắt như hình dưới đây để được ~5~ hình vuông.
Problem source: Chuyên Sơn La Online Judge
Bình luận
bài này thêm 10 test nx được kh ạ