De-Evolution Tam Giác
Đề bài
Mô tả
Cho một tam giác đều có độ dài cạnh là . Ta muốn biến nó thành một tam giác đều có độ dài cạnh là .
Trong mỗi giây, ta được phép thay đổi độ dài của đúng một cạnh của tam giác hiện tại, với hai điều kiện:
- Sau khi thay đổi, ba cạnh vẫn tạo thành một tam giác không suy biến (có diện tích dương).
- Tại mọi thời điểm, độ dài mỗi cạnh luôn là số nguyên dương.
Hãy tìm số giây ít nhất để biến tam giác đều cạnh thành tam giác đều cạnh .
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên và (), lần lượt là độ dài cạnh của tam giác đều ban đầu và tam giác đều cần đạt được.
Dữ liệu ra
In ra một số nguyên duy nhất là số giây ít nhất cần thiết.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 3 | 4 | Một cách: , mỗi bước đều là tam giác hợp lệ. Cần 4 bước. |
| 8 5 | 3 | . Cần 3 bước. |
| 22 4 | 6 | Cần 6 bước để đưa tam giác đều cạnh 22 về tam giác đều cạnh 4. |
Bình luận