Помогите решить задачу на с++/питоне
Вот задача:
У хомяка Даттона n
переключателей, контролирующих свет. Он боится темноты, поэтому просит вас написать вас программу, которая поможет ему.
Его дом выглядит как коридор , состоящий из n
комнат, соединенных в ряд. В каждой комнате есть лампочка, которая изначально может быть включена «1» или выключена «0».
Начальные состояния лампочек описаны массивом L
. Даттон часто просыпается ночью, чтобы пойти поесть, поэтому перед сном хочет переключить все лампочки так, чтобы он мог пройти по коридору из своей спальни на кухню так, чтобы в каждой комнате, по которой придется пройти, лампочка была включена.
Так как он хочет сэкономить на электричестве, то во всех остальных комнатах свет должен быть выключен.
Кухня находится в комнате с номером A
. Если A=0
, то он может попасть на кухню напрямую из спальни, и все лампочки в коридоре должны быть выключены. Если A>0
, то в комнатах с номерами с 1
по A
лампочки должны остаться включенными.
Переключать лампочки он может следующим образом: выбрать k
подряд идущих комнат коридора, во всех комнатах из k
выбранных, если лампочки были включены, они станут выключенными, и наоборот. То есть «0» будут изменяться на «1», а «0» на «1».
Даттон устал после тяжелого рабочего дня, поэтому хочет сделать как можно меньше таких переключений.
Ваша задача — написать программу, которая должна найти минимальное количество действий, которые Даттону нужно сделать или сказать, что его просьбу выполнить невозможно.
Вот примеры
Входные данные:
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
def min_switches(n, k, L, A):
# Если A == 0, то все лампочки должны быть выключены
# Если A > 0, то лампочки с 1 по A должны быть включены, а остальные - выключены
target = [0] * n
if A > 0:
target[:A] = [1] * A
# Считаем минимальное количество переключений
switches = 0
i = 0
while i < n:
# Если текущее состояние не совпадает с требуемым, инвертируем
if L[i] != target[i]:
# Инвертируем следующие k комнат, если возможно
if i + k <= n:
for j in range(i, i + k):
L[j] = 1 - L[j] # Инвертируем состояние комнаты
switches += 1
else:
return -1 # Невозможно сделать переключение, выходим
i += 1
return switches
# Чтение входных данных
n, k = map(int, input().split())
L = list(map(int, input().split()))
A = int(input())
# Выводим результат
print(min_switches(n, k, L, A))
https://youtu.be/xD6L5cXfm-U?si=bZ0UX595fa6lWVII