Kotlin Heroes: Episode 7 |
---|
Закончено |
Ваш друг создал функцию поиска ближайшей точки. Для заданного массива целочисленных точек $$$x$$$ (отсортированного в возрастающем порядке и не содержащего дубликатов) и точки $$$y$$$ эта функция может найти ближайшую точку из $$$x$$$ к заданной точке $$$y$$$. Другими словами, функция найдет такую точку $$$x_i$$$, что значение $$$|y - x_i|$$$ является минимальным, где $$$|a|$$$ — абсолютное значение (модуль) $$$a$$$.
Например, если $$$x = [1, 2, 5, 7, 9, 11]$$$, то ответ для $$$y=3$$$ будет равен $$$2$$$, ответ для $$$y=5$$$ будет равен $$$5$$$, а ответ для $$$y=100$$$ будет равен $$$11$$$.
На самом деле, эта функция работает немного неправильно. Если к заданной точке существует несколько ближайших точек, то функция сломается (возникнет ошибка при ее исполнении). Например, если $$$x = [1, 2, 5, 7, 9, 11]$$$ (как выше) и $$$y=6$$$, то функция сломается, потому что точки $$$5$$$ и $$$7$$$ обе являются ближайшими для точки $$$6$$$.
Ваша задача — для заданного массива целочисленных точек $$$x$$$ (отсортированного в возрастающем порядке и не содержащего дубликатов) определить, можно ли сломать функцию, выбрав какую-то целочисленную точку $$$y$$$.
Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов тестовых данных.
Первая строка набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество точек в массиве $$$x$$$.
Вторая строка набора содержит $$$n$$$ целых чисел $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_i \le 10^9$$$), где $$$x_i$$$ — $$$i$$$-я точка в массиве $$$x$$$.
Все точки в массиве $$$x$$$ различны, а массив $$$x$$$ отсортирован в возрастающем порядке (другими словами, $$$x_1 < x_2 < \ldots < x_n$$$).
Сумма $$$n$$$ по всем наборам тестовых данных в тесте не превосходит $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).
Для каждого набора тестовых данных выведите YES, если возможно найти какую-то целочисленную точку $$$y$$$, которая сломает функцию, и NO иначе.
7 2 1 3 2 1 100 3 1 50 101 2 1 1000000000 2 1 999999999 6 1 2 5 7 9 11 6 1 2 5 8 9 12
YES NO NO NO YES YES NO
В первом наборе входных данных примера из условия функция не может обработать точку $$$y = 2$$$.
В пятом наборе входных данных примера из условия функция не может обработать точку $$$y = 500000000$$$.
В шестом наборе входных данных примера из условия функция не может обработать точку $$$y = 10$$$.
Название |
---|