- Описание
- Отправленные решения
21. Нормализация показателей
Разработчики сервиса сбора данных решили уменьшить количество возможных вариантов ответов. Для этого выбрали $n$ различных целых чисел — канонические варианты.
Но в системе уже имеется $m$ старых ответов. Для каждого их этих $m$ чисел необходимо найти ближайший из $n$ канонических вариантов, т.е. с минимальным модулем разности.
Формат ввода
В первой строке записано целое число $n$ ($1 \le n \le 50\,000$).
Во второй строке записаны $n$ целых чисел $a_1$ $a_2$ … $a_n$ — канонические ответы.
В третьей строке записано одно целое число $m$ ($1 \le m \le 50\,000$).
В $j$-й из следующих $m$ строк записано одно целое число $b_{j}$.
Гарантируется, что все входные числа не превосходят $10^{6}$ по абсолютной величине.
Формат вывода
Для каждого значения $b_j$ найдите каноническое значение (ближайшее). Если оптимальных значений несколько, выведите любое из них.
Ограничения
Ограничение времени
2 с
Ограничение памяти
256 МБ
Пример 1
6
-7 3 8 12 -3 -10
7
-12
13
-5
-3
5
-2
0
-10
12
-3
-3
3
-3
3
Пример 2
5
20 -27 12 21 -7
12
-18
19
-27
-9
-26
-6
-2
-20
0
-3
16
-12
-27
20
-27
-7
-27
-7
-7
-27
-7
-7
20
-7
Пример 3
16
-1 -20 -17 25 24 18 -12 -11 14 9 7 -2 -29 -13 29 6
7
-25
-14
20
-23
24
26
18
-29
-13
18
-20
24
25
18