Codeforces Round 895 (Div. 3) |
---|
Закончено |
У вас есть два сосуда с водой. В первом сосуде сейчас находится $$$a$$$ грамм воды, во втором сосуде сейчас находится $$$b$$$ грамм воды. Оба сосуда очень большие, в каждый из них может поместиться любое количество воды.
Также у вас есть пустая чашка, в которую может поместиться не более $$$c$$$ грамм воды.
За один ход вы можете зачерпнуть из любого сосуда не более $$$c$$$ грамм воды и перелить её в другой сосуд. Заметим, что масса перелитой за один ход воды — не обязательно целое число.
Какое минимальное количество ходов потребуется, чтобы массы воды в сосудах стали равны? Обратите внимание, что производить какие-либо действия помимо описанных ходов нельзя.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора содержит три целых числа $$$a$$$, $$$b$$$ и $$$c$$$ ($$$1 \le a, b, c \le 100$$$) — масса воды в сосудах и вместимость чашки, соответственно.
Для каждого набора входных данных выведите единственное число — минимальное количество ходов, необходимое для того, чтобы в сосудах стало одинаковое количество воды. Можно показать, что это всегда возможно.
63 7 217 4 317 17 117 21 1001 100 197 4 3
1 3 0 1 50 16
В первом наборе входных данных примера достаточно одного хода: если перелить $$$2$$$ грамма воды из второго сосуда в первый, то в каждом из них окажется по $$$5$$$ грамм воды.
Во втором наборе входных данных примера достаточно совершить три хода:
Заметьте, что это не единственный способ уравнять сосуды за $$$3$$$ хода, но не существует способа сделать это за $$$2$$$ хода.
В третьем наборе входных данных примера сосуды изначально содержат одинаковое количество воды, следовательно, совершать ходы не нужно. Ответ — $$$0$$$.
Название |
---|