Đong nước

View as PDF

Submit solution


Points: 400 (partial)
Time limit: 1.0s
Memory limit: 64M
Input: stdin
Output: stdout

Author:
Problem types

Cho một thùng nước và hai gáo nước có dung tích lần lượt là \(A\) và \(B\). Ban đầu thùng nước rỗng. Một người phải dùng hai gáo nước múc nước vào thùng, với điều kiện khi múc vào hay múc ra đều phải đong đầy gáo. Hãy tìm cách dùng số lần múc nước ít nhất để có được lượng nước là \(C\) trong thùng.

Dữ liệu

  • Dòng 1 chứa số \(k ≤ 100\) là số test.
  • \(k\) dòng tiếp theo, mỗi dòng chứa ba số nguyên dương \(A, B, C ≤ 10^9\) cách nhau bởi dấu cách, tương ứng với một test.

Kết quả

  • Với mỗi test, ghi ra trên một dòng một số nguyên duy nhất là số lần múc theo phương án tìm được, nếu không thể thực hiện yêu cầu ghi ra số -1.

Sample input

2
15 24 3
100 27 8

Sample output

5
5

Giải thích:

  • Test 1: Dùng giáo 24 múc vào 2 lần và dùng gáo 15 đổ ra 3 lần.
  • Test 2: Dùng gáo 27 múc vào 4 lần và dùng gáo 100 múc ra 1 lần.

Nguồn: LMH-ĐHSP


Be the first to comment

Comments

There are no comments at the moment.