DHBB 2023 - CBG - 11 - Cắt hình chữ nhật
Xem dạng PDF
Gửi bài giải
Điểm:
17,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Có một hình chữ nhật ~M \times N~ ô, mỗi lần ta được phép cắt hình chữ nhật thành hai hình chữ nhật con theo chiều ngang hoặc chiều dọc và lại tiếp tục cắt các hình chữ nhật con cho đến khi được hình vuông thì dừng.
Hỏi có thể cắt hình chữ nhật ~M \times N~ thành ít nhất bao nhiêu hình vuông.
Input
Gồm một số dòng, mỗi dòng là một test chứa một cặp số ~M, N~ ~(1 \le M, N \le 100)~.
Output
Gồm một số dòng là kết quả tương ứng với dữ liệu vào.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~60\%~ | ~1 \le M, N \le 20~ |
| 2 | ~40\%~ | ~20 < M, N \le 100~ |
Sample Input 1
10 2
Sample Output 1
5
Bình luận