Bài toán đong nước

General
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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:

  1. Đổ đầy nước vào bình $1$ hoặc bình $2$.
  2. Đổ hết nước trong bình $1$ hoặc bình $2$ ra ngoài.
  3. Đổ 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$
Draft saved