\input style

\proof pREDPOLOZHIM, CHTO V ZDANII IMEETSYA DOPOLNITELXNO $b$~CHELOVEK; 
PERVONACHALXNO ONI NAHODYATSYA V LIFTE, I |TAZH IH NAZNACHENIYA ISKUSSTVENNO 
POLAGAETSYA NULEVYM. lIFT MOZHET FUNKCIONIROVATX V SOOTVETSTVII SO SLEDUYUSHCHIM 
ALGORITMOM, NACHINAYA S~$k$ (TEKUSHCHIJ |TAZH), RAVNOGO~$1$.
\picture{rYAS. 87.  aLGORITM kARPA DLYA LIFTA.}
% !!! v KNIGE NET ZAGOLOVKA
\alg K.(aLGORITM kARPA DLYA LIFTA)
\st[dVIZHENIE VVERH.] iZ $b+c$~LYUDEJ, NAHODYASHCHIHSYA V DANNYJ MOMENT V LIFTE I 
NA |TAZHE~$k$, TOLXKO~$b$, IMEYUSHCHIE SAMOE VYSOKOE MESTO NAZNACHENIYA, 
POPADAYUT V LIFT, OSTALXNYE OSTAYUTSYA NA |TAZHE~$k$.

pUSTX TEPERX V LIFTE NAHODYATSYA $u$~CHELOVEK S NAZNACHENIEM~$>k$ I~$d$ S 
NAZNACHENIEM~$\le k$. (oKAZHETSYA, CHTO~$u=\min (b, u_k)$;
ESLI~$u_k<b$, MY MOZHEM, SLEDOVATELXNO, UVOZITX NEKOTORYH LYUDEJ OT IH MESTA 
NAZNACHENIYA. eTO---IH ZHERTVA DLYA OBSHCHEJ POLXZY). uMENXSHITX~$u_k$ NA~$u$, 
UVELICHITX~$d_{k+1}$ NA~$d$ I ZATEM UVELICHITX~$k$ NA~$1$.

\st[pRODOLZHATX DVIZHENIE VVERH?] eSLI~$u_k>0$, VERNUTXSYA K SHAGU~\stp{1}.

\st[dVIZHENIE VNIZ.] iZ $b+c$~LYUDEJ, NAHODYASHCHIHSYA V DANNYJ MOMENT V LIFTE 
ILI NA |TAZHE~$k$, TOLXKO~$b$, IMEYUSHCHIE SAMOE NIZKOE MESTO NAZNACHENIYA, 
POPADAYUT V LIFT, OSTALXNYE OSTAYUTSYA NA |TAZHE~$k$. pUSTX TEPERX V LIFTE 
NAHODYATSYA $u$~CHELOVEK S NAZNACHENIEM~$\ge k$ I~$d$ S NAZNACHENIEM~$<k$. 
(vSEGDA OKAZYVAETSYA, CHTO~$u=0$, a~$d=b$, NO ALGORITM OPISYVAETSYA 
ZDESX PRIMENITELXNO K OBSHCHIM~$u$ I~$d$, CHTOBY SDELATX DOKAZATELXSTVO 
NESKOLXKO PROZRACHNEE.) uMENXSHITX~$d_k$ NA~$d$, UVELICHITX~$u_{k-1}$ NA~$u$ 
I ZATEM UMENXSHITX~$k$ NA~$1$.

\st[pRODOLZHATX DVIZHENIE VNIZ?] eSLI~$k>1$ I~$u_{k-1}>0$, VERNUTXSYA K 
SHAGU~\stp{3}. eSLI~$k=1$ I~$u_1=0$, ZAKONCHITX ALGORITM (VSE LYUDI 
DOSTAVLENY NA SVOE MESTO NAZNACHENIYA, A $b$~"DOPOLNITELXNYH" LYUDEJ SNOVA 
NAHODYATSYA V LIFTE). v PROTIVNOM SLUCHAE VERNUTXSYA K SHAGU~\stp{2}
\algend

nA RIS.~88 POKAZAN PRIMER RABOTY |TOGO ALGORITMA DLYA ZDANIYA S DEVYATXYU 
|TAZHAMI I~$b=3$, $c=2$. zAMETIM, CHTO ODNA IZ SHESTEROK VREMENNO 
PEREMESHCHAETSYA OT SVOEGO MESTA NAZNACHENIYA, NESMOTRYA NA TO CHTO LIFT PROHODIT 
MINIMALXNO VOZMOZHNOE 
%%426
RASSTOYANIE. pROVERKA~$u_{k-1}$ NA SHAGE~K4 YAVLYAETSYA, KAK MY UVIDIM,
RESHAYUSHCHIM MOMENTOM DLYA PRAVILXNOJ RABOTY ALGORITMA.

chTOBY PROVERITX PRAVILXNOSTX |TOGO ALGORITMA, ZAMETIM, CHTO SHAGI~K1 I~K3 
VSEGDA PODDERZHIVAYUT MASSIVY~$u$ I~$d$ V SOOTVETSTVII S TEKUSHCHIM 
POLOZHENIEM, ESLI SCHITATX LYUDEJ V LIFTE NAHODYASHCHIMISYA NA TEKUSHCHEM |TAZHE~$k$. 
tEPERX MOZHNO DOKAZATX PO
\picture{rIS.~88. oPTIMALXNYJ SPOSOB PERERASPREDELENIYA LYUDEJ PRI POMOSHCHI 
  NEBOLXSHOGO MEDLENNOGO LIFTA. (kAZHDYJ CHELOVEK PREDSTAVLEN NOMEROM |TAZHA, 
  NA KOTORYJ ON NAPRAVLYAETSYA.)
}
INDUKCII, CHTO V NACHALE KAZHDOGO SHAGA IMEYUT MESTO SLEDUYUSHCHIE SVOJSTVA:
$$
\displaylinesno{
u_l=d_{l+1}  \rem{PRI $k\le l < n$;} & (6) \cr
u_l=d_{l+1}-b \rem{PRI $1\le l < k$;} & (7) \cr
\hbox{ESLI } u_l=0 \hbox{ I } k\le l < n, \hbox{ TO } u_{l+1}=0. & (8) \cr
}
$$
kROME TOGO, V NACHALE SHAGA~K1 V LIFTE ILI NA |TAZHE~$k$ NAHODYATSYA 
$\min(u_k, b)$~CHELOVEK S NAIVYSSHIMI NAZNACHENIYAMI SREDI VSEH LYUDEJ NA 
|TAZHAH~$\le k$ S NAZNACHENIYAMI~$>k$. v NACHALE SHAGA~K3 V LIFTE ILI NA 
|TAZHE~$k$ NAHODYATSYA $\min(d_k, b)$~CHELOVEK S NAINIZSHIMI NAZNACHENIYAMI 
SREDI VSEH LYUDEJ NA |TAZHAH~$\ge k$ S NAZNACHENIYAMI~$<k$. eTI USLOVIYA 
TAKZHE MOZHNO PROVERITX INDUKTIVNO, ESLI PROSLEDITX, KAK MY POPADAEM V 
SHAGI~K1 ILI~K3 (SM.~UPR.~5).

iZ |TIH SVOJSTV SLEDUET, CHTO ZAMECHANIYA V SKOBKAH NA SHAGAH~K1 I~K3 
SPRAVEDLIVY. kAZHDOE VYPOLNENIE SHAGA~K1, SLEDOVATELXNO, 
UMENXSHAET~$\ceil{u_k/b}$ NA~1 I OSTAVLYAET~$\ceil{d_{k+1}/b}$ BEZ IZMENENIJ.
kAZHDOE VYPOLNENIE SHAGA~K3 UMENXSHAET~$\ceil{d_k/b}$ NA~$1$ I
%% 427
OSTAVLYAET NEIZMENNYM~$\ceil{u_{k-1}/b}$. aLGORITM, SLEDOVATELXNO, DOLZHEN 
ZAVERSHITXSYA ZA KONECHNOE CHISLO SHAGOV, I POSLE |TOGO V SILU~(6) I~(8) KAZHDYJ 
CHELOVEK DOLZHEN OKAZATXSYA NA SVOEM |TAZHE.
\proofend

eSLI~$u_k=0$, a~$u_{k+1}>0$, MY IMEEM "NESVYAZNUYU" SITUACIYU;
LIFT DOLZHEN PODNYATXSYA DO |TAZHA~$k+1$, CHTOBY PEREMESTITX LYUDEJ VVERH, HOTYA 
NIKOMU NE NUZHNO PEREEZZHATX S |TAZHEJ~$\le k$ NA |TAZHI~$\ge k+1$. He 
POSTUPAYASX OBSHCHNOSTXYU, MOZHNO SCHITATX~$u_{n-1}>0$; TOGDA LYUBOJ PRAVILXNYJ 
GRAFIK DOLZHEN VKLYUCHATX PO KRAJNEJ MERE
$$
2 \sum_{1\le k < n} \max (1, \ceil{u_k/b})
\eqno (9)
$$
DVIZHENIJ, TAK KAK MY TREBUEM, CHTOBY LIFT VERNULSYA NA PERVYJ |TAZH. gRAFIK, 
DLYA KOTOROGO DOSTIGAETSYA |TA NIZHNYAYA GRANICA, LEGKO SOSTAVITX (UPR.~4).

\excercises
\ex[17] v METODE PUZYRXKA $P\hbox{-GO}$~PORYADKA, OBSUZHDAVSHEMSYA V TEKSTE, 
ISPOLXZUETSYA TOLXKO PRYAMOE CHTENIE I PEREMOTKA. mOZHNO LI MODIFICIROVATX 
ALGORITM TAK, CHTOBY IZVLECHX PREIMUSHCHESTVA IZ \emph{OBRATNOGO} CHTENIYA?

\ex[m26] nAJDITE YAVNYE VYRAZHENIYA V ZAMKNUTOM VIDE DLYA CHISEL~$X_n$, $Y_n$,
 OPREDELENNYH V~(3). [\emph{uKAZANIE:} IZUCHITE RESHENIE URAVNENIYA~(5.2.2-19).]

\ex[38] sUSHCHESTVUET LI METOD SORTIROVKI S DVUMYA LENTAMI, OSNOVANNYJ TOLXKO 
NA SRAVNENII KLYUCHEJ (A NE NA SVOJSTVAH CIFR), DLYA KOTOROGO V NAIHUDSHEM 
SLUCHAE PRI SORTIROVKE $N$~ZAPISEJ PEREMESHCHENIE LENT SOSTAVLYAET~$O(N\log N)$?  
[pRI BYSTROJ SORTIROVKE |TO ZNACHENIE DOSTIGAETSYA V SREDNEM, NO NE V 
NAIHUDSHEM SLUCHAE, A V METODE hENNI I~sTIRNZA (RIS.~86) ONO 
RAVNYAETSYA~$O(N(\log N)^2)$.]

\ex[m23] v ZADACHE O LIFTE PREDPOLOZHIM, CHTO IMEYUTSYA INDEKSY~$p$, $q$, 
PRICHEM~$q\ge p+2$, $u_p>0$, $u_q>0$ I~$u_{p+1}=\cdots=u_{q-1}=0$. 
oB®YASNITE, KAK SOSTAVITX GRAFIK, TREBUYUSHCHIJ NE BOLEE (9)~EDINIC VREMENI.

\rex[m23] vERNO LI SLEDUYUSHCHEE UTVERZHDENIE? pOSLE SHAGA~K1 
ALGORITMA TEOREMY~k NIKTO V LIFTE NE STREMITSYA POPASTX NA BOLEE NIZKIJ 
|TAZH, CHEM NEKTO IZ OSTAVSHIHSYA NA |TAZHAH~$<k$.

\ex[m30] (r.~m.~kARP.) oBOBSHCHITE ZADACHU O LIFTE (RIS.~87) NA SLUCHAJ, 
KOGDA NA |TAZHE~$j$ PERVONACHALXNO NAHODITSYA $c_j$~PASSAZHIROV I |TAZH~$j$ 
SLUZHIT NAZNACHENIEM DLYA $c'_j$~PASSAZHIROV PRI~$1\le j \le n$. pOKAZHITE, 
CHTO SUSHCHESTVUET GRAFIK RABOTY, RASSCHITANNYJ NA 
$2\sum_{1\le k < n} \max (1, \ceil{u_k/b}, \ceil{d_{k+1}/b})$~EDINIC 
VREMENI, PRICHEM NA |TAZHE~$j$ 
NIKOGDA NE OKAZYVAETSYA ODNOVREMENNO BOLEE $\max (c_j, c'_j)$~PASSAZHIROV. 
[\emph{uKAZANIE:} VVEDITE, ESLI NEOBHODIMO, FIKTIVNYH LYUDEJ, 
CHTOBY SDELATX~$c_j=c'_j$ PRI VSEH~$j$.]

\ex[m40] (r.~m.~kARP.) oBOBSHCHITE ZADACHU IZ UPR.~6, ZAMENIV LINEJNYJ PUTX, 
PROHODIMYJ LIFTOM, NA SETX DOROG, PO KOTORYM MOZHNO EZDITX NA AVTOBUSE, 
PRI USLOVII, CHTO SETX OBRAZUET LYUBOE \emph{SVOBODNOE DEREVO.} aVTOBUS 
IMEET KONECHNUYU EMKOSTX, I ZHELATELXNO PEREVEZTI PASSAZHIROV K IH MESTAM 
NAZNACHENIYA TAK, CHTOBY AVTOBUS PROSHEL MINIMALXNOE RASSTOYANIE. 

\ex[m32] pUSTX V ZADACHE O LIFTE, RAZOBRANNOJ V TEKSTE, $c=1$. 
sKOLXKO PERESTANOVOK IZ $n$~CHELOVEK PO $n$~|TAZHAM DADUT V~(4) $u_k \le 1$ 
PRI~$1 \le k \le n$? [nAPRIMER, $3\,1\,4\,5\,9\,2\,6\,8\,7$---TAKAYA PERESTANOVKA.]

\rex[m25] nAJDITE VAZHNUYU SVYAZX MEZHDU SHEJKER-SORTIROVKOJ, OPISANNOJ V 
P.~5.2.2 (RIS.~16), I CHISLAMI~$u_1$, $u_2$,~\dots, $u_n$ V~(4) V SLUCHAE~$c=1$.

\ex[20] kAK BY VY SORTIROVALI FAJLY NA NESKOLXKIH BOBINAH, IMEYA TOLXKO DVA 
LENTOPROTYAZHNYH USTROJSTVA?

%% 428
\bye