Волшебный прыгающий мяч

Question

Мэри получила волшебный шар на свой день рождения. Мяч, когда брошен из некоторая высота, подпрыгивает для двойной этой высоты. Мария бросила мяч с ее балкона, который x над землей. Помочь ей подсчитайте, сколько отскоков необходимо, чтобы мяч достиг высота w.

Ввод: одно целое число z (1 & le; z & le; 10 ⁶ ) как количество тестовых случаев. За каждый тест, целые числа x и w (1 & le; x & le; 10 ⁹ , 0 & le; w & le; 10 ⁹ ).

Вывод: для каждого случая одно целое число равно числу отскоков необходимо, чтобы шарик достиг w, должно быть напечатано.

ОК, так что, хотя это выглядит невероятно просто, я не могу найти более эффективного способа его решения, чем простой, тупой, брутальный подход с циклическим умножением x на 2 до, по крайней мере, w. Конечно, для максимального теста это будет ужасное время. Затем я подумал об использовании предыдущих случаев, что экономит довольно много времени, при условии, что мы можем получить ближайший, но меньший результат из предыдущих случаев за короткое время (O (1)?), Чего, однако, я не могу (и не не знаю, если это возможно ..) реализовать. Как это сделать?

Answer 1

Вы по сути пытаетесь решить проблему

2 ⁱ x = w

и затем находите наименьшее целое число больше i.Решая, мы получаем

2 ⁱ = w / x

i = log ₂ (w / x)

Таким образом, один из подходов состоит в том, чтобы явно вычислить это значение, а затем взять потолок.Конечно, вам придется остерегаться численной нестабильности при этом.Например, если вы используете float s для кодирования значений, а затем разрешите w = 8 000 001 и x = 1 000 000, вы получите неправильный ответ (3 вместо 4).Если вы используете double s для хранения значения, вы также получите неправильный ответ, когда x = 1 и w = 536870912 (отчет 30 вместо 29, так как 1 x 2 ²⁹ = 536870912, но из-зана неточности в двойном ответе ошибочно округлено до 30).Похоже, нам придется переключиться на другой подход.

Давайте вернемся к вашему первоначальному решению, просто удвоив значение x до тех пор, пока оно не превысит w, здесь должно быть совершенно нормально.Максимальное количество раз, которое вы можете удвоить x, пока оно не достигнет w, задается в log ₂ (w / x), и, поскольку w / x составляет не более одного миллиарда, это повторяет самое большее log ₂ 10 ⁹ раз, что примерно в тридцать раз больше каждого.Выполнение тридцати итераций умножения на два, вероятно, будет чрезвычайно быстрым.В более общем случае, если верхняя граница w / x равна U, то для ее завершения потребуется не более O (log U) времени.Если у вас есть k (x, w) пар для проверки, это займет время O (k log U).

Если вы не удовлетворены этим, есть еще один очень быстрый алгоритм, который вы можете попробовать.По сути, вы хотите вычислить лог ₂ ш / х.Вы можете начать с создания таблицы, в которой перечислены все степени двух, а также их логарифмы.Например, ваша таблица может выглядеть следующим образом:

T[1] = 0
T[2] = 1
T[4] = 2
T[8] = 3
...

Затем вы можете вычислить w / x, а затем выполнить двоичный поиск, чтобы выяснить, в каком диапазоне находится значение.Верхняя граница этого диапазона - это количество раз, когда мяч должен отскочить.Это означает, что если у вас есть k разных пар для проверки, и если вы знаете, что максимальное отношение w / x равно U, создание этой таблицы занимает время O (log U), а затем каждый запрос занимает время, пропорциональное журналу размератаблицы, которая является O (log log U).Тогда общее время выполнения O (log U + k log log U), что очень хорошо.Учитывая, что вы имеете дело не более чем с одним миллионом проблемных случаев и что U составляет один миллиард, k log log U составляет чуть менее пяти миллионов, а log U - около тридцати.

Наконец, если вы готовычтобы делать извращенно ужасные вещи с побитовым хакерством, поскольку вы точно знаете, что w / x вписывается в 32-битное слово, вы можете использовать этот побитовый трюк с IEEE, удваивающим довычислить логарифм в очень небольшом количестве машинных операций.Это, вероятно, будет быстрее, чем два вышеупомянутых подхода, хотя я не могу обязательно гарантировать это.

Надеюсь, это поможет!

Answer 2

Используйте эту формулу для расчета количества отказов для каждого тестового случая.

ceil( log(w/x) / log(2) )

Это псевдокод, но преобразовать его в любой язык довольно просто.Просто замените log функцией, которая находит логарифм числа в некоторой конкретной базе, и замените ceil функцией, которая округляет указанное десятичное значение до следующего целого числа над ним (например, ceil (2.3) = 3).

См. http://www.purplemath.com/modules/solvexpo2.htm, почему это работает (в вашем случае вы пытаетесь решить уравнение x * 2 ^ n = w для целого числа n, и вы должны начать с деления обеих сторон на x).

РЕДАКТИРОВАТЬ:
Перед использованием этого метода, вы должны проверить, что w> x и вернуть 1, если это не так.(Мяч всегда должен отскакивать, по крайней мере, один раз).

Также было отмечено, что неточности в значениях с плавающей запятой могут иногда приводить к сбою этого метода.Вы можете обойти эту проблему, проверив, если 2 ^ (n-1)> = w, где n - результат вышеприведенного уравнения, и если это так, вернет (n - 1) вместо n.