Условие:
В родном городе Бобритто Бандито находится бесконечное количество домов на бесконечной числовой прямой, с домами на …,−2,−1,0,1,2,…
. В день 0
он начал эпидемию, заразив несчастных жителей дома 0
. Каждый следующий день эпидемия распространяется на ровно один здоровый дом, соседствующий с зараженным домом. Можно показать, что каждый день зараженные дома образуют непрерывный отрезок.
Обозначим отрезок, начинающийся в l
-м доме и заканчивающийся в r
-м, как [l,r]
. Вам известно, что спустя n
дней оказался заражённым отрезок [l,r]
. Найдите любой такой отрезок [l′,r′]
, что в m
-й день (m≤n
) мог быть заражён именно этот отрезок.
Входные данные
Первая строка содержит целое число t
(1≤t≤100
) – количество независимых наборов входных данных.
Единственная строка каждого набора содержит четыре целых числа n
, m
, l
и r
(1≤m≤n≤2000,−n≤l≤0≤r≤n,r−l=n
).
Выходные данные
Для каждого набора входных данных выведите два целых числа l′
и r′
на новой строке. Если существует несколько решений, выведите любое.
Примечание
В первом примере возможно, что на 1
-й, 2
-й и 3
-й дни отрезками затронутых домов являлись [−1,0]
, [−1,1]
и [−2,1]
, соответственно. Следовательно, [−1,1]
является допустимым выводом.
Решение:
Для решения данной задачи мы будем использовать свойства распространения эпидемии и ограничения, заданные в условии. Давайте разберем шаги, которые нам нужно выполнить.
Шаг 1: Понимание задачи
Мы знаем, что на деньn эпидемия охватила отрезок [l, r], где r - l = n. Это означает, что на день эпидемия распространилась на домов (включая оба конца отрезка).
Нам нужно найти отрезок , который мог быть заражен на день , где .
На день эпидемия могла охватить отрезок, который:
1. Начинается не дальше, чем на домов от (поскольку на день был заражен только дом ).
2. Заканчивается не дальше, чем на домов от .
Таким образом, отрезок должен удовлетворять следующим условиям:
- должно быть не меньше (это минимально возможный левый конец, если мы предположим, что эпидемия двигалась влево).
- должно быть не больше (это максимально возможный правый конец, если мы предположим, что эпидемия двигалась вправо).
Мы можем выбрать отрезок как:
-
-
Это гарантирует, что отрезок будет находиться в пределах на день , и будет корректным на день .
Теперь мы можем реализовать это в коде. Для каждого набора входных данных мы просто вычислим и и выведем их.
Теперь давайте проверим, что полученные значения и соответствуют условиям задачи:
- не выходит за пределы и .
- не превышает .
Таким образом, мы можем быть уверены, что наш ответ корректен.
Теперь мы можем вывести результаты для каждого теста, используя предложенный алгоритм.