В
Все
Б
Биология
Б
Беларуская мова
У
Українська мова
А
Алгебра
Р
Русский язык
О
ОБЖ
И
История
Ф
Физика
Қ
Қазақ тiлi
О
Окружающий мир
Э
Экономика
Н
Немецкий язык
Х
Химия
П
Право
П
Психология
Д
Другие предметы
Л
Литература
Г
География
Ф
Французский язык
М
Математика
М
Музыка
А
Английский язык
М
МХК
У
Українська література
И
Информатика
О
Обществознание
Г
Геометрия
del9832
del9832
22.10.2022 15:17 •  Информатика

Задача 10: Ремонт забора

Забор состоит из N одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать продающиеся в магазине щиты, которые бывают L разных видов: шириной в 1 доску, в 2 доски, ..., в L досок. Щит нельзя разрезать на части, то есть одним щитом можно заменить не более любых L подряд идущих досок. При этом можно менять не только сгнившие доски, но и хорошие.

Оказалось, что все щиты стоят одинаково, независимо от размера щита. Определите, какое наименьшее число щитов необходимо приобрести, чтобы починить весь забор.

Входные данные

Первая строка входных данных содержит целое число L (L > 0) – максимальный размер щита. Во второй строке входных данных записано целое число N (N > 0) – количество досок в заборе. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующая доска в заборе нуждается в замене, число 0 – что доска может быть сохранена.

Выходные данные

Программа должна вывести одно целое число – минимальное число щитов, которое необходимо приобрести для ремонта всего забора.

Система оценивания

Решение, правильно работающее только для случаев, когда числа L и N не превосходят 1000, будет оцениваться в

В будет оцениваться решение, правильно работающее, когда числа L и N не превосходят 105.

Пример

Ввод Вывод Пояснение

3

8

0

0

1

0

1

0

1

0

2

Максимальная ширина одного щита равна 3. Забор состоит из 8 досок, нужно заменить доски с номерами 3, 5 и 7. Для этого достаточно двух щитов, например, одним щитом меняем доски с номерами 3, 4, 5, а другим щитом меняем доску с номером 7.

Показать ответ
Ответ:
Соня8912
Соня8912
15.10.2020 08:33

Решил на python3

MaxLenRep = int(input())

Len = int(input())

zabor = []

rem = 0

tl = 0

for i in range(Len):

   zabor.append(int(input()))

for i in zabor:

   if i == 1 and tl == 0:

       rem += 1

       tl = MaxLenRep

   if tl > 0:

       tl -= 1

print(rem)

0,0(0 оценок)
Популярные вопросы: Информатика
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота