\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