Две монеты
На острове ходят монеты только двух достоинств: a и b тенге. Вы покупаете товар за c тенге и можете давать монеты продавцу и получать монеты сдачей, у обоих монет сколько угодно. Какое наименьшее число монет при этом перейдёт из рук в руки — в обе стороны вместе?
Иначе говоря, нужны целые x и y с a·x + b·y = c (положительное число — монеты от вас, отрицательное — сдача вам), и среди всех таких пар — наименьшее |x| + |y|.
Вход
В первой строке число покупок q (1 ≤ q ≤ 20 000). В каждой из следующих строк — a, b, c (1 ≤ a, b ≤ 10⁹, 0 ≤ c ≤ 10⁹).
Выход
Для каждой покупки — наименьшее число монет или -1, если заплатить ровно c невозможно.
Примеры
Пример 1
6 3 5 4 4 6 7 5 5 10 7 3 0 1 1 1 2 7 1
4 -1 2 0 1 4
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 5 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Когда уравнение a·x + b·y = c вообще разрешимо в целых числах? Подумайте, на что делится левая часть при любых x и y.
2Подсказка 2
Если одно решение (x, y) нашлось, как получить из него все остальные? Попробуйте прибавить к x что-нибудь и отнять от y что-нибудь, не меняя суммы.
3Идея
Левая часть всегда делится на g = НОД(a, b), поэтому при c, не кратном g, ответ −1. Иначе расширенный алгоритм Евклида даёт a·x₀ + b·y₀ = g, и, умножив на c/g, получаем одно решение. Все решения — это x = x₀ + t·b/g, y = y₀ − t·a/g для целых t. Осталось выбрать t, при котором |x| + |y| меньше всего.
4Разбор
Функция f(t) = |x₀ + t·B| + |y₀ − t·A|, где A = a/g, B = b/g, — сумма двух «уголков», то есть выпуклая ломаная. Её минимум лежит в изломе, а изломы — там, где одна из скобок обращается в ноль: t = −x₀/B и t = y₀/A. Эти точки обычно не целые, поэтому проверяем несколько целых t рядом с каждой и берём лучшее.
В первом примере a = 3, b = 5, c = 4: решения 3·3 − 5·1 = 4 и 3·(−2) + 5·2 = 4 дают по четыре монеты, и меньше нельзя. Это та же задача, что знаменитая головоломка о двух кувшинах на 3 и 5 литров: как отмерить ровно 4.
Аккуратнее с округлением: в Go деление целых округляет к нулю, а нам нужен «пол». Для отрицательных чисел это разные вещи, поэтому в эталоне есть своя floorDiv. Числа помещаются в int64: |x₀| ≤ b/g, после умножения на c/g — не больше 10¹⁸.
4+Решение
5Сложность
O(log min(a, b)) на расширенный алгоритм и O(1) на перебор кандидатов. Всего O(q log max(a, b)).
6Типичные ошибки
- Первое решение вместо лучшего. Коэффициенты расширенного алгоритма, умноженные на c/g, могут быть огромными — около 10¹⁸ монет вместо десятка.
- Перебор x. Пробовать все x от −c до c честно, но при c = 10⁹ — миллиард шагов на покупку.
- Округление к нулю.
-7 / 2в Go даёт −3, а пол — −4. Пропустив нужного кандидата, получите ответ на единицу-две хуже.