Bi xanh (THT TQ 2015)

Xem PDF

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Em nhận được một món quà từ ông tiên. Ông ban cho em hộp gồm vô hạn viên bi xanh. Tuy nhiên khi sử dụng bi để chơi trò chơi thì cần dùng đúng \(X\) viên bi xanh. Có 2 thao tác được sử dụng là:

  • Thao tác 1: Lấy \(A\) viên bi xanh từ trong hộp ra.
  • Thao tác 2: Bỏ \(B\) viên bi xanh từ ngoài vào hộp.

Yêu cầu duy nhất ông tiên đưa ra là em phải dùng ít thao tác nhất để lấy được đúng \(X\) viên bi xanh thì chiếc hộp sẽ thuộc về em mãi mãi.

Ví dụ em cần lấy ra 7 viên bi xanh (\(X = 7\)), \(A = 3, B = 8\) thì số thao tác ít nhất phải dùng là 6 trong đó dùng 5 lần thao tác 1, 1 lần thao tác 2.

Input

  • Gồm một dòng chứa 3 số nguyên dương \(A, B, X\) (\(A \le 10^{18}, B \le 10^{18}, X \le 10^{18}\)).

Output

  • Ghi ra một số nguyên dương duy nhất là tổng số thao tác ít nhất cần phải thực hiện. Nếu không có cách thực hiện để lấy được đúng \(X\) bi xanh thì đưa ra -1.

Example

Test 1

Input
3 8 7
Output
6

Bình luận

Không có bình luận nào.