Кегельбан
Отмечаем покрытие интервалами сбитых кеглей.
Как к ней подойти
Потренируйтесь хранить последовательность значений и обращаться к нужным элементам списка.
Список хранит элементы в определённом порядке. Прежде чем менять его, решите, нужны ли исходные индексы и можно ли пройти по данным один раз. При удалении элементов будьте внимательны: индексы сдвигаются.
Добавляем начало и конец каждого интервала. Префиксная сумма показывает, сколько бросков покрыли данную кеглю; положительное значение означает падение.
Проверьте перед запуском
- Ввод нумерует кегли с 1, список — с 0.
- Правый конец интервала включён.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Разностный массив
Добавляем начало и конец каждого интервала. Префиксная сумма показывает, сколько бросков покрыли данную кеглю; положительное значение означает падение.
n, k = map(int, input().split())
difference = [0] * (n + 1)
for _ in range(k):
left, right = map(int, input().split())
difference[left - 1] += 1
difference[right] -= 1
active = 0
result = []
for i in range(n):
active += difference[i]
result.append('.' if active else 'I')
print(''.join(result))
Время: O(n + k). Память: O(n).
Другой способ: Явная отметка каждой сбитой кегли
Простой подход напрямую воспроизводит каждый бросок. При длинных перекрывающихся интервалах он повторяет одну работу много раз.
n, k = map(int, input().split())
pins = ['I'] * n
for _ in range(k):
left, right = map(int, input().split())
for i in range(left - 1, right):
pins[i] = '.'
print(''.join(pins))
Время: O(n + сумма длин интервалов), максимум O(nk + n). Память: O(n).