2017-11-30
1045
| input.dat | output.dat |
| 20 3 5 3 1 7 4 2 8 10 | 5 8 2 7 3 |
Анализ. Входные данные состоят из двух строк. Первая - это количество матрешек в магазине, а вторая - высоты соответствующих матрешек. Тогда задача сводится к нахождению длины монотонной последовательности высот матрешек с разницей высот ровно в 1 см. Поиск такой последовательности удобно будет сделать в отсортированном массиве. Так как в результате работы программы необходимо вывести номера матрешек, которые необходимо купить, то входные данные удобно хранить в двумерном массиве, где первая компонента - это высота матрешки, а вторая - ее начальный порядковый номер на полке.
Метод поиска наибольшей монотонной последовательности заключается в проверке условия монотонности с подсчетом начала последовательности и ее длины. Самая длинная текущая последовательность сравнивается с найденной, таким образом, в конце работы получим самую длинную монотонную последовательность.
// блок объявления переменных
var mass: array [ 1..10000, 1..2 ] of longint;
n, i, j, mdl, tdl, n_tdl, n_mdl: integer;
r: longint; pr: boolean;
input:text;
output:text;
begin
//организация связи с файлами открытие файов на запись и чтение
assign (input, ' input.dat ');
assign (output, ' output.dat ');
reset (input); rewrite (output);
// чтение данных из файла
Readln(input,n); // количество матершек
for i:=1 to n do begin //заполнение двумерного массива
read (input, mass [i,1 ]); // первый столбец – высота матрешек
mass [i,2]:= i; // второй столбец – порядковый номер на полке
end;
// в блоке происходит перебор массива и исключение повторяющихся данных
for i:=1 to n-1 do
for j:= i+1 to n do
if mass [ i,1]= mass [ j, 1 ] { если встречаются повторяющиеся данные одно из значений заменяется на -1 }
then begin mass [ j,1]:= -1;
end;
// блок сортировки массива
pr:=true;
while pr do
begin
pr:= false;
for i:=1 to n-1 do
if mass [ i,1] >mass [ i +1,1] then
begin
r:=mass [ i, 1 ]; mass [ i,1]:= mass [ i +1,1];
mass [ i +1,1]:= r; r:=mass [ i, 2 ];
mass [ i,2]:= mass [ i +1,2]; mass [ i +1,2]:= r;
pr:=true;
end;
end;
// задание начальных значений переменным для подсчета максимальной длины последовательности, которая удовлетворяет условию задачи
n_tdl:=1; tdl:=1; n_mdl:=0;mdl:=0;
for i:=1 to n do
begin
//проверка условия разницы в высоте в 1 см
if mass [ i,1]+1<>mass [ i +1,1]
then begin
// если текущая длина последовательности больше максимальной
if tdl>=mdl
// принимаем такущую длину за максимальную
then begin n_mdl:=n_tdl; mdl:= tdl; end;
// задаем значения для дальнейшей работы
tdl:=1; n_tdl:= i +1;
end
// если условие разницы в высоте не выполняется, то значение текущей длины последовательности увеличиваем на единицу
else tdl:= tdl +1;
end;
// вывод данных в файл
writeln (output,mdl);
// вывод номеров расположения матрешек на полке
for i:=n_mdl to n_mdl+mdl-1 do
write (output, mass [ i, 2 ], ' ');
writeln;
close (input); close (output);
end.
Задача 2. Бой с драконом.
Тип: циклические алгоритмы
Сложность: легкая
В шахматном королевстве завелся N-головый шахматный дракон, который нападал на другие фигуры и съедал их. Тогда шахматный король дал шахматному ферзю шахматный щит и шахматный меч и приказал уничтожить такую странную агрессивную фигуру. Оседлал шахматный ферзь своего шахматного коня и поскакал к логову дракона. И вот сошлись ферзь и дракон в шахматном бою, который происходит следующим образом. Сначала атакует ферзь - он может отрубить одним ударом своего шахматного меча любые головы дракона, но не более чем M за раз. Потом атакует дракон своим огненным дыханием, ферзь скрывается за шахматным щитом, а за это время у дракона вырастают K новых голов. После этого снова атакует ферзь и так далее. Бой продолжается до тех пор, пока у дракона не останется ни одной головы. В этом случае дракон погибает, а ферзь возвращается к своему королю с победой. Но бой может и не закончиться никогда. Составьте алгоритм, определяющий, сможет ферзь одолеть дракона, и если да, то какое минимальное число ударов ему нужно для этого.
Входные данные: В первой строке входного файла input.dat записаны три значения N (1 ≤ N ≤ 1000000000), M (1 ≤ M ≤ 100000), K (1 ≤ K ≤ 100000).
Выходные данные. В первую строку выходного файла output.dat необходимо вывести слово yes – если возможно преодолеть шахматного дракона и слово no – если преодолеть дракона нельзя, а вторая строчка должна содержать количество ударов для победы (если победа возможна).
Ограничение по времени: 0,5 секунды на тест.
