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

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

1. На m-й день длина отрезка будет равна m, т.е. r - l = m. 2. Мы можем выбрать l равным l + (n - m) (это смещение от l на количество дней, которые мы откатываем назад). 3. Соответственно, r будет равно l + m. Таким образом, мы можем вычислить l и r следующим образом: - l = l + (n - m) - r = l + m = l + (n - m) + m = l + n Теперь давайте реализуем это в коде: Если вы введете данные: Вы получите: Этот код будет корректно обрабатывать все наборы данных и выводить допустимые отрезки для m-го дня.

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

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

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