Помогите решить задачу на языке с++/питоне
Вот задача:
Ограничение по времени 1 сек
Ограничение по памяти 256мб
У хомяка Даттона n
переключателей, контролирующих свет. Он боится темноты, поэтому просит вас написать вас программу, которая поможет ему.
Его дом выглядит как коридор , состоящий из n
комнат, соединенных в ряд. В каждой комнате есть лампочка, которая изначально может быть включена «1» или выключена «0».
Начальные состояния лампочек описаны массивом L
. Даттон часто просыпается ночью, чтобы пойти поесть, поэтому перед сном хочет переключить все лампочки так, чтобы он мог пройти по коридору из своей спальни на кухню так, чтобы в каждой комнате, по которой придется пройти, лампочка была включена.
Так как он хочет сэкономить на электричестве, то во всех остальных комнатах свет должен быть выключен.
Кухня находится в комнате с номером A
. Если A=0
, то он может попасть на кухню напрямую из спальни, и все лампочки в коридоре должны быть выключены. Если A>0
, то в комнатах с номерами с 1
по A
лампочки должны остаться включенными.
Переключать лампочки он может следующим образом: выбрать k
подряд идущих комнат коридора, во всех комнатах из k
выбранных, если лампочки были включены, они станут выключенными, и наоборот. То есть «0» будут изменяться на «1», а «0» на «1».
Даттон устал после тяжелого рабочего дня, поэтому хочет сделать как можно меньше таких переключений.
Ваша задача — написать программу, которая должна найти минимальное количество действий, которые Даттону нужно сделать или сказать, что его просьбу выполнить невозможно.
n < 100000
k < n
Вот примеры
Входные данные:
10 3
1 0 0 0 0 0 1 1 1 0
1
Выходные данные:
1
Входные данные:
10 3
1 0 0 0 1 1 0 1 1 0
1
Выходные данные:
2
Для решения этой задачи мы можем использовать жадный алгоритм. Мы будем проходить по массиву состояний лампочек и переключать группы лампочек по мере необходимости, чтобы достичь желаемого состояния.
Основная идея заключается в том, что мы будем проходить по массиву и, когда найдем лампочку, которая должна быть включена, но выключена, мы будем переключать группу из k лампочек, начиная с текущей позиции. Это будет продолжаться до тех пор, пока мы не достигнем позиции A, где все лампочки должны быть включены.
Вот реализация на Python:
def min_switches(n, k, L, A):
# Если A == 0, все лампочки должны быть выключены
if A == 0:
return L.count(1) # Считаем количество включенных лампочек
# Устанавливаем целевое состояние
target = [1] * A + [0] * (n - A)
# Количество переключений
switches = 0
# Проходим по всем лампочкам от 0 до n - k
for i in range(n - k + 1):
if L[i] != target[i]:
# Если состояние не совпадает, переключаем k лампочек
switches += 1
for j in range(k):
L[i + j] = 1 - L[i + j] # Переключаем состояние
# Проверяем, совпадает ли оставшаяся часть с целевым состоянием
if L[:A] == target[:A] and L[A:] == target[A:]:
return switches
else:
return -1 # Невозможно выполнить задачу
# Пример использования
n, k = map(int, input().split())
L = list(map(int, input().split()))
A = int(input())
result = min_switches(n, k, L, A)
print(result)
▎Объяснение кода:
1. Входные данные: Мы считываем количество комнат n, размер переключаемой группы k, текущее состояние лампочек L и номер комнаты A.
2. Целевое состояние: Если A == 0, то все лампочки должны быть выключены. В противном случае мы создаем целевое состояние, где первые A лампочек должны быть включены, а остальные выключены.
3. Переключения: Мы проходим по массиву L и, если состояние лампочки не совпадает с целевым, переключаем k лампочек, начиная с текущей позиции.
4. Проверка результата: В конце проверяем, совпадает ли текущее состояние с целевым. Если да, возвращаем количество переключений, иначе возвращаем -1 (невозможно выполнить задачу).
▎Сложность:
• Временная сложность: O(n)
• Пространственная сложность: O(1) (по сути, мы модифицируем массив на месте)
Этот алгоритм эффективно решает задачу, соблюдая ограничения по времени и памяти.
