Добрый день, уважаемые подписчики! В этом выпуске:
1.Разбор задачи "Путешествие";
2.Условие задачи "Зигзаги";
1.Задача "Путешествие"
Вы путешествуете из города A в город B. В связи с недавно проведенной реформой путей сообщения, из города С существует прямой путь в город D, в том и только том случае если D южнее и восточнее города С. Вы приняли решение проехать из A в B через максимально возможное число городов (города A и B не в счет). Найти наибольшее число городов, через которые можно проехать по пути из A в B или указать, что Вы не сможете попасть в город B.
Входные данные
В первой строке записано натуральное число N (2<=N<=1000) - количество городов. Далее в N строках описаны положения всех городов парой координат в некоторой декартовой системе, которая введена таким образом, что ось абсцисс направлена с запада на восток, а ординат - с юга на север. Координаты - целые числа, по абсолютной величине не превосходящие 10^9. Числа в строке разделяются пробелами. Город A имеет номер 1, а город B - номер N. Любая пара городов имеет разные координаты. Выходные данные
Если путь в B существует, то выведите единственное неотрицательное целое число - наибольшее число проезжих городов, через которые может проходить путь. Выведите фразу "No way", если такого пути нет.
Пример входных данных:
5
0 2
1 2
1 1
2 1
2 0
Пример выходных данных:
1 Решение
Читаем координаты городов в массив a. a[1,i]-иксовая координата города, a[2,i]-игрековая. Организуем цикл, в котором ищем город с минимальным a[1,i] южнее и восточнее A. Записываем его в массив b, убираем из a. Ищем, из каких городов можно было в этот город приехать, из них выбираем тот, по пути в который можно было проехать через наибольшее количество городов. В конце цикла выводим ответ.
Использовался прием динамического программирования, о котором Вы можете прочитать здесь.
program p7;
var
max,max1,min,q,i,j,k,m,n,t,l,s:longint;
a,b:array[1..2,1..1000]of longint;
w:array[1..1000] of longint;
begin
read(n);
max1:=0;
for i:=1 to n do readln(a[1,i],a[2,i]);
m:=n-1;
t:=0;
k:=0;
q:=0;
while qmax)and(l>b[1,i])and(sa[2,n])and(l>a[1,1])and(smax1 then max1:=w[t];
end;
if (a[1,1]>=a[1,n])or(a[2,1]<=a[2,n])then write('No way')else write(max1);
end.
2. Условие задачи "Зигзаги":
Последовательность A1, A2, ..., AK называется зигзагом, если верны неравенства A1 < A2 > A3 < A4 > ... и т.д. или A1 > A2 < A3 > A4 < ... и дальше. Например, последовательности 1, -1, 0 и 10, 20, 9, 24, 11, 20 - зигзаги, также любые последовательности из одного или двух различных чисел тоже зигзаги. На доске написано N чисел. Ваша задача найти наименьшее количество чисел, которые надо удалить, что бы остался зигзаг и номера этих чисел в последовательности. Входные данные
В первой строке входного файла записано число N (1 <= N <= 1000). Далее следует N чисел - последовательность чисел, записанных на доске. Каждое из них целое, по абсолютной величине не превосходящее 10^6. Числа во входном файле разделяются пробелами и/или символами перевода строки. Выходные данные
В первой строке выведите единственное число - наименьшее количество чисел, которые надо удалить, чтобы остался зигзаг. Во второй строке выведите номера этих чисел в данной последовательности. Номера разделяйте пробелами. Если решений несколько, то выведите любое из них. Пример входных данных:
4
1 2 3 1
Пример выходных данных:
1
3
Разбор этой задачи - в следующем номере рассылки.
Если у Вас возникли вопросы, пишите, отвечу. Рекомендую посетить сайт рассылки: http://olympinform.narod.ru. До новых встреч!
