Задачка на алгоритм для ниндзя

Уже полторы недели небольшими набегами думаем, как её решить. Может быть, тут кто-то сможет :) Даны два массива натуральных чисел: x и y (оба массива неубывающие), и натуральное число Q. Найти такие числа из этих массивов, что x[i] * y[j] максимально близко к Q Сложность не должна превышать O(n+m), где n и m — размеры массивов.

Ответ

Просматриваем один массив с головы, другой с хвоста. Передвигаемся по второму массиву из хвоста в голову, сохраняя два значения- текущее произведение и предыдущее когда текущее произведение меньше Q, то находим какое произведение ближе к искомому- текущее, предыдущее или ранее сохраненное как наиближайшее сдвигаем первый массив из головы в хвост на одну позицию и повторяем движение по второму массиву, пока опять текущее произведение не станет меньше Q Когда первый массив будет весь пройден то наиближайшее будет найдено при сложности i+j UPD Реализация на JavaScript http://jsfiddle.net/ReinRaus/nK5Nz/ UPD2 Исправил ошибки и недочеты кода