Question

ДАМ 100 БАЛЛОВ НА ЛЮБОМ ЯЗЫКЕ!!! Задача 10: Ремонт забора Забор состоит из N одинаковых вертикальных досок. Некоторые из досок сгнили и нуждаются в замене, для каждой доски известно, нужно ли её заменить. Для ремонта забора можно использовать продающиеся в магазине щиты, которые бывают L разных видов: шириной в 1 доску, в 2 доски, ..., в L досок. Щит нельзя разрезать на части, то есть одним щитом можно заменить не более любых L подряд идущих досок. При этом можно менять не только сгнившие доски, но и хорошие. Оказалось, что все щиты стоят одинаково, независимо от размера щита. Определите, какое наименьшее число щитов необходимо приобрести, чтобы починить весь забор. Входные данные Первая строка входных данных содержит целое число L (L > 0) – максимальный размер щита. Во второй строке входных данных записано целое число N (N > 0) – количество досок в заборе. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующая доска в заборе нуждается в замене, число 0 – что доска может быть сохранена. Выходные данные Программа должна вывести одно целое число – минимальное число щитов, которое необходимо приобрести для ремонта всего забора. Система оценивания Решение, правильно работающее только для случаев, когда числа L и N не превосходят 1000, будет оцениваться в 6 баллов. В 10 баллов будет оцениваться решение, правильно работающее, когда числа L и N не превосходят 105. Пример Ввод Вывод Пояснение 3 8 0 0 1 0 1 0 1 0 2 Максимальная ширина одного щита равна 3. Забор состоит из 8 досок, нужно заменить доски с номерами 3, 5 и 7. Для этого достаточно двух щитов, например, одним щитом меняем доски с номерами 3, 4, 5, а другим щитом меняем доску с номером 7.

Answer 1

Ответ:

Решил на 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)

Answer 2

Для решения этой задачи мы можем использовать жадный алгоритм. Давайте пройдемся по забору слева направо и будем считать, сколько досок подряд нужно заменить. Как только мы достигнем момента, когда нужно заменить L-ю доску, мы установим щит на этот участок. Затем продолжим двигаться вперед до тех пор, пока не встретим новую доску, требующую замены. Таким образом, мы будем минимизировать количество использованных щитов.

Вот Python код, решающий эту задачу:

pythonCopy code
L = int(input())  # максимальный размер щита
N = int(input())  # количество досок

boards = []
for _ in range(N):
    boards.append(int(input()))  # список досок, требующих замены (1) или не требующих (0)

shields = 0  # счетчик использованных щитов
current_section = 0  # текущий участок подряд идущих досок, требующих замены

for board in boards:
    if board == 1:
        current_section += 1
        if current_section == L:  # если достигли L подряд идущих досок требующих замены
            shields += 1
            current_section = 0
    else:
        current_section = 0  # сбрасываем счетчик, если нашли доску, не требующую замены

# Если остались незамененные доски в конце, добавляем еще один щит
if current_section > 0:
    shields += 1

print(shields)

Вы можете вставить этот код в среду для выполнения Python и передать входные данные, как описано в вашем примере. Код определит минимальное количество щитов, необходимых для ремонта забора.