Ремонт дороги Длина автомобильной дороги составляет N километров. Часть дороги необходимо отремонтировать. При обследовании дорога была разбита на N участков длиной 1 километр, и для каждого участка было определено, нуждается ли он в ремонте или нет, после чего был составлен план дороги, на котором отмечены участки, нуждающиеся в ремонте.
Для ремонта дороги можно привлечь несколько компаний-подрядчиков. Каждая компания может отремонтировать только непрерывный фрагмент дороги. При этом из-за требований антимонопольного законодательства длина фрагмента дороги, который ремонтирует одна компания, не должна превышать L километров (даже если на фрагменте, который ремонтирует одна компания, есть не нуждающиеся в ремонте участки, общая длина данного фрагмента не должна превышать L километров).
Определите, какое наименьшее количество компаний-подрядчиков необходимо привлечь для ремонта дороги.
Входные данные
Первая строка входных данных содержит целое число L ( L> 0 ) — максимальную длину фрагмента дороги, который может отремонтировать одна компания. Во второй строке входных данных записано целое число N ( N> 0 ) — длина всей дороги. Следующие N строк содержат по одному числу, равному 0 или 1. Число 1 обозначает, что соответствующий участок дороги нуждается в ремонте, число 0 — что участок не требует ремонта.
Выходные данные
Программа должна вывести одно целое число — минимальное количество компаний-подрядчиков, которое необходимо привлечь для ремонта дороги.
Примечание
В тесте из примера первая компания может отремонтировать участок номер 3, вторая компания — участки с 5 по 7.
Примеры
Ввод
Вывод
3
8
0
0
1
0
1
0
1
0
2
Var i, N, k1, k2, k3, R : integer;
mas: array[1..100]of integer;
Begin
Writeln ('Введите число элементов массива (N<100)');
Readln (N);
For i:=1 to N do begin
Write ('Введите ', i, ' элемент массива ');
Readln (mas[i]);
end;
Write ('Введите номера элементов, которые необходимо поменять местами: ');
Readln (k1, k2);
Writeln ('Исходный массив: ');
For i:=1 to N do write(mas[i], ' ');
writeln;
if (mas[k1] mod 2=0)and(mas[k2] mod 2=0) then
begin
R:=mas[k1]; mas[k1] := mas[k2]; mas[k2] := R;
end
else
begin
write('Введите ещё один номер: ');
readln(k3);
R:=mas[k3]; mas[k3] := mas[1]; mas[1] := R;
end;
Writeln ('Итоговый массив: ');
for i := 1 to N do Write (mas[i], ' ');
End.
Пример:
Введите число элементов массива (N<100)
5
Введите 1 элемент массива 12
Введите 2 элемент массива 84
Введите 3 элемент массива 37
Введите 4 элемент массива 59
Введите 5 элемент массива 20
Введите номера элементов, которые необходимо поменять местами: 2 4
Исходный массив: 12 84 37 59 20
Введите ещё один номер: 5
Итоговый массив: 20 84 37 59 12
N = 30;
Var
T:array[1..N] of integer;
i,k:integer;
Begin
Write('Температура в течение месяца:');
k:=0;
For i:= 1 to N do
Begin
T[i]:=random(20)-15;
Write(' ',T[i]);
if T[i] < 0 then k:=k+1;
End;
WriteLn;
WriteLn('Количество дней, когда температура опускалась ниже нуля: ',k);
End.
Пример работы программы:
Температура в течение месяца: -3 -5 -4 1 -11 -5 0 2 2 4 3 -6 -7 -4 -14 -11 -15 -14 -15 0 -7 -14 -13 -13 -12 -1 -3 -13 -15 -5
Количество дней, когда температура опускалась ниже нуля: 23