В далёком королевстве, где магия и реальность переплетаются, существует легенда о бесконечной цепи магических костяшек домино. Эти костяшки выстроены вдоль старинной дороги и обладают особыми свойствами. Каждая костяшка расположена на координате xi и имеет магическую силу, равную hi, определяющую её способность влиять на другие костяшки. Однажды юная волшебница Оля решила испытать силу этой цепи и толкнула первую костяшку. При падении костяшка выпускает магический импульс, который распространяется вперёд и заставляет падать все костяшки, находящиеся на координатах не больше, чем xi+hi. Каждая следующая костяшка, попавшая под действие импульса, действует аналогично, создавая эффект магической цепной реакции. Строго говоря, при воздействии на костяшку на позиции xi будут задеты, и как следствие, выпустят уже свой магический импульс, все костяшки с такими координатами xj, что xi+hi≤xj. К Оле решила присоединиться её подруга Яло. Она решила проверить, как поведут себя костяшки, если их толкнуть с другой стороны. Девочка толкнула последнюю костяшку, которая находилась на самой правой позиции. И вот что произошло. Самая правая костяшка, которую толкнула Яло, выпустила магический импульс, который распространяется назад, заставляя падать костяшки, находящиеся на координатах не больших чем xi−hi. Иными словами, если костяшка на позиции xi падает, то она сама выпускает магический импульс, под воздействие которого попадают все костяшки, чьи координаты удовлетворяют условию xi−hi>xj. Таким образом, костяшки, падающие с одной стороны, могут встретиться с костяшками, падающими с другой, при этом магические импульсы с двух сторон продолжат распространяться так же, как и до встречи. Теперь обе цепные реакции Оли и Яло идут навстречу друг другу, и вы очень хотите узнать, сколько же суммарно костяшек упадёт. Формат входных данных Первая строка содержит одно целое число N (2≤N≤105) количество волшебных костяшек. Следующие 2N строк содержат два набора целых чисел: Первые N строк содержат координаты костяшек xi (0≤xi≤109). Следующие N строк содержат магическую силу костяшек hi (0≤hi≤109). Гарантируется, что координаты образуют возрастающую последовательность (никакие две костяшки не имеют одинаковых координат). Формат выходных данных Выведите одно целое число общее число костяшек, которые упадут после удара. Система оценки Решения, правильно работающие при n≤1000, будут оценены не менее чем в 50 баллов. Замечание В первом примере первая костяшка, которую толкнула Оля, не достанет до следующей (т.к. её «высота» составляет всего 2), а поэтому от импульса слева упадёт только она. Стоящая на координате 8 костяшка, которую толкнула Яло, заденет костяшку, стоящую на координате 7, которая, в свою очередь, не заденет костяшку на координате 5, т.к. её «высота» равна 1. На рисунке ниже показаны костяшки до того, как их толкнули, и их итоговое состояние (красным отмечены места, которые «задела» хотя бы одна костяшка). Ввод 4 1 5 7 8 2 3 1 1 Вывод 3

Question 1

Задача Задача №1980650

А

Аноним

23 октября 2024 06:20 · публичный вопрос

А

Аноним 23 октября 2024 06:20

В далёком королевстве, где магия и реальность переплетаются, существует легенда о бесконечной цепи магических костяшек домино. Эти костяшки выстроены вдоль старинной дороги и обладают особыми свойствами. Каждая костяшка расположена на координате xi и имеет магическую силу, равную hi, определяющую её способность влиять на другие костяшки. Однажды юная волшебница Оля решила испытать силу этой цепи и толкнула первую костяшку. При падении костяшка выпускает магический импульс, который распространяется вперёд и заставляет падать все костяшки, находящиеся на координатах не больше, чем xi+hi. Каждая следующая костяшка, попавшая под действие импульса, действует аналогично, создавая эффект магической цепной реакции. Строго говоря, при воздействии на костяшку на позиции xi будут задеты, и как следствие, выпустят уже свой магический импульс, все костяшки с такими координатами xj, что xi+hi≤xj. К Оле решила присоединиться её подруга Яло. Она решила проверить, как поведут себя костяшки, если их толкнуть с другой стороны. Девочка толкнула последнюю костяшку, которая находилась на самой правой позиции. И вот что произошло. Самая правая костяшка, которую толкнула Яло, выпустила магический импульс, который распространяется назад, заставляя падать костяшки, находящиеся на координатах не больших чем xi−hi. Иными словами, если костяшка на позиции xi падает, то она сама выпускает магический импульс, под воздействие которого попадают все костяшки, чьи координаты удовлетворяют условию xi−hi>xj. Таким образом, костяшки, падающие с одной стороны, могут встретиться с костяшками, падающими с другой, при этом магические импульсы с двух сторон продолжат распространяться так же, как и до встречи. Теперь обе цепные реакции Оли и Яло идут навстречу друг другу, и вы очень хотите узнать, сколько же суммарно костяшек упадёт. Формат входных данных Первая строка содержит одно целое число N (2≤N≤105) количество волшебных костяшек. Следующие 2N строк содержат два набора целых чисел: Первые N строк содержат координаты костяшек xi (0≤xi≤109). Следующие N строк содержат магическую силу костяшек hi (0≤hi≤109). Гарантируется, что координаты образуют возрастающую последовательность (никакие две костяшки не имеют одинаковых координат). Формат выходных данных Выведите одно целое число общее число костяшек, которые упадут после удара. Система оценки Решения, правильно работающие при n≤1000, будут оценены не менее чем в 50 баллов. Замечание В первом примере первая костяшка, которую толкнула Оля, не достанет до следующей (т.к. её «высота» составляет всего 2), а поэтому от импульса слева упадёт только она. Стоящая на координате 8 костяшка, которую толкнула Яло, заденет костяшку, стоящую на координате 7, которая, в свою очередь, не заденет костяшку на координате 5, т.к. её «высота» равна 1. На рисунке ниже показаны костяшки до того, как их толкнули, и их итоговое состояние (красным отмечены места, которые «задела» хотя бы одна костяшка). Ввод 4 1 5 7 8 2 3 1 1 Вывод 3

Answer

Чтобы решить задачу о магических костяшках домино, нам необходимо понять, как распространяются импульсы от каждой стороны.

Понимание условий:
- Первая волшебница Оля толкает первую костяшку слева направо. Она создает импульс, который будет падать костяшки с координатами, не превышающими xi + hi.
- Вторая волшебница Яло толкает последнюю костяшку справа налево. Импульс от неё будет падать костяшки, чьи координаты не больше xi - hi.
Алгоритм:
- Проанализируем, какие костяшки упадут при первом толчке (от Оли).
- Затем проанализируем, какие костяшки упадут при втором толчке (от Яло).
- Будем использовать два указателя, чтобы отслеживать, какие костяшки были сброшены.
Реализация:
- Создадим два массива, чтобы отслеживать сброшенные костяшки – от Оли и от Яло.
- Начнем с первого элемента (для Оли) и проанализируем, заденет ли текущая костяшка следующую. Если да, то считаем её и продвигаемся дальше. Это делаем до тех пор, пока костяшки будут падать.
- Аналогично повторяем процесс для костяшек, которые толкнула Яло, двигаясь вправо.
Сложность:
- При оптимальном подходе с использованием двух указателей общая сложность будет O(N), так как каждая костяшка будет проверяться не более одного раза.

Пример реализации на Python:

N = int(input().strip())
x = [int(input().strip()) for _ in range(N)]
h = [int(input().strip()) for _ in range(N)]

# Массив, который будет хранить информацию о том, упала ли костяшка
fallen = [False] * N

# Толкание от Оли
for i in range(N):
    if not fallen[i]:  # Если костяшка ещё не упала
        fallen[i] = True  # Она упадёт
        reach = x[i] + h[i]  # Максимальная координата, до которой можно дотянуться
        # Найдем, до какой костяшки она сможет дотянуться
        while i + 1 < N and x[i + 1] <= reach:
            i += 1
            fallen[i] = True  # Эта костяшка также упадёт

# Толкание от Яло
for i in range(N - 1, -1, -1):
    if not fallen[i]:  # Если костяшка ещё не упала
        fallen[i] = True  # Она упадёт
        reach = x[i] - h[i]  # Максимальная координата, до которой можно дотянуться
        # Найдем, до какой костяшки она сможет дотянуться
        while i - 1 >= 0 and x[i - 1] >= reach:
            i -= 1
            fallen[i] = True  # Эта костяшка также упадёт

# Подсчет упавших костяшек
result = sum(fallen)  # Суммируем по массиву fallen, чтобы узнать количество упавших костяшек
print(result)

Вывод:
- После выполнения программы, вы получите общее количество костяшек, которые упадут после толчка обеих волшебниц.

Такой подход обеспечит эффективное решение данной задачи, и с помощью алгоритмов вы сможете определить, сколько костяшек упадёт в вашем случае.

Question 2

В далёком королевстве, где магия и реальность переплетаются, существует легенда о бесконечной цепи магических костяшек домино. Эти костяшки выстроены вдоль старинной дороги и обладают особыми свойствами. Каждая костяшка расположена на координате xi и имеет магическую силу, равную hi, определяющую её способность влиять на другие костяшки. Однажды юная волшебница Оля решила испытать силу этой цепи и толкнула первую костяшку. При падении костяшка выпускает магический импульс, который распространяется вперёд и заставляет падать все костяшки, находящиеся на координатах не больше, чем xi+hi. Каждая следующая костяшка, попавшая под действие импульса, действует аналогично, создавая эффект магической цепной реакции. Строго говоря, при воздействии на костяшку на позиции xi будут задеты, и как следствие, выпустят уже свой магический импульс, все костяшки с такими координатами xj, что xi+hi≤xj. К Оле решила присоединиться её подруга Яло. Она решила проверить, как поведут себя костяшки, если их толкнуть с другой стороны. Девочка толкнула последнюю костяшку, которая находилась на самой правой позиции. И вот что произошло. Самая правая костяшка, которую толкнула Яло, выпустила магический импульс, который распространяется назад, заставляя падать костяшки, находящиеся на координатах не больших чем xi−hi. Иными словами, если костяшка на позиции xi падает, то она сама выпускает магический импульс, под воздействие которого попадают все костяшки, чьи координаты удовлетворяют условию xi−hi>xj. Таким образом, костяшки, падающие с одной стороны, могут встретиться с костяшками, падающими с другой, при этом магические импульсы с двух сторон продолжат распространяться так же, как и до встречи. Теперь обе цепные реакции Оли и Яло идут навстречу друг другу, и вы очень хотите узнать, сколько же суммарно костяшек упадёт. Формат входных данных Первая строка содержит одно целое число N (2≤N≤105) количество волшебных костяшек. Следующие 2N строк содержат два набора целых чисел: Первые N строк содержат координаты костяшек xi (0≤xi≤109). Следующие N строк содержат магическую силу костяшек hi (0≤hi≤109). Гарантируется, что координаты образуют возрастающую последовательность (никакие две костяшки не имеют одинаковых координат). Формат выходных данных Выведите одно целое число общее число костяшек, которые упадут после удара. Система оценки Решения, правильно работающие при n≤1000, будут оценены не менее чем в 50 баллов. Замечание В первом примере первая костяшка, которую толкнула Оля, не достанет до следующей (т.к. её «высота» составляет всего 2), а поэтому от импульса слева упадёт только она. Стоящая на координате 8 костяшка, которую толкнула Яло, заденет костяшку, стоящую на координате 7, которая, в свою очередь, не заденет костяшку на координате 5, т.к. её «высота» равна 1. На рисунке ниже показаны костяшки до того, как их толкнули, и их итоговое состояние (красным отмечены места, которые «задела» хотя бы одна костяшка). Ввод 4 1 5 7 8 2 3 1 1 Вывод 3

Answer

Чтобы решить задачу о магических костяшках домино, нам необходимо понять, как распространяются импульсы от каждой стороны. 1. **Понимание условий**: - Первая волшебница Оля толкает первую костяшку слева направо. Она создает импульс, который будет падать костяшки с координатами, не превышающими `xi + hi`. - Вторая волшебница Яло толкает последнюю костяшку справа налево. Импульс от неё будет падать костяшки, чьи координаты не больше `xi - hi`. 2. **Алгоритм**: - Проанализируем, какие костяшки упадут при первом толчке (от Оли). - Затем проанализируем, какие костяшки упадут при втором толчке (от Яло). - Будем использовать два указателя, чтобы отслеживать, какие костяшки были сброшены. 3. **Реализация**: - Создадим два массива, чтобы отслеживать сброшенные костяшки – от Оли и от Яло. - Начнем с первого элемента (для Оли) и проанализируем, заденет ли текущая костяшка следующую. Если да, то считаем её и продвигаемся дальше. Это делаем до тех пор, пока костяшки будут падать. - Аналогично повторяем процесс для костяшек, которые толкнула Яло, двигаясь вправо. 4. **Сложность**: - При оптимальном подходе с использованием двух указателей общая сложность будет O(N), так как каждая костяшка будет проверяться не более одного раза. 5. **Пример реализации на Python**: ```python N = int(input().strip()) x = [int(input().strip()) for _ in range(N)] h = [int(input().strip()) for _ in range(N)] # Массив, который будет хранить информацию о том, упала ли костяшка fallen = [False] * N # Толкание от Оли for i in range(N): if not fallen[i]: # Если костяшка ещё не упала fallen[i] = True # Она упадёт reach = x[i] + h[i] # Максимальная координата, до которой можно дотянуться # Найдем, до какой костяшки она сможет дотянуться while i + 1 < N and x[i + 1] <= reach: i += 1 fallen[i] = True # Эта костяшка также упадёт # Толкание от Яло for i in range(N - 1, -1, -1): if not fallen[i]: # Если костяшка ещё не упала fallen[i] = True # Она упадёт reach = x[i] - h[i] # Максимальная координата, до которой можно дотянуться # Найдем, до какой костяшки она сможет дотянуться while i - 1 >= 0 and x[i - 1] >= reach: i -= 1 fallen[i] = True # Эта костяшка также упадёт # Подсчет упавших костяшек result = sum(fallen) # Суммируем по массиву fallen, чтобы узнать количество упавших костяшек print(result) ``` 6. **Вывод**: - После выполнения программы, вы получите общее количество костяшек, которые упадут после толчка обеих волшебниц. Такой подход обеспечит эффективное решение данной задачи, и с помощью алгоритмов вы сможете определить, сколько костяшек упадёт в вашем случае.