Codeforces Round 570 (Div. 3) |
---|
Закончено |
В магазине продается $$$n$$$ предметов. Цена $$$i$$$-го предмета равна $$$a_i$$$. Владелец магазина хочет приравнять цены всех предметов. Но он хочет изменить цены аккуратно.
Фактически, владелец магазина может изменять цену какого-то предмета $$$i$$$ таким образом, что разница между старой ценой этого предмета $$$a_i$$$ и новой ценой $$$b_i$$$ не превышает $$$k$$$. Другими словами, должно выполняться условие $$$|a_i - b_i| \le k$$$ ($$$|x|$$$ — это абсолютное значение $$$x$$$).
Он может изменять цену каждого предмета не более одного раза. Заметьте, что он может оставить старые цены некоторым предметам. Новая цена $$$b_i$$$ каждого предмета $$$i$$$ должна быть положительной (то есть должно выполняться условие $$$b_i > 0$$$ для всех $$$i$$$ от $$$1$$$ до $$$n$$$).
Ваша задача — найти максимально возможную равную цену $$$B$$$ всех предметов с ограничением, что для всех предметов должно выполняться условие $$$|a_i - B| \le k$$$ (где $$$a_i$$$ равно старой цене предмета, а $$$B$$$ — это одинаковая новая цена всех предметов) или сказать, что невозможно найти такую цену $$$B$$$.
Заметьте, что выбранная цена $$$B$$$ должна быть целой.
Вам необходимо ответить на $$$q$$$ независимых запросов.
Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 100$$$) — количество запросов. Каждый запрос представлен двумя строками.
Первая строка запроса содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 100, 1 \le k \le 10^8$$$) — количество предметов и величину $$$k$$$. Вторая строка запроса содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^8$$$), где $$$a_i$$$ равно цене $$$i$$$-го предмета.
Выведите $$$q$$$ целых чисел, где $$$i$$$-е целое число является ответом $$$B$$$ на $$$i$$$-й запрос.
Если невозможно приравнять цены всех заданных предметов с ограничением, что для всех предметов должно выполняться условие $$$|a_i - B| \le k$$$ (где $$$a_i$$$ равно старой цене предмета, а $$$B$$$ равно новой равной цене всех предметов), выведите -1. Иначе выведите максимально возможную равную цену всех предметов.
4 5 1 1 1 2 3 1 4 2 6 4 8 5 2 2 1 6 3 5 5 2 5
2 6 -1 7
В первом запросе тестового примера Вы можете выбрать цену $$$B=2$$$. Легко заметить, что разница между каждой старой ценой и новой ценой $$$B=2$$$ не превышает $$$1$$$.
В первом запросе тестового примера Вы можете выбрать цену $$$B=6$$$, тогда все разницы между старыми ценами и новыми ценами $$$B=6$$$ не превысит $$$2$$$.
В третьем запросе тестового примера Вы не можете выбрать никакую подходящую цену $$$B$$$. Для любого значения $$$B$$$ хотя бы одно условие из двух будет нарушено: $$$|1-B| \le 2$$$, $$$|6-B| \le 2$$$.
В четвертом запросе тестового примера все значения $$$B$$$ между $$$1$$$ и $$$7$$$ являются корректными. Но самое максимальное равно $$$7$$$, поэтому оно является ответом.
Название |
---|