Cắt tấm vật liệu

Bối cảnh và bài toán

Một tấm hình chữ nhật kích thước a x b cần được cắt thành các hình vuông. Mỗi lần chỉ được cắt một mảnh hình chữ nhật thành hai mảnh theo đường thẳng song song cạnh.

Yêu cầu

Tìm số lần cắt ít nhất.

Input

Một dòng a b.

Output

In số lần cắt ít nhất.

Ràng buộc

• 1 <= a,b <= 200

Chấm điểm

Ví dụ 1

Input

3 5

Output

3

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

1 1

Output

0

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Rectangle Cutting. Bản FULLHOUSE DEV đã biên tập bối cảnh/format và ràng buộc khi cần để khớp scope-lock của khóa học.