Задание 6. Бинарный поиск

6.1 Приближенный поиск

Дан упорядоченный по возрастанию массив чисел. Дан второй массив чисел — запросы. Для каждого запроса необходимо вывести число из первого массива наиболее близкое к запрашиваемому.

Входные данные

В первой строке целое число $n$ — количество элементов в массиве. Во второй строке $n$ целых чисел — элементов массива. В третьей строке число $m$ — количество запросов. В четвертой строке $m$ целых числе — запросы.

Выходные данные

На выходе $m$ чисел через пробел — результаты выполнения запросов.

Пример

Вход

8
1 3 5 8 10 11 14 20
2
19 9

Выход

20 8

6.2 Дипломы

Дано $N$ одинаковых дипломов высотой $h$ и шириной $w$. Нужно найти сторону $M$ минимально возможного квадратного ящика, в который можно будет разложить все дипломы.

Дипломы нельзя вращать и складывать друг на друга.

Алгоритм должен использовать бинарный поиск.

Входные данные

На входе 3 целых числа: n w h, где $1 \le n,w,h \le 10^9$

Выходные данные

На выходе одно целое число — длина стороны минимального квадратного ящика, в который можно расположить все дипломы.

Пример 0

Вход

1 1 1

Выход

1

Пример 1

Вход

10 2 3

Выход

9

Пример 2

Вход

5 1 1 

Выход

3

6.3 Решение уравнения

Найдите такое число $x$, что $x^{2} - x + \sqrt{x} = a$, с точностью не менее 6 знаков после точки.

Алгоритм должен найти корни уравнения методом динарного поиска для последовательного приближения, до тех пор, пока не будет достигнута требуемая точность.

Входные данные

Вещественное число $1.0 \le a \le 10^10$

Выходные данные

Вещественное число $x$, удовлетворяющее уравнению.

Пример 1

Вход

1.0

Выход

1.0

Пример 2

Вход

4.0

Выход

2.166738