Задача Подняться на лестницу При прохождении компьютерной игры Вася дошел до финального испытания. Ему необходимо взобраться на вершину пирамиды. Вокруг пирамиды идет лестница, однако за долгие годы некоторые из ступенек этой лестницы стали слишком опасными для того, чтобы можно было на них наступать.
Вася очень аккуратно проходил все предыдущие испытания, и поэтому у него есть все подсказки о том, на какие ступеньки наступать нельзя.
Лестница состоит из N ступенек, пронумерованных от 1 до N от основания пирамиды до её вершины, и в ней K опасных ступенек. Кроме того, персонаж Васи за одну секунду может сделать один шаг и подняться на 1, 2, …S ступенек.
До прохождения испытания персонаж стоит перед первой ступенькой, а для успешного его прохождения требуется оказаться на N-ой ступеньке.
Определите минимальное и максимальное время, за которое Вася может пройти финальное испытание.
Формат входных данных
В первой строке входного файла записаны три целых числа N, K и S (1 ≤ N ≤ 200 000, 1 ≤ S 0, то во второй строке записаны K различных целых чисел ai (1 ≤ ai < N) — номера опасных ступенек. Гарантируется, что можно подняться на вершину пирамиды, не наступая на опасные ступеньки. В 80 % тестов N ≤ 1 000.
Формат выходных данных
В единственной строке выходного файла выведите два целых числа: минимальное и максимальное время, за которое Вася может пройти финальное испытание.
const
nn=100; // предельное кол-во элементов в массиве
type
mas=array[1..nn] of integer;
procedure RandomArray(var a:mas;n,p,q:integer);
// Заполняет первые n элементов массива a
// случайными числами из интервала [p;q]
var
i:integer;
begin
for i:=1 to n do a[i]:=Random(q-p+1)+p
end;
procedure PrintArray(a:mas;n:integer);
// Выводит на экран первые n элементов массива a
var
i:integer;
begin
for i:=1 to n do Write(a[i],' ');
Writeln
end;
procedure SortByDescending(var a:mas;n:integer);
// Сортирует по невозрастанию первые n элементов массива a.
// Элементарная обменная сортировка
var
i,j,t:integer;
begin
for i:=1 to n-1 do
for j:=1 to n-1 do
if a[j]<a[j+1] then
begin t:=a[j]; a[j]:=a[j+1]; a[j+1]:=t end
end;
// Основная программа
var
i,n1,n2,n3,x,y:integer;
a,b,c:mas;
begin
Randomize;
Write('Кол-во элементов в массиве и границы интервала из значений: ');
Read(n1,x,y);
RandomArray(a,n1,x,y);
Write('Кол-во элементов в массиве и границы интервала из значений: ');
Read(n2,x,y);
RandomArray(b,n2,x,y);
Write('Первый массив: '); PrintArray(a,n1);
Write('Второй массив: '); PrintArray(b,n2);
Writeln('Объединенный массив, отсортированный по невозрастанию');
n3:=n1+n2;
for i:=1 to n1 do c[i]:=a[i];
for i:=1 to n2 do c[i+n1]:=b[i];
SortByDescending(c,n3);
PrintArray(c,n3)
end.
Тестовое решение
Кол-во элементов в массиве и границы интервала из значений: 8 10 60
Кол-во элементов в массиве и границы интервала из значений: 6 30 90
Первый массив: 41 56 14 57 52 51 30 54
Второй массив: 76 36 44 39 68 38
Объединенный массив, отсортированный по невозрастанию
76 68 57 56 54 52 51 44 41 39 38 36 30 14
2. На самом деле эту же задачу можно написать гораздо короче
// PascalABC.NET 3.1, сборка 1246 от 23.05.2016
begin
var n1,n2,x,y:integer;
Write('Кол-во элементов в массиве и границы интервала из значений: ');
Read(n1,x,y);
var a:=ArrRandom(n1,x,y);
Write('Кол-во элементов в массиве и границы интервала из значений: ');
Read(n2,x,y);
var b:=ArrRandom(n2,x,y);
Write('Первый массив: '); a.Println;
Write('Второй массив: '); b.Println;
Writeln('Объединенный массив, отсортированный по невозрастанию');
var c:=(a+b).SortedDescending; c.Println
end.