Максимальное время X и Y можно уменьшить почти до 0, используя числа A или B.

Даны 4 целых числа X, Y, A, B . За один ход либо уменьшите X на A и Y на B , либо уменьшите X на B и Y на A. Рассчитайте максимально возможные ходы. Даны 4 целых числа X, Y, A, B . За один ход мы можем сделать X = X — A и Y = Y — B или X = X — B и Y = Y — A. Подсчитайте максимальное количество возможных ходов.

Пример:

Input: X = 10, Y = 12, A = 2, B = 5
Output: 3
Explanation: 1st move: X = 8, Y = 7 after subtracting X by A and Y by B
2nd move: X = 6, Y = 2 after subtracting X by A and Y by B
3rd move: X = 1, Y = 0 after subtracting X by B and Y by A
So a total of 3 moves can be performed.

Input: X = 1, Y = 1, A = 2, B = 2
Output: 0

Наивный подход: при каждом значении X и Y мы можем вычесть максимальное значение A и B из максимального значения X и Y и вычесть минимальное значение A и B из минимального значения X и Y до тех пор, пока X и Y не останутся больше нуля.

Эффективный подход: данная проблема может быть решена с использованием метода бинарного поиска ответов.

• Ключевая идея здесь заключается в том, что если для любого количества ходов N можно выполнить столько же ходов, то мы также можем выполнить N – 1 ходов.
• Таким образом, мы можем выполнить бинарный поиск по ответу. Зафиксируйте диапазон L = 1 и R = 10000000 (измените это, если есть большие целые значения) и для каждого значения mid = ( L + R )/2 проверьте, можем ли мы выполнить столько ходов. Если возможно, сдвиньте L = mid + 1, иначе R = mid – 1. Верните максимально возможное значение.
• Чтобы проверить любое число mid, мы должны уменьшить X и Y как минимум на mid * min( A , B ), а для оставшегося элемента мы можем вычислить общие значения для оставшихся для | А – Б |. Если эти значения больше среднего, увеличьте правый диапазон, в противном случае уменьшите левый диапазон.

Реализация:

Временная сложность: O (log (MAXN)), где MAXN — максимальное количество ходов.
Вспомогательное пространство: O(1)