Тайна магического домино Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В далёком королевстве, где магия и реальность переплетаются, существует легенда о…
Тайна магического домино Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В далёком королевстве, где магия и реальность переплетаются, существует легенда о бесконечной цепи магических костяшек домино. Эти костяшки выстроены вдоль старинной дороги и обладают особыми свойствами. Каждая костяшка расположена на координате х; и имеет магическую силу, равную h,, определяющую её способность влиять на другие костяшки. Однажды юная волшебница Оля решила испытать силу этой цепи и толкнула первую костяшку. При падении костяшка выпускает магический импульс, который распространяется вперёд и заставляет падать все костяшки, находящиеся на координатах не больше, чем х; + h;. Каждая следующая костяшка, попавшая под действие импульса, действует аналогично, создавая эффект магической цепной реакции. Строго говоря, при воздействии на костяшку на позиции х, будут задеты, и как следствие, выпустят уже свой магический импульс, все костяшки с такими координатами х ;, Что Xi + hi ≤ xj. К Оле решила присоединиться её подруга Яло. Она решила проверить, как поведут себя костяшки, если их толкнуть с другой стороны. Девочка толкнула последнюю костяшку, которая находилась на самой правой позиции. И вот что произошло. Самая правая костяшка, которую толкнила Яло, выпустила магический импульс, который распространяется назад, заставляя падать костяшки, находящиеся на координатах не больших чем 2; - h. Иными словами, если костяшка на позиции х; падает, то она сама выпускает магический импульс, под воздействие которого попадают все костяшки, чьи координаты удовлетворяют условию хі - пі > Х; Таким образом, костяшки, падающие с одной стороны, могут встретиться с костяшками, падающими с другой, при этом магические импульсы с двух сторон продолжат распространяться так же, как и до встречи. Теперь обе цепные реакции Оли и Яло идут навстречу друг другу, и вы очень хотите узнать, сколько же суммарно костяшек упадёт. Формат входных данных Первая строка содержит одно целое число N (2 ≤ N ≤ 105) — количество волшебных костяшек. Следующие 2N строк содержат два набора целых чисел: Первые N строк содержат координаты костяшек х; (0 ≤ х; ≤ 10°). Следующие N строк содержат магическую силу костяшек h, (0 ≤ hi ≤ 10%). Гарантируется, что координаты образуют возрастающую последовательность никакие две костяшки не имеют одинаковых координат). Формат выходных данных Выведите одно целое число - общее число костяшек, которые упадут после удара. Система оценки Решения, правильно работающие при п ≤ 1000, будут оценены не менее чем в 50 баллов. Замечание В первом примере первая костяшка, которую толкнула Оля, не достанет до следующей (т.к. её «высота» составляет всего 2), а поэтому от импульса слева упадёт только она. Стоящая на координате 8 костяшка, которую толкнула Яло, заденет костяшку, стоящую на координате 7, которая, в свою очередь, не заденет костяшку на координате 5, т.к. её «высота» равна 1. На рисунке ниже показаны костяшки до того, как их толкнули, и их итоговое состояние (красным отмечены места, которые «задела» хотя бы одна костяшка). Ввод 4 1 5 7 8 2 3 1 1 Вывод 3
Привет! Давай разберёмся с этой задачей пошагово.
Понимание задачи:
У нас есть массив доминошек с координатами \(x_1, x_2, ..., x_N\) и каждой доминошке соответствует её магическая сила \(h_1, h_2, ..., h_N\). Когда толкается первая доминошка, она начинает цепную реакцию, толкая доминошки вперёд, до тех пор, пока \(x_i + h_i \geq x_j\). Толкнув последнюю доминошку, она начинает цепную реакцию назад, до тех пор, пока \(x_j - h_j \leq x_i\).
Цель: Узнать общее количество доминошек, которые упадут.
Решение:
Считывание данных:
- У нас есть число \(N\) и два массива координат и сил.
Имитация падения слева направо:
- Начнём с первой доминошки. Проверяем, насколько далеко распространяется её воздействие. Если следующее домино находится в зоне воздействия текущей, оно тоже падает и распространяет своё воздействие.
Имитация падения справа налево:
- Начнём с последней доминошки и аналогично проверяем её воздействие назад.
Подсчёт уникальных упавших доминошек:
- Объединяем результаты падения слева и справа, чтобы посчитать общее количество упавших доминошек.
def count_fallen_dominoes(n, x, h):
# Левое падение
fallen_from_left = [False] * n
max_reach_from_left = x[0] + h[0]
fallen_from_left[0] = True
for i in range(1, n):
if x[i] <= max_reach_from_left:
fallen_from_left[i] = True
max_reach_from_left = max(max_reach_from_left, x[i] + h[i])
# Правое падение
fallen_from_right = [False] * n
max_reach_from_right = x[n-1] - h[n-1]
fallen_from_right[n-1] = True
for i in range(n-2, -1, -1):
if x[i] >= max_reach_from_right:
fallen_from_right[i] = True
max_reach_from_right = min(max_reach_from_right, x[i] - h[i])
# Подсчёт упавших
total_fallen = 0
for i in range(n):
if fallen_from_left[i] or fallen_from_right[i]:
total_fallen += 1
return total_fallen
# Пример использования
n = 4
x = [1, 5, 7, 8]
h = [2, 3, 1, 1]
print(count_fallen_dominoes(n, x, h)) # вывод: 3
Теперь ты знаешь, как решать эту задачу! Если есть вопросы, не стесняйся спрашивать.
