Сегодня разберем задание Олимпиады Сириус по информатике для 8-10 классов - задача "Ремонт забора" и напишем программу на Паскале. Напомню условие:
Забор состоит из N одинаковых досок. Некоторые из досок сгнили и нуждаются в замене. Для ремонта забора можно использовать щиты, которые могут иметь ширину, равную от 1 до L досок, т. е. шириною в 1 доску, 2 доски, ... и максимум L досок. Щит нельзя разрезать на части, т. е. одним щитом можно заменить от 1 до L подряд идущих досок. При этом можно менять не только сгнившие доски, но и хорошие.
Определить наименьшее число щитов, требующееся для ремонта забора.
Максимальные значения L и N равны 100000.
Первый входной параметр содержит число L>0 - максимальный размер щита. Второй параметр число N>0 - количество досок в заборе. Далее вводятся N значений, каждое из которых равно 1, если текущая доска требует замены, и равно 0, если доска годная.
На выходе нужно получить минимальное число щитов, требуемых для ремонта.
Для понимания алгоритма давайте рассмотрим конкретную исходную конфигурацию. Пусть забор имеет 20 досок, из которых требуют замены номера 3, 4, 7, 11, 13, 14, 19. А максимальный размер щита пусть будет 5.
Доски, подлежащие ремонту, отмечены цифрами 1 и выделены штриховкой. Годные доски, согласно условию, отмечены нулями.
Легко видеть, что для использования минимального количества щитов нужно в первую очередь брать щиты максимального размера L, поскольку по условию менять можно и хорошие доски. А на участок, оставшийся в конце, при необходимости, поставить щит меньшей ширины, поскольку мы располагаем щитами любого размера от 1 до L. Таким образом, просматривается следующий алгоритм: движемся от начала до первой плохой доски. Начиная с этой доски ставим щит максимальной длины. От конца этого щита находим следующую плохую доску и вновь ставим самый большой щит. И так далее, пока забор не закончится.
В нашем случае понадобится 3 щита (выделены красным): 2 шт. максимальной ширины (5) и в конце шириной 2.
А вот и программа:
Объявляем переменные
var
l, n, i, s: longint;
z: array[1..100000] of byte;
Здесь
l - максимальная длина щита;
n - длина забора (количество досок);
i - переменная для цикла;
s - счетчик числа щитов;
z - массив признаков досок (1 - подлежит ремонту, 0 - годная);
Вводим длину щита и длину забора (попутно проверяя на допустимые значения)
repeat
readln(l, n);
until (l>0) and (l<=100000) and (n>0) and (n<=100000);
Заполняем массив признаков досок:
for i:=1 to n do read(z[i]);
Здесь ничего не проверяем, главное, если доска подлежит ремонту - ввести 1, для годной доски можно ввести любое число (в пределах границ типа). Это слегка не соответствует условию (годная доска должна обозначаться нулем), но не будем усложнять программу. Насколько я понял, конкретно в этой Олимпиаде при проверке решения вводились исключительно допустимые значения. Хотя о "защите от дурака" никогда забывать не следует.
Присваиваем переменным исходные значения и начинаем проверять доски:
s:=0; i:=1;
while i<=n do
begin
Если текущая доска подлежит ремонту, то ставим самый длинный щит, т. е. смещаемся на длину щита, начиная с текущей доски, и увеличиваем счетчик установленных щитов на 1:
if (z[i]=1) then
begin
i:=i+l-1;
s:=s+1;
end;
Переходим к следующей доске и так далее по циклу:
i:=i+1;
end;
Выводим результат и завершаем программу.
writeln(s);
end.
Полностью текст программы без комментариев:
var
l, n, i, s: longint;
z: array[1..100000] of byte;
begin
repeat
readln(l, n);
until (l>0) and (l<=100000) and (n>0) and (n<=100000);
for i:=1 to n do read(z[i]);
s:=0;
i:=1;
while i<=n do
begin
if (z[i]=1) then
begin
i:=i+l-1;
s:=s+1;
end;
i:=i+1;
end;
writeln(s);
end.
Проверяем для вышеописанного примера.
Входные данные:
5 20 0 0 1 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0
На выходе получаем 3 - что и требовалось.