Задача 30.
Заданы натуральное N и две последовательности целых чисел (а1,а2,...,аn) и (b1,b2,...,bn). Заданы также два числа X0 и X1, X0<X1.
1. Найти числа t(0), t(1), ..., t(p), p<=N, такие ,что X0=t(0)<t(1)<...<t(p)=X1 и указать для каждого отрезка [t(j-1), t(j)], 1<=j<=p, такое число k, 1<=k<=N, что для всех i, 1<=i<=N, и для всех x из [t(j)-1,t(j)] справедливо неравенство аk*x+bk>=аi*x+bi.
2.Найти числа s(0), s(1), ..., s(Q), таки, что X0=s(0)< <s(1)<...<s(Q)=X1, и указать для каждого отрезка [s(j-1),s(j)], 1<=j<=Q, такую перестановку (i1,i2,...,iN) чисел 1,2,3,...,N, что для всех x из [s(j-1),s(j)] справедливо неравенство
ai1*x+bi1<=аi2*x+bi2<=...<=аiN*x+biN
и для всех отрезков соответствующие перестановки различны.
|
Решение задачи 30.
Дадим другую интерпретацию этой задачи: Есть N отрезков, описываемых уравнениями
ai*x+bi=y, x0<=x<=x1, i=1, ... ,N.
Предположим, что отрезки не совпадают.
1. Найти верхний контур объединения фигур
ai*x+bi<=y, i=1, ..., N, x0<=x<=x1,
(т.е. найти такую разбивку t0, ..., tp отрезка [x0,x1] и те кусочки отрезков ai*x+bi=y, tj<=x<=tj+1, j=1, ..., p, что отрезок ai*x+bi лежит не ниже любого другого отрезка al*x+bl при tj<=x<=tj+1)
2. Найти такую разбивку отрезка [x0,x1] точками Sj, что в каждом секторе Si<x<Si+1 кусочки отрезков ai*x+bi, i=1, ..., N не пересекаются, а на границах сектора, при x=Si и при x=Si+1, лежит по крайней мере по одной точке пересечения отрезков ai*x+bi, i=1,..., N.
Решим сначала пункт 2 задачи, затем пункт 1.
Найдем все точки пересечения отрезков ai*x+bi, i=1,...,N друг с другом. Добавим в это множество точки x0 и x1. Упорядочим точки пересечения по возрастанию (если в последовательности встречаются несколько точек с одним и тем же значением, то оставляем из них только одну). Получаем таким образом последовательность S0, ..., SQ.
Для каждого отрезка [Si, Si+1] находим его середину
Zi=(Si+Si+1)/2, вычисляем значения fj=aj*Zi+bj, j=1, ...,N, сортируем их по возрастанию. Индексы j значений fj в отсортированной последовательности - это как раз и есть искомая перестановка (i1,i2,...,iN) чисел 1,2,3, ..., N, упомянутая в формулировке задачи в пункте 2.
Для решения пункта 1 выпишем по порядку для каждого отрезка [Sj,Sj+1], j=0, ..., Q-1, величины iN (это индекс самого верхнего отрезка в секторе [Sj,Sj+1]). Отрезок с номером k может быть самым верхним для нескольких смежных секторов [Sj,Sj+1], ..., [Sl,Sl+1]. Поэтому мы просматриваем номера iN, соответствующие отрезкам [Sj,Sj+1], j=0, ..., Q-1 и определяем последовательные максимальные отрезки, помеченные одним и тем же номером. Концевые точки этих максимальных отрезков и есть искомые точки t0, ..., tp (они выбираются по указанному выше методу из точек S0, ..., SQ).
|
