1. Главная
  2. Библиотека
  3. Теория вероятностей
  4. В родном городе Бобритто Бандито находится бесконечное количество домов на бесконечной числовой прямой, с домами на ...,−2...

В родном городе Бобритто Бандито находится бесконечное количество домов на бесконечной числовой прямой, с домами на ...,−2,−1,0,1,2,... . В день 0 он начал эпидемию, заразив несчастных жителей дома 0. Каждый следующий день эпидемия распространяется на

«В родном городе Бобритто Бандито находится бесконечное количество домов на бесконечной числовой прямой, с домами на ...,−2,−1,0,1,2,... . В день 0 он начал эпидемию, заразив несчастных жителей дома 0. Каждый следующий день эпидемия распространяется на»
  • Теория вероятностей

Условие:

В родном городе Бобритто Бандито находится бесконечное количество домов на бесконечной числовой прямой, с домами на …,−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′
на новой строке. Если существует несколько решений, выведите любое.

Пример
Входные данныеСкопировать
4
4 2 -2 2
4 1 0 4
3 3 -1 2
9 8 -6 3
Выходные данныеСкопировать
-1 1
0 1
-1 2
-5 3
Примечание
В первом примере возможно, что на 1
-й, 2
-й и 3
-й дни отрезками затронутых домов являлись [−1,0]
, [−1,1]
и [−2,1]
, соответственно. Следовательно, [−1,1]
является допустимым выводом

Решение:

Для решения задачи нам нужно понять, как эпидемия распространяется от дома 0. Каждый день она может захватывать один новый дом слева или справа от текущего диапазона зараженных домов. Дано, что на n-й день заражен отрезок [l, r], где r - l = n. Это означает, что на n-й день эпидемия охватывает n + 1 домов, начиная с l и заканчивая r. На m-й день (где m ≤ n) мы можем выбрать любой отрезок [l, r], который соответствует правилам распространения эпидемии. Мы можем сделать это, уменьшая дли...

Не нашел нужную задачу?

Воспользуйся поиском

Выбери предмет