Покраска забора
У Васи на даче длина забора составляет N метров. Часть забора необходимо покрасить. При обследовании забор был разбит на N участков длиной 1 метр, и для каждого участка было определено, нуждается ли он в покраске или нет.
После того как валик для покраски пропитывается в ведре краской, им можно окрасить не более L
метров подряд. В том числе можно перекрашивать и участки в этом не нуждающиеся.
Определите, за какое количество подобных операций (пропитать валик краской и перекрасить не более L метров) можно обновить забор так, чтобы все нуждающиеся в покраске фрагменты оказались окрашены.
Формат входных данных
Первая строка входных данных содержит целое число L
( 0 ( 0 — что участок в покраске не нуждается.
Формат выходных данных
Программа должна вывести одно целое число — минимальное количество описанных действий, которое необходимо для перекраски забора.
Замечание
В тесте из примера за первое действие можно, например, перекрасить второй метр забора, а за второе — с 5-го по 7-й метр.
У Васи на даче длина забора составляет N метров. Часть забора необходимо покрасить. При обследовании забор был разбит на N участков длиной 1 метр, и для каждого участка было определено, нуждается ли он в покраске или нет.
После того как валик для покраски пропитывается в ведре краской, им можно окрасить не более L
метров подряд. В том числе можно перекрашивать и участки в этом не нуждающиеся.
Определите, за какое количество подобных операций (пропитать валик краской и перекрасить не более L метров) можно обновить забор так, чтобы все нуждающиеся в покраске фрагменты оказались окрашены.
Формат входных данных
Первая строка входных данных содержит целое число L
( 0 ( 0 — что участок в покраске не нуждается.
Формат выходных данных
Программа должна вывести одно целое число — минимальное количество описанных действий, которое необходимо для перекраски забора.
Замечание
В тесте из примера за первое действие можно, например, перекрасить второй метр забора, а за второе — с 5-го по 7-й метр.
Answers & Comments
Для решения данной задачи можно использовать жадный алгоритм. Он будет работать следующим образом:
Создаем переменную count и инициализируем ее нулем. Она будет хранить количество операций, необходимых для покраски забора.
Создаем переменную current_length и инициализируем ее нулем. Она будет хранить текущую длину непрерывного участка, который мы можем покрасить одним валиком.
Проходимся по всем участкам забора.
Если текущий участок нуждается в покраске, то увеличиваем текущую длину на 1.
Если текущая длина стала больше L, то это означает, что мы не можем больше покрасить непрерывный участок одним валиком. Поэтому мы должны сделать новую операцию, пропитав валик краской и начав покраску нового непрерывного участка. Увеличиваем count на 1 и обнуляем текущую длину.
После прохода по всем участкам, если текущая длина не равна нулю, это означает, что мы не докрасили последний непрерывный участок до конца. Поэтому мы должны сделать еще одну операцию. Увеличиваем count на 1.
Выводим значение count.
Пример решения на Python:
L = int(input())
fence = input().split()
n = len(fence)
count = 0
current_length = 0
for i in range(n):
if fence[i] == '1':
current_length += 1
if current_length > L:
count += 1
current_length = 1
elif current_length > 0:
count += 1
current_length = 0
if current_length > 0:
count += 1
print(count)
Пример работы:
Входные данные:
2
0 1 1 0 1 1 1 0 1 0
Выходные данные:
5
В данном случае мы можем покрасить первые два участка одним валиком, затем следующие три участка тоже одним валиком, затем два участка по одному валику и, наконец, последний участок тоже одним валиком. Всего нам потребуется 5 операций.