В далеком королевстве где магия и реальность переплетаются существует легенда о бесконечной цепи магических костяшек домино. Эти костяшки выстроены вдоль старинной дороги и обладают особыми свойствами. Каждая костяшка расположена на координате 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. На рисунке ниже показаны костяшки до того, как их толкнули, и их итоговое состояние (красным отмечены места, которые «задела» хотя бы одна костяшка).

Question 1

Задача Задача №1992089

А

Аноним

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

А

Аноним 23 октября 2024 17:39

В далеком королевстве где магия и реальность переплетаются существует легенда о бесконечной цепи магических костяшек домино. Эти костяшки выстроены вдоль старинной дороги и обладают особыми свойствами. Каждая костяшка расположена на координате 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. На рисунке ниже показаны костяшки до того, как их толкнули, и их итоговое состояние (красным отмечены места, которые «задела» хотя бы одна костяшка).

Answer

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

Шаги решения:

Ввод данных: Нам нужно считать количество костяшек \( N \) и координаты \( x_i \) и магическую силу \( h_i \).
Распространение импульсов:
- Начнем с того, что когда Оля толкает первую костяшку, нам нужно определить, какие костяшки упадут от её воздействия. Это делается, пока текущая костяшка может "достать" следующую.
- Аналогично, когда Яло толкает последнюю костяшку, мы будем определять, какие костяшки упадут, пока костяшка может воздействовать на предыдущую.
Моделирование падения:
- Создадим два массива: один для отслеживания падения костяшек при толчке Оли (слева направо) и другой для толчка Яло (справа налево).
- Для каждой костяшки определим диапазон, в который может распространяться её магическая сила, и будем учитывать, какие костяшки могут упасть.
Подсчет падений: После того, как мы пройдём обе стороны, мы должны объединить результаты и подсчитать, сколько уникальных костяшек упадёт при взаимодействии обеих цепных реакций.

Пример кода на Python:

n = int(input())
x = []
h = []

# Чтение координат костяшек
for i in range(n):
    x.append(int(input()))

# Чтение магической силы костяшек
for i in range(n):
    h.append(int(input()))

# Массив для отслеживания падающих костяшек
fallen = [False] * n

# Толкнем сначала костяшки с левой стороны
right_most = 0
for i in range(n):
    if not fallen[i]:  # Если костяшка ещё не упала
        right_most = max(right_most, x[i] + h[i])  # Максимальная координата, которую мы можем достичь
        for j in range(i, n):
            if x[j] <= right_most:
                fallen[j] = True
            else:
                break

# Толкнем костяшки с правой стороны
left_most = 0
for i in range(n - 1, -1, -1):
    if not fallen[i]:  # Если костяшка ещё не упала
        left_most = max(left_most, x[i] - h[i])  # Минимальная координата, которую мы можем достичь
        for j in range(i, -1, -1):
            if x[j] >= left_most:
                fallen[j] = True
            else:
                break

# Подсчет количества упавших костяшек
total_fallen = sum(fallen)

print(total_fallen)

Объяснение кода:

Мы используем два цикла для падения костяшек: один идёт слева направо, другой — справа налево.
Массив fallen отмечает, какие костяшки уже упали.
В конце подсчитывается общее количество падающих костяшек, используя функцию sum.

Заключение:

Данный алгоритм будет работать эффективно для больших значений \( N \) до 100,000, поскольку он имеет линейную сложность. Используя этот метод, вы сможете выяснить, сколько всего костяшек упадёт, что позволит вам понять магическую реакцию в этом волшебном мире.

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. На рисунке ниже показаны костяшки до того, как их толкнули, и их итоговое состояние (красным отмечены места, которые «задела» хотя бы одна костяшка).

Answer

Для решения этой задачи необходимо понять, как магические костяшки домино взаимодействуют друг с другом, когда их толкают с обоих концов. Мы будем реализовывать процесс распространения магических импульсов от обеих сторон и определим, сколько костяшек в итоге упадёт. ### Шаги решения: 1. **Ввод данных**: Нам нужно считать количество костяшек \( N \) и координаты \( x_i \) и магическую силу \( h_i \). 2. **Распространение импульсов**: - Начнем с того, что когда Оля толкает первую костяшку, нам нужно определить, какие костяшки упадут от её воздействия. Это делается, пока текущая костяшка может "достать" следующую. - Аналогично, когда Яло толкает последнюю костяшку, мы будем определять, какие костяшки упадут, пока костяшка может воздействовать на предыдущую. 3. **Моделирование падения**: - Создадим два массива: один для отслеживания падения костяшек при толчке Оли (слева направо) и другой для толчка Яло (справа налево). - Для каждой костяшки определим диапазон, в который может распространяться её магическая сила, и будем учитывать, какие костяшки могут упасть. 4. **Подсчет падений**: После того, как мы пройдём обе стороны, мы должны объединить результаты и подсчитать, сколько уникальных костяшек упадёт при взаимодействии обеих цепных реакций. ### Пример кода на Python: ```python n = int(input()) x = [] h = [] # Чтение координат костяшек for i in range(n): x.append(int(input())) # Чтение магической силы костяшек for i in range(n): h.append(int(input())) # Массив для отслеживания падающих костяшек fallen = [False] * n # Толкнем сначала костяшки с левой стороны right_most = 0 for i in range(n): if not fallen[i]: # Если костяшка ещё не упала right_most = max(right_most, x[i] + h[i]) # Максимальная координата, которую мы можем достичь for j in range(i, n): if x[j] <= right_most: fallen[j] = True else: break # Толкнем костяшки с правой стороны left_most = 0 for i in range(n - 1, -1, -1): if not fallen[i]: # Если костяшка ещё не упала left_most = max(left_most, x[i] - h[i]) # Минимальная координата, которую мы можем достичь for j in range(i, -1, -1): if x[j] >= left_most: fallen[j] = True else: break # Подсчет количества упавших костяшек total_fallen = sum(fallen) print(total_fallen) ``` ### Объяснение кода: - Мы используем два цикла для падения костяшек: один идёт слева направо, другой — справа налево. - Массив `fallen` отмечает, какие костяшки уже упали. - В конце подсчитывается общее количество падающих костяшек, используя функцию `sum`. ### Заключение: Данный алгоритм будет работать эффективно для больших значений \( N \) до 100,000, поскольку он имеет линейную сложность. Используя этот метод, вы сможете выяснить, сколько всего костяшек упадёт, что позволит вам понять магическую реакцию в этом волшебном мире.