Bài toán đong nước
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Bạn có hai chiếc bình rỗng dung tích lần lượt là $A$ lít và $B$ lít cùng một nguồn nước vô tận. Trong mỗi bước, bạn được phép thực hiện một trong các thao tác sau:
- Đổ đầy nước vào bình $1$ hoặc bình $2$.
- Đổ hết nước trong bình $1$ hoặc bình $2$ ra ngoài.
- Đổ nước từ bình này sang bình kia cho đến khi bình nguồn cạn hoặc bình đích đầy.
Hãy tìm số bước ít nhất để có đúng $C$ lít nước trong một trong hai bình.
Dữ liệu vào
Một dòng duy nhất chứa ba số nguyên $A, B, C$.
Dữ liệu ra
In ra số bước ít nhất để đong được $C$ lít, hoặc -1 nếu không thể thực hiện.
Ví dụ
| Input | Output |
|---|---|
| 3 5 4 | 6 |
| 2 6 5 | -1 |
Giới hạn
- $1 \le A, B \le 1000$
- $0 \le C \le 1000$
Community Discussion