\input style

\proof яРЕДПОЛОЖИМ, ЧТО В ЗДАНИИ ИМЕЕТСЯ ДОПОЛНИТЕЛЬНО $b$~ЧЕЛОВЕК; 
ПЕРВОНАЧАЛЬНО ОНИ НАХОДЯТСЯ В ЛИФТЕ, И ЭТАЖ ИХ НАЗНАЧЕНИЯ ИСКУССТВЕННО 
ПОЛАГАЕТСЯ НУЛЕВЫМ. ыИФТ МОЖЕТ ФУНКЦИОНИРОВАТЬ В СООТВЕТСТВИИ СО СЛЕДУЮЩИМ 
АЛГОРИТМОМ, НАЧИНАЯ С~$k$ (ТЕКУЩИЙ ЭТАЖ), РАВНОГО~$1$.
\picture{ЁЯС. 87.  рЛГОРИТМ ъАРПА ДЛЯ ЛИФТА.}
% !!! т КНИГЕ НЕТ ЗАГОЛОВКА
\alg K.(рЛГОРИТМ ъАРПА ДЛЯ ЛИФТА)
\st[фВИЖЕНИЕ ВВЕРХ.] шЗ $b+c$~ЛЮДЕЙ, НАХОДЯЩИХСЯ В ДАННЫЙ МОМЕНТ В ЛИФТЕ И 
НА ЭТАЖЕ~$k$, ТОЛЬКО~$b$, ИМЕЮЩИЕ САМОЕ ВЫСОКОЕ МЕСТО НАЗНАЧЕНИЯ, 
ПОПАДАЮТ В ЛИФТ, ОСТАЛЬНЫЕ ОСТАЮТСЯ НА ЭТАЖЕ~$k$.

яУСТЬ ТЕПЕРЬ В ЛИФТЕ НАХОДЯТСЯ $u$~ЧЕЛОВЕК С НАЗНАЧЕНИЕМ~$>k$ И~$d$ С 
НАЗНАЧЕНИЕМ~$\le k$. (юКАЖЕТСЯ, ЧТО~$u=\min (b, u_k)$;
ЕСЛИ~$u_k<b$, МЫ МОЖЕМ, СЛЕДОВАТЕЛЬНО, УВОЗИТЬ НЕКОТОРЫХ ЛЮДЕЙ ОТ ИХ МЕСТА 
НАЗНАЧЕНИЯ. ¤ТО---ИХ ЖЕРТВА ДЛЯ ОБЩЕЙ ПОЛЬЗЫ). єМЕНЬШИТЬ~$u_k$ НА~$u$, 
УВЕЛИЧИТЬ~$d_{k+1}$ НА~$d$ И ЗАТЕМ УВЕЛИЧИТЬ~$k$ НА~$1$.

\st[яРОДОЛЖАТЬ ДВИЖЕНИЕ ВВЕРХ?] хСЛИ~$u_k>0$, ВЕРНУТЬСЯ К ШАГУ~\stp{1}.

\st[фВИЖЕНИЕ ВНИЗ.] шЗ $b+c$~ЛЮДЕЙ, НАХОДЯЩИХСЯ В ДАННЫЙ МОМЕНТ В ЛИФТЕ 
ИЛИ НА ЭТАЖЕ~$k$, ТОЛЬКО~$b$, ИМЕЮЩИЕ САМОЕ НИЗКОЕ МЕСТО НАЗНАЧЕНИЯ, 
ПОПАДАЮТ В ЛИФТ, ОСТАЛЬНЫЕ ОСТАЮТСЯ НА ЭТАЖЕ~$k$. яУСТЬ ТЕПЕРЬ В ЛИФТЕ 
НАХОДЯТСЯ $u$~ЧЕЛОВЕК С НАЗНАЧЕНИЕМ~$\ge k$ И~$d$ С НАЗНАЧЕНИЕМ~$<k$. 
(тСЕГДА ОКАЗЫВАЕТСЯ, ЧТО~$u=0$, a~$d=b$, НО АЛГОРИТМ ОПИСЫВАЕТСЯ 
ЗДЕСЬ ПРИМЕНИТЕЛЬНО К ОБЩИМ~$u$ И~$d$, ЧТОБЫ СДЕЛАТЬ ДОКАЗАТЕЛЬСТВО 
НЕСКОЛЬКО ПРОЗРАЧНЕЕ.) єМЕНЬШИТЬ~$d_k$ НА~$d$, УВЕЛИЧИТЬ~$u_{k-1}$ НА~$u$ 
И ЗАТЕМ УМЕНЬШИТЬ~$k$ НА~$1$.

\st[яРОДОЛЖАТЬ ДВИЖЕНИЕ ВНИЗ?] хСЛИ~$k>1$ И~$u_{k-1}>0$, ВЕРНУТЬСЯ К 
ШАГУ~\stp{3}. хСЛИ~$k=1$ И~$u_1=0$, ЗАКОНЧИТЬ АЛГОРИТМ (ВСЕ ЛЮДИ 
ДОСТАВЛЕНЫ НА СВОЕ МЕСТО НАЗНАЧЕНИЯ, А $b$~"ДОПОЛНИТЕЛЬНЫХ" ЛЮДЕЙ СНОВА 
НАХОДЯТСЯ В ЛИФТЕ). т ПРОТИВНОМ СЛУЧАЕ ВЕРНУТЬСЯ К ШАГУ~\stp{2}
\algend

эА РИС.~88 ПОКАЗАН ПРИМЕР РАБОТЫ ЭТОГО АЛГОРИТМА ДЛЯ ЗДАНИЯ С ДЕВЯТЬЮ 
ЭТАЖАМИ И~$b=3$, $c=2$. чАМЕТИМ, ЧТО ОДНА ИЗ ШЕСТЕРОК ВРЕМЕННО 
ПЕРЕМЕЩАЕТСЯ ОТ СВОЕГО МЕСТА НАЗНАЧЕНИЯ, НЕСМОТРЯ НА ТО ЧТО ЛИФТ ПРОХОДИТ 
МИНИМАЛЬНО ВОЗМОЖНОЕ 
%%426
РАССТОЯНИЕ. яРОВЕРКА~$u_{k-1}$ НА ШАГЕ~K4 ЯВЛЯЕТСЯ, КАК МЫ УВИДИМ,
РЕШАЮЩИМ МОМЕНТОМ ДЛЯ ПРАВИЛЬНОЙ РАБОТЫ АЛГОРИТМА.

ўТОБЫ ПРОВЕРИТЬ ПРАВИЛЬНОСТЬ ЭТОГО АЛГОРИТМА, ЗАМЕТИМ, ЧТО ШАГИ~K1 И~K3 
ВСЕГДА ПОДДЕРЖИВАЮТ МАССИВЫ~$u$ И~$d$ В СООТВЕТСТВИИ С ТЕКУЩИМ 
ПОЛОЖЕНИЕМ, ЕСЛИ СЧИТАТЬ ЛЮДЕЙ В ЛИФТЕ НАХОДЯЩИМИСЯ НА ТЕКУЩЕМ ЭТАЖЕ~$k$. 
ЄЕПЕРЬ МОЖНО ДОКАЗАТЬ ПО
\picture{ЁИС.~88. юПТИМАЛЬНЫЙ СПОСОБ ПЕРЕРАСПРЕДЕЛЕНИЯ ЛЮДЕЙ ПРИ ПОМОЩИ 
  НЕБОЛЬШОГО МЕДЛЕННОГО ЛИФТА. (ъАЖДЫЙ ЧЕЛОВЕК ПРЕДСТАВЛЕН НОМЕРОМ ЭТАЖА, 
  НА КОТОРЫЙ ОН НАПРАВЛЯЕТСЯ.)
}
ИНДУКЦИИ, ЧТО В НАЧАЛЕ КАЖДОГО ШАГА ИМЕЮТ МЕСТО СЛЕДУЮЩИЕ СВОЙСТВА:
$$
\displaylinesno{
u_l=d_{l+1}  \rem{ПРИ $k\le l < n$;} & (6) \cr
u_l=d_{l+1}-b \rem{ПРИ $1\le l < k$;} & (7) \cr
\hbox{ЕСЛИ } u_l=0 \hbox{ И } k\le l < n, \hbox{ ТО } u_{l+1}=0. & (8) \cr
}
$$
ъРОМЕ ТОГО, В НАЧАЛЕ ШАГА~K1 В ЛИФТЕ ИЛИ НА ЭТАЖЕ~$k$ НАХОДЯТСЯ 
$\min(u_k, b)$~ЧЕЛОВЕК С НАИВЫСШИМИ НАЗНАЧЕНИЯМИ СРЕДИ ВСЕХ ЛЮДЕЙ НА 
ЭТАЖАХ~$\le k$ С НАЗНАЧЕНИЯМИ~$>k$. т НАЧАЛЕ ШАГА~K3 В ЛИФТЕ ИЛИ НА 
ЭТАЖЕ~$k$ НАХОДЯТСЯ $\min(d_k, b)$~ЧЕЛОВЕК С НАИНИЗШИМИ НАЗНАЧЕНИЯМИ 
СРЕДИ ВСЕХ ЛЮДЕЙ НА ЭТАЖАХ~$\ge k$ С НАЗНАЧЕНИЯМИ~$<k$. ¤ТИ УСЛОВИЯ 
ТАКЖЕ МОЖНО ПРОВЕРИТЬ ИНДУКТИВНО, ЕСЛИ ПРОСЛЕДИТЬ, КАК МЫ ПОПАДАЕМ В 
ШАГИ~K1 ИЛИ~K3 (СМ.~УПР.~5).

шЗ ЭТИХ СВОЙСТВ СЛЕДУЕТ, ЧТО ЗАМЕЧАНИЯ В СКОБКАХ НА ШАГАХ~K1 И~K3 
СПРАВЕДЛИВЫ. ъАЖДОЕ ВЫПОЛНЕНИЕ ШАГА~K1, СЛЕДОВАТЕЛЬНО, 
УМЕНЬШАЕТ~$\ceil{u_k/b}$ НА~1 И ОСТАВЛЯЕТ~$\ceil{d_{k+1}/b}$ БЕЗ ИЗМЕНЕНИЙ.
ъАЖДОЕ ВЫПОЛНЕНИЕ ШАГА~K3 УМЕНЬШАЕТ~$\ceil{d_k/b}$ НА~$1$ И
%% 427
ОСТАВЛЯЕТ НЕИЗМЕННЫМ~$\ceil{u_{k-1}/b}$. рЛГОРИТМ, СЛЕДОВАТЕЛЬНО, ДОЛЖЕН 
ЗАВЕРШИТЬСЯ ЗА КОНЕЧНОЕ ЧИСЛО ШАГОВ, И ПОСЛЕ ЭТОГО В СИЛУ~(6) И~(8) КАЖДЫЙ 
ЧЕЛОВЕК ДОЛЖЕН ОКАЗАТЬСЯ НА СВОЕМ ЭТАЖЕ.
\proofend

хСЛИ~$u_k=0$, a~$u_{k+1}>0$, МЫ ИМЕЕМ "НЕСВЯЗНУЮ" СИТУАЦИЮ;
ЛИФТ ДОЛЖЕН ПОДНЯТЬСЯ ДО ЭТАЖА~$k+1$, ЧТОБЫ ПЕРЕМЕСТИТЬ ЛЮДЕЙ ВВЕРХ, ХОТЯ 
НИКОМУ НЕ НУЖНО ПЕРЕЕЗЖАТЬ С ЭТАЖЕЙ~$\le k$ НА ЭТАЖИ~$\ge k+1$. He 
ПОСТУПАЯСЬ ОБЩНОСТЬЮ, МОЖНО СЧИТАТЬ~$u_{n-1}>0$; ТОГДА ЛЮБОЙ ПРАВИЛЬНЫЙ 
ГРАФИК ДОЛЖЕН ВКЛЮЧАТЬ ПО КРАЙНЕЙ МЕРЕ
$$
2 \sum_{1\le k < n} \max (1, \ceil{u_k/b})
\eqno (9)
$$
ДВИЖЕНИЙ, ТАК КАК МЫ ТРЕБУЕМ, ЧТОБЫ ЛИФТ ВЕРНУЛСЯ НА ПЕРВЫЙ ЭТАЖ. уРАФИК, 
ДЛЯ КОТОРОГО ДОСТИГАЕТСЯ ЭТА НИЖНЯЯ ГРАНИЦА, ЛЕГКО СОСТАВИТЬ (УПР.~4).

\excercises
\ex[17] т МЕТОДЕ ПУЗЫРЬКА $P\hbox{-ГО}$~ПОРЯДКА, ОБСУЖДАВШЕМСЯ В ТЕКСТЕ, 
ИСПОЛЬЗУЕТСЯ ТОЛЬКО ПРЯМОЕ ЧТЕНИЕ И ПЕРЕМОТКА. ьОЖНО ЛИ МОДИФИЦИРОВАТЬ 
АЛГОРИТМ ТАК, ЧТОБЫ ИЗВЛЕЧЬ ПРЕИМУЩЕСТВА ИЗ \emph{ОБРАТНОГО} ЧТЕНИЯ?

\ex[ь26] эАЙДИТЕ ЯВНЫЕ ВЫРАЖЕНИЯ В ЗАМКНУТОМ ВИДЕ ДЛЯ ЧИСЕЛ~$X_n$, $Y_n$,
 ОПРЕДЕЛЕННЫХ В~(3). [\emph{єКАЗАНИЕ:} ИЗУЧИТЕ РЕШЕНИЕ УРАВНЕНИЯ~(5.2.2-19).]

\ex[38] ёУЩЕСТВУЕТ ЛИ МЕТОД СОРТИРОВКИ С ДВУМЯ ЛЕНТАМИ, ОСНОВАННЫЙ ТОЛЬКО 
НА СРАВНЕНИИ КЛЮЧЕЙ (А НЕ НА СВОЙСТВАХ ЦИФР), ДЛЯ КОТОРОГО В НАИХУДШЕМ 
СЛУЧАЕ ПРИ СОРТИРОВКЕ $N$~ЗАПИСЕЙ ПЕРЕМЕЩЕНИЕ ЛЕНТ СОСТАВЛЯЕТ~$O(N\log N)$?  
[яРИ БЫСТРОЙ СОРТИРОВКЕ ЭТО ЗНАЧЕНИЕ ДОСТИГАЕТСЯ В СРЕДНЕМ, НО НЕ В 
НАИХУДШЕМ СЛУЧАЕ, А В МЕТОДЕ їЕННИ И~ёТИРНЗА (РИС.~86) ОНО 
РАВНЯЕТСЯ~$O(N(\log N)^2)$.]

\ex[ь23] т ЗАДАЧЕ О ЛИФТЕ ПРЕДПОЛОЖИМ, ЧТО ИМЕЮТСЯ ИНДЕКСЫ~$p$, $q$, 
ПРИЧЕМ~$q\ge p+2$, $u_p>0$, $u_q>0$ И~$u_{p+1}=\cdots=u_{q-1}=0$. 
юБоЯСНИТЕ, КАК СОСТАВИТЬ ГРАФИК, ТРЕБУЮЩИЙ НЕ БОЛЕЕ (9)~ЕДИНИЦ ВРЕМЕНИ.

\rex[ь23] тЕРНО ЛИ СЛЕДУЮЩЕЕ УТВЕРЖДЕНИЕ? яОСЛЕ ШАГА~K1 
АЛГОРИТМА ТЕОРЕМЫ~ъ НИКТО В ЛИФТЕ НЕ СТРЕМИТСЯ ПОПАСТЬ НА БОЛЕЕ НИЗКИЙ 
ЭТАЖ, ЧЕМ НЕКТО ИЗ ОСТАВШИХСЯ НА ЭТАЖАХ~$<k$.

\ex[ь30] (Ё.~ь.~ъАРП.) юБОБЩИТЕ ЗАДАЧУ О ЛИФТЕ (РИС.~87) НА СЛУЧАЙ, 
КОГДА НА ЭТАЖЕ~$j$ ПЕРВОНАЧАЛЬНО НАХОДИТСЯ $c_j$~ПАССАЖИРОВ И ЭТАЖ~$j$ 
СЛУЖИТ НАЗНАЧЕНИЕМ ДЛЯ $c'_j$~ПАССАЖИРОВ ПРИ~$1\le j \le n$. яОКАЖИТЕ, 
ЧТО СУЩЕСТВУЕТ ГРАФИК РАБОТЫ, РАССЧИТАННЫЙ НА 
$2\sum_{1\le k < n} \max (1, \ceil{u_k/b}, \ceil{d_{k+1}/b})$~ЕДИНИЦ 
ВРЕМЕНИ, ПРИЧЕМ НА ЭТАЖЕ~$j$ 
НИКОГДА НЕ ОКАЗЫВАЕТСЯ ОДНОВРЕМЕННО БОЛЕЕ $\max (c_j, c'_j)$~ПАССАЖИРОВ. 
[\emph{єКАЗАНИЕ:} ВВЕДИТЕ, ЕСЛИ НЕОБХОДИМО, ФИКТИВНЫХ ЛЮДЕЙ, 
ЧТОБЫ СДЕЛАТЬ~$c_j=c'_j$ ПРИ ВСЕХ~$j$.]

\ex[ь40] (Ё.~ь.~ъАРП.) юБОБЩИТЕ ЗАДАЧУ ИЗ УПР.~6, ЗАМЕНИВ ЛИНЕЙНЫЙ ПУТЬ, 
ПРОХОДИМЫЙ ЛИФТОМ, НА СЕТЬ ДОРОГ, ПО КОТОРЫМ МОЖНО ЕЗДИТЬ НА АВТОБУСЕ, 
ПРИ УСЛОВИИ, ЧТО СЕТЬ ОБРАЗУЕТ ЛЮБОЕ \emph{СВОБОДНОЕ ДЕРЕВО.} рВТОБУС 
ИМЕЕТ КОНЕЧНУЮ ЕМКОСТЬ, И ЖЕЛАТЕЛЬНО ПЕРЕВЕЗТИ ПАССАЖИРОВ К ИХ МЕСТАМ 
НАЗНАЧЕНИЯ ТАК, ЧТОБЫ АВТОБУС ПРОШЕЛ МИНИМАЛЬНОЕ РАССТОЯНИЕ. 

\ex[ь32] яУСТЬ В ЗАДАЧЕ О ЛИФТЕ, РАЗОБРАННОЙ В ТЕКСТЕ, $c=1$. 
ёКОЛЬКО ПЕРЕСТАНОВОК ИЗ $n$~ЧЕЛОВЕК ПО $n$~ЭТАЖАМ ДАДУТ В~(4) $u_k \le 1$ 
ПРИ~$1 \le k \le n$? [эАПРИМЕР, $3\,1\,4\,5\,9\,2\,6\,8\,7$---ТАКАЯ ПЕРЕСТАНОВКА.]

\rex[ь25] эАЙДИТЕ ВАЖНУЮ СВЯЗЬ МЕЖДУ ШЕЙКЕР-СОРТИРОВКОЙ, ОПИСАННОЙ В 
П.~5.2.2 (РИС.~16), И ЧИСЛАМИ~$u_1$, $u_2$,~\dots, $u_n$ В~(4) В СЛУЧАЕ~$c=1$.

\ex[20] ъАК БЫ ВЫ СОРТИРОВАЛИ ФАЙЛЫ НА НЕСКОЛЬКИХ БОБИНАХ, ИМЕЯ ТОЛЬКО ДВА 
ЛЕНТОПРОТЯЖНЫХ УСТРОЙСТВА?

%% 428
\bye