Třetí série dvacátého pátého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

I v této sérii můžete získat sladkou odměnu! Každému, kdo vyřeší alespoň tři libovolné úlohy na plný počet bodů, pošleme čokoládu.

---

• Termín série: 4. února 2013 8:00
• Termín CodExové úlohy: 5. února 2013 8:00
• Odevzdávání: elektronicky přes Odevzdávátko
• Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
• Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.

Zadání úloh

• 25-3-1: Kontrola docházky
• 25-3-2: Zasedání u kulatého stolu
• 25-3-3: Do třetice sekání
• 25-3-4: Zločinná záležitost
• 25-3-5: Histogram
• 25-3-6: Rytíř a princezny
• 25-3-7: Zkratky
• 25-3-8: Tabulatika

---

25-3-1 Kontrola docházky (12 bodů)

---

Pro řádnou kontrolu docházky je nutno své podřízené přepočítat. Policejní poručík Hamáček na to má svůj systém osvědčený léty služby – ve svém notesu má N dvojic (M_i,K_i). Všechna M_i jsou po dvou nesoudělná a 0≤ K_i<M_i. Celkový počet policistů je menší než součin všech M_i.

Samotná kontrola probíhá v N krocích, v i-tém kroku se příslušníci srovnají do řad po M_i osobách a poručík Hamáček následně zkontroluje, zda odpovídá počet policistů, kteří už nemohli vytvořit celou řadu, hodnotě K_i.

Vrchní referent, strážmistr Borůvka, se stěhuje. Pomozte mu určit k takové, že vygumováním dvojice (M_k,K_k) z poručíkova notesu umožní co největšímu počtu kolegů mu místo porady pomoci se stěhováním.

Poručík nesmí nic poznat, tedy počty nezařazených policistů pro zbývajících N-1 dvojic musí stále odpovídat.

Příklad: Mějme 7157 policistů, kteří se postupně řadí do řad po 12, 13 a 49 osobách. Dvojice (M_i,K_i) tedy jsou (12,5), (13,7) a (49,3). Optimálním řešením je vygumovat dvojici (13,7). Na stanici pak musí zůstat 101 policistů.

Řešení

---

25-3-2 Zasedání u kulatého stolu (10 bodů)

---

Na policejní schůzi se sešlo N příslušníků policejního sboru sedících u kulatého stolu, vzdálenost mezi každými dvěma sousedními policisty je shodná. Schůze je dlouhá, policisté v jejím průběhu všelijak odcházejí a přicházejí. Přítomnost policistů v pravé poledne je zadána jakožto posloupnost N nul a jedniček, kde i-tá jednička znamená, že policista na i-tém místě je na schůzi právě přítomen. Vaším úkolem je zjistit, zda existuje K ≥ 3 takové, že lze vytvořit pravidelný K-úhelník, jehož vrcholy tvoří přítomní policisté.

Příklad: Pro 12 policistů a posloupnost 111010111011 je odpověď kladná, lze sestrojit trojúhelník nebo šestiúhelník. Pro 5 policistů a posloupnost 10111 pravidelný K-úhelník nesestrojíme. Další příklad je na obrázku (plné tečky představují přítomné policisty):

Řešení

---

25-3-3 Do třetice sekání (13 bodů)

---

V této sérii pro změnu trávník vypadá jako jeden řádek čtvercové sítě a je již posekán, nyní je potřeba posvážet posekanou trávu. Vaším úkolem je zanalyzovat, kolik by různé možnosti svozu stály námahy.

Máte zadáno N přirozených čísel udávajících hmotnost trávy na jednotlivých polích a D intervalů [a..b]. Takový interval znamená, že se bude svážet z políček a až b. Námaha pro převoz L trávy z políčka k na políčko l je dána jako L · |k - l|. Pro každý interval určete políčko, na které se dá všechna tráva posvážet s nejmenší celkovou námahou. Celková námaha je součet veškeré námahy, jež byla potřeba pro svezení trávy z celého intervalu na toto políčko.

Pokud existuje více správných políček, vypište libovolné z nich. Výpočty pro jednotlivé intervaly jsou nezávislé, tedy množství trávy na jednotlivých políčcích se mezi intervaly nemění. Složitost algoritmu by měla být optimalizována pro případy, kdy je D řádově stejně velké jako N.

Příklad: (První řádek obsahuje N a D, následují hodnoty L a pak intervaly.)

10 3
10 3 1 3 9 8 5 4 12 9

1 4
3 6
5 9

Odpovědi pro jednotlivé intervaly jsou 1 5 7.

Řešení

---

25-3-4 Zločinná záležitost (10 bodů)

---

Ve špinavých vodách mezinárodního zločinu je obzvláště důležitá organizace, typickým příkladem zločinu je výroba něčeho ilegálního. Výroba probíhá ve fázích a obvykle na více než jednom místě. Převoz z jednoho místa na druhé je nejkritičtější částí výrobního procesu, proto je potřeba počet převozů mezi výrobními místy minimalizovat.

V této úloze budete mít na vstupu popsán výrobní proces ve dvou továrnách. První řádek obsahuje čísla N a M, kde N udává počet výrobních fází a M počet závislostí mezi nimi. Druhý řádek vstupu obsahuje N hodnot, kde i-tá hodnota je 1, pokud má i-tá fáze probíhat v první ilegální továrně, a 2 v případě, kdy má probíhat ve druhé továrně. Následuje M řádků obsahující dvojice a, b, které značí, že fáze b může proběhnout až tehdy, když byla provedena fáze a.

Určete pořadí fází výrobního procesu tak, aby každá fáze proběhla až poté, co jsou provedeny všechny fáze, na kterých je závislá, a aby počet převozů mezi výrobními místy byl minimální. Převoz je nutný vždy, když po fázi probíhající v továrně 1 bezprostředně následuje fáze v továrně 2, nebo naopak. (Můžete předpokládat, že řešení existuje.)

Lehčí varianta (za 6 bodů): Nabízíme k řešení i jednodušší variantu úlohy, kde všechny fáze probíhají v jediné továrně.

Příklad:

7 9
2 2 1 1 1 2 1
2 1
2 5
3 2
3 4
4 1
4 5
4 7
5 6
6 7

Potřebujeme alespoň 4 převozy. Výroba může proběhnout takto – začneme v první továrně, provedeme v ní fáze 3 a 4, pak se přesuneme do druhé továrny a provedeme fáze 2 a 1. Následují fáze 5 v první továrně a 6 v druhé továrně, končíme po čtvrtém převozu v první továrně fází 7.

Řešení

---

25-3-5 Histogram (9 bodů)

---

Jedním z četně používaných typů grafů je histogram. Histogram je, jak praví Wikipedie, grafické znázornění distribuce dat pomocí sloupcového grafu se sloupci stejné šířky. Máte zadán histogram jakožto posloupnost N přirozených čísel udávajících výšky sloupců, šířka sloupců je jednotková. Určete obsah největšího obdélníka rovnoběžného s osami, který lze do grafu umístit tak, že celá jeho plocha leží na sloupcích histogramu.

Příklad: Pro 7 sloupců a výšky 3 6 7 4 2 3 1 je výsledný obsah 12. Existují hned 4 různé obdélníky s tímto optimálním obsahem. Další příklad s jednoznačným řešením je na obrázku:

Řešení

---

25-3-6 Rytíř a princezny (10 bodů)

---

Rytíř v dalekém království se vydal na hrdinnou výpravu. Trasa jeho výpravy vypadá jako N polí uspořádaných do řádku. Na každém poli se nachází buď drak, který má u sebe H zlatých mincí, nebo princezna, která má koeficient krásy K. Rytíř se pohybuje při své výpravě z prvního políčka na poslední a je dostatečně silný na to, aby zabil kteréhokoliv draka po cestě. Je jeho volbou, zda draka zabije a získá mince, či jej obejde a ponechá drakovi život i mince.

V okamžiku, kdy přijde k princezně o kráse K, nastávají dvě možnosti. Pokud již rytíř zabil alespoň K draků, princezna se do něj zamiluje a chce si jej vzít. Rytíř není schopen odmítnout a jeho výprava končí. Pokud rytíř zabil menší počet draků, prohodí pár zdvořilých slov s princeznou a pokračuje ve výpravě.

Na posledním políčku sídlí princezna, kterou rytíř miluje. Pro zadanou trasu výpravy určete, zda je možné získat princeznu na posledním poli. Pokud ano, vypište seznam zabitých draků tak, aby rytíř získal nejen princeznu na posledním poli, ale i co nejvíce zlatých mincí.

Tato úloha je praktická a řeší se ve vyhodnocovacím systému CodEx. Přesný formát vstupu a výstupu, povolené jazyky a další technické informace jsou uvedeny v CodExu přímo u úlohy.

Řešení

---

25-3-7 Zkratky (7 bodů)

---

Svět je plný zkratek, nejen těch policejních. V této úloze máte zadáno nejvýše 10 zkratek o nejvýše pěti písmenech a slovo délky L. Vaším úkolem je rozhodnout, zda lze slovo sestavit ze zadaných zkratek. Zkratky je možno spojovat za sebe a jednu zkratku lze použít i opakovaně.

Příklad: Pokud bychom jako zkratky měli oblíbenou čtveřici sus, usu, sss, Ssu a ještě pro obohacení su. Pak slovo Ssusss postavit půjde, slovo sususu také a rovnou dvěma způsoby, ale slova ssss nebo susSus už nepostavíme.

Řešení

---

25-3-8 Tabulatika (13 bodů)

---

Upozornění: Přesný vzhled vysázených konstrukcí je v PDF verzi! Ve webové verzi mohou být různé nepřesnosti, zvláště u vzhledu vysázených vzorců. Pokud si tedy chcete být jisti tím, jak něco vypadá, sáhněte prosím po verzi v PDF.

Třetí díl seriálu o TeXu bude snad méně děsivý než druhý. Nebojte, budeme se věnovat „jenom“ tabulkám, pokročilé matematice a podrobnostem sazby odstavců.

Sazba na tabulátory

Nejjednodušší tabulky můžeme sázet jednoduchým způsobem. Následující konstrukcí rozdělíme stránku na 3 stejně široké sloupce a pak do nich sázíme řádky:

\settabs 3\columns
\+Sloupec 1&Sloupec 2&Sloupec 3\cr
\+&Jen druhý\cr
\+První&&a třetí\cr
\+Vykřičník je ve čtvrtém sloupci~-- mimo&&&!\cr
\+První sloupec je příliš dlouhý&
  a druhý se přesází přes něj.\cr
\+Mezery za \&&     se ignorují.\cr
\+\hfill Tento řádek&\hfill je zarovnán
  &\hfill na pravý okraj.&\cr

Ukončení tabulky se nijak zvlášť neřeší.

Poznámka: Důvod, proč zde má \hfill najednou dvě L, vysvětlíme v tomto díle seriálu v kapitole o různých typech lepidla.

Nelíbí se vám stejně široké sloupce? Vymyslete si vzorový řádek, podle kterého TeX nastaví šířky sloupců:

\settabs\+První sloupec &Druhý sloupec
         &Třetí sloupec &Zbytek&\cr
\+A&B&C&D&E\cr
\+První sloupec &Druhý sloupec
 &Třetí sloupec &Zbytek&!\cr

Vzorový řádek se nezobrazí, jen se podle něj nastaví šířka sloupců.

Úkol 1 [2b]

Vysázejte pomocí tabulátorů tuto jednoduchou tabulku z knihy jízd:

Správně odsazený zdrojový kód

Tabulátory vůbec nemusí být extra pevné. Můžeme zrušit všechny tabulátorové pozice vpravo od aktuální „buňky“ příkazem \cleartabs. A pokud použijeme mezi \+ a \cr znak & na místě, kde ještě není definovaná tabulátorová pozice, tak se ta pozice jednoduše nadefinuje právě na ono místo.

Víc asi ukáže příklad:

\cleartabs
\+{\bf if} $x<0$: &{\bf if} $x<-1000$:
  &{\it print} \uv{$x$ je echt záporné}\cr
\+&{\bf else}:
  &{\it print} \uv{$x$ je trochu záporné}\cr
\+{\bf else}: &\cleartabs{\bf if} $x>0$:
  &{\it print} \uv{$x$ je kladné}\cr
\+&{\bf else}: &{\it print} \uv{$x$ je nula}\cr

Tabulky

Při sazbě na tabulátory je potřeba odhadnout, který sloupec bude jak dlouhý, a podle toho nastavit šířku sloupců. Také pokud chcete tabulku s orámováním, nemáte moc rozumných možností. TeX však nabízí mocnější nástroj než sazbu na tabulátory – primitivum \halign.

Tabulku z úkolu 1 vysázíme primitivem \halign takto:

\halign{
# \hfil&# \hfil&# \hfil& \hfil#\cr
\it Odkud&\it Kam&\it Kdy&\it Kolik km\cr
Praha&Olomouc&21. 12.&250\cr
Olomouc&Uherské Hradiště&30. 12.&130\cr
Uherské Hradiště&Vyšší Brod&5. 1.&350\cr
Vyšší Brod&Jablonec nad Nisou&17. 2.&324\cr
}

Tabulka se skládá z jednotlivých řádků oddělených od sebe značkou \cr. Buňky se od sebe oddělují znakem & (nebo jiným znakem kategorie 4 – alignment).

První řádek obsahuje vzor. V každé buňce musí být znak # (kategorie 6 – parameter) právě jednou (jinak vám TeX vynadá), jinak může být vzorem prakticky libovolný kus TeXu, který se dá použít uvnitř hboxu (třeba \bye není povolený příkaz). Buňky se pak sází tak, že se v příslušném vzoru nahradí výskyt znaku # za obsah buňky.

Dejte si pozor na mezery – mezery za & se ignorují, mezery před & se neignorují.

Tabulky a boxy

Při sazbě tabulky si TeX zjistí pro každý sloupec, jak bude široký, a podle toho nastaví šířku všem jeho buňkám. Každá buňka tabulky je separátní hbox široký právě tak jako celý sloupec. Pokud nechcete mít ošklivě roztažené mezery v textu, vložte na vhodné místo \hfil-y, vizte příklad výše.

Očárovaná tabulka

Potřebujete-li do tabulky vložit vodorovnou čáru (nebo libovolný jiný materiál), využijte prostředí \noalign. Tím začne vertikální box šířky přesně takové, jak je široká celá tabulka:

\halign{
\strut# \hfil&# \hfil&# \hfil& \hfil#\cr
\it Odkud&\it Kam&\it Kdy&\it Kolik km\cr
\noalign{\hrule\smallskip\line{\hfil
    2012 \hfil}\smallskip\hrule\smallskip}
Praha&Olomouc&21. 12.&250\cr
Olomouc&Uherské Hradiště&30. 12.&130\cr
\noalign{\hrule\smallskip\line{\hfil
    2013 \hfil}\smallskip\hrule\smallskip}
Uherské Hradiště&Vyšší Brod&5. 1.&350\cr
Vyšší Brod&Jablonec nad Nisou&17. 2.&324\cr
}

Potřebujeme-li i svislé čáry, je náš úkol o poznání složitější. TeX totiž vkládá každý řádek tabulky samostatně do stránkového vboxu jako jednotlivé hboxy. Takže mezi ně vloží \lineskip nebo \baselineskip. Proto je musíme vypnout a výšky řádků nastavit explicitně. Na vypnutí lineskipů „pořádně a důkladně“ použijte makro \offinterlineskip, které myslí i na zběsilé okrajové případy.

Aby byl každý řádek stejně vysoký, je potřeba do něj vložit vzpěru. Jinak by sazba vypadala ošklivě. K tomu se hodí makro \strut, které je v Plain TeXu definováno přibližně takto:

\def\strut{\vrule height 8.5pt
           depth 3.5pt width 0pt\relax}

{\offinterlineskip
\def\higher{\vrule height 11pt
            depth 3.5pt width 0pt\relax}
\halign{%
\strut# \hfil&# \hfil\vrule\ &# \hfil& \hfil#\cr
\it Odkud&\it Kam&\it Kdy&\it Kolik km\cr
\noalign{\hrule\smallskip\line{\hfil
    2012 \hfil}\smallskip\hrule}
\higher Praha&Olomouc&21. 12.&250\cr
Olomouc&Uherské Hradiště&30. 12.&130\cr
\noalign{\hrule\smallskip\line{\hfil
    2013 \hfil}\smallskip\hrule}
\higher Uherské Hradiště&Vyšší Brod&5. 1.&350\cr
Vyšší Brod&Jablonec nad Nisou&17. 2.&324\cr
}}

Ještě se vám můžou hodit dvě tabulkové operace: \omit na začátku buňky dočasně nahradí vzor pro tuto buňku za prosté #.

Místo & v běžném řádku můžete použít \span. V tu chvíli se příslušné dvě buňky spojí. To, co bylo před \span-em, se vloží na místo prvního #, a to, co je za \span-em, se vloží na místo druhého #.

{\offinterlineskip
\halign{
\strut1A#1B\hfil\vrule&\ 2A#2B\hfil\vrule
   &\ 3A#3B\hfill\cr
x&y&z\cr
\omit\strut x x&y\span z\cr
\omit\strut\hfil x\span\omit y&z\cr
xxx& yyy& zzz\cr
x\span y\span z\cr
\omit\span\omit\span\omit
   \strut\hfil abcde\hfil\cr
}}

Podrobnosti o tom, jak se vlastně TeX v tabulkách chová, si najděte v TeXbooku v kapitole 22 (nebo v TBN (Petr Olšák: TeXbook naruby, Konvoj Brno 2001 (2. vydání), ISBN 80-7302-007-6) v kapitole 4) – překračuje to rámec tohoto seriálu.

Úkol 2 [6b]

Definujte makra pro sazbu výsledkové listiny KSP. Zdroják výsledkovky pak může vypadat například takto:

\vysledkovka{
\radek 1. Petr Pilný (GABCD; 4; 7):
       12 7 - 4 9 5 - 7: 49,4 69,3
\radek 2. ...
}

Pokud se vám nelíbí současný desing naší výsledkovky, navrhněte lepší a přehlednější.

Poznámka: Pokud byste potřebovali tabulku ne po řádkách, ale po sloupcích, zkuste \valign. Funguje to stejně jako \halign, jenom otočeně.

Periodická hlavička

Zdvojíte-li v hlavičce na nějakém (nejvýše jednom) místě &, říkáte tím TeXu: „Zde začíná periodická část hlavičky.“ Tedy pokud by v nějakém řádku došly vzory pro buňky, tak začne recyklovat vzory od && dál:

\halign{1# & 2# && 1P# & 2P# \cr
A&B&C&D&E&F&G&H&I&J&K&L\cr
A&B&C&D&E&F&G\cr
}

Tolik k tabulkám.

Matematické závorky

Ve druhé části poněkud rozkouskovaného třetího dílu se budeme věnovat složitějšímu využití matematického módu.

Složité vzorce jsou často různě zběsile vysoké a jedna velikost závorek nestačí. Prohlédněte si příklad:

TeX si umí určit velikost závorek sám, jen je potřeba mu říct, která patří ke které. Používají se k tomu primitiva \left a \right, kterými se označí příslušné závorky:

$$\left(\sqrt{
    \left(x + \sqrt{x - 1}\right)
    \left(\sum_{k=1}^\infty {1 \over k^2}\right)
  }\right)$$

TeX sám zvolí velikost závorek takovou, aby byly vhodně vysoké. Pokud byste potřebovali, aby se jedna ze závorek nezobrazila, použijte místo ní tečku:

\left({x\over y}\right.

Typů závorek je hrozná spousta, Plain určitě zná tyto:

$$()[]\{\}\vert\Vert\lceil\rceil
  \lfloor\rfloor\langle\rangle
  \backslash/\uparrow\downarrow
  \Uparrow\Downarrow\updownarrow\Updownarrow$$

Pokud byste čirou náhodou potřebovali použít jiné závorky, konzultujte TeXbook, kapitolu 17 a následující (nebo TBN, kapitolu 5).

Může se vám však stát, že potřebujete jinak velkou závorku, než vám dá TeX. V takovém případě jsou pro vás připraveny varianty \big, \bigg, \Big a \Bigg:

$\Bigg(\bigg(\Big(\big(()\big)\Big)\bigg)\Bigg)$

Zákulisí matematické sazby

Ani celý rozsah seriálu by zdaleka nevystačil na vyložení sazby matematiky v celé její kráse a síle. Donald Knuth na to v TeXbooku vynaložil přes 60 stran. Naznačíme si však některé principy, které by vám při pokročilé sazbě neměly zůstat utajeny.

TeX umí velmi sofistikovaně rozložit mezery do matematického vzorce, pokud ví, jakého typu je která část vzorce. Rozlišuje těchto 13 typů:

Poznámka: PlainTeX má v matematice definována tato diakritická znaménka:

Používají se stejným způsobem jako nematematická.

Poznámka: \vcenter je explicitní vbox v matematickém módu, který je stejně vysoký jako hluboký, takže se vysází centrovaný na osu. Vůbec, matematika se sází ne na účaří, ale na pomyslnou vodorovnou osu, neboť vzorce jsou často takto symetrické. Ale toho už jste si jistě všimli.

Mezi jednotlivými kategoriemi je pak definována tabulka, která určuje, kam patří jak velká mezera. Tato tabulka je pro drtivou většinu použití dostačující.

Pokud vám připadá, že TeX nějakou mezeru určil chybně, zkuste označit atomy v jejím okolí jejich typem. K tomu použijte \mathord, \mathop, \mathbin, \mathrel, \mathopen, \mathclose, \mathpunct a \mathinner. Zbytek typů se značí automaticky a nelze je označit ručně.

Pokud selže i označení atomu vhodným typem, můžete použít mezery různých velikostí – \,, \; nebo \!:

$$x\!y\quad xy\quad x\,y\quad x\;y$$

Matematický mód se dělí na několik dílčích módů. Všimněte si, jak se vysází různé výrazy na různých místech – $$\sum$$, $\sum$, $x^{\sum}$ či $x^{x^{\sum}}$. Nejde jen o velikost, ale také o umístění indexů a rozložení mezer.

Ony dílčí módy jsou D, T, S a SS: „display“, „text“, „script“ a „scriptscript“ uvedené ve stejném pořadí jako v předchozím odstavci.

Chcete-li si vyzkoušet víc magie okolo módů, poradím primitivum \mathchoice:

\def\te{{\mathchoice{D}{T}{S}{SS}}}
$$\te {\te^{\te^\te} \over \te^{\te^\te}}$$

Nebo můžete vynutit konkrétní mód použitím \displaystyle, \textstyle, \scriptstyle a \scriptscriptstyle.

Tabulkové konstrukce v matematice

Plain TeX definuje některé maticové konstrukce:

$$\pmatrix{a_{11}&a_{12}&\ldots&a_{1n}\cr
           a_{21}&a_{22}&\ldots&a_{2n}\cr
           \vdots&\vdots&\ddots&\vdots\cr
           a_{m1}&a_{m2}&\ldots&a_{mn}\cr}$$

Použití je obdobné jako u tabulek, jen nemusíte definovat vzorový řádek. Matici bez závorek můžete získat použitím \matrix. A na matici s okraji je definováno makro \bordermatrix (vyzkoušejte sami).

Úkol 3 [3b]

Vysázejte tento vzorec:

Sázíme odstavec

Další kousek třetího dílu věnujeme podrobnějšímu náhledu na algoritmus lámání odstavce.

Když se na vstupu objeví něco, co by mělo začít odstavec (znak, \indent (Primitivum \indent explicitně započne odstavec; \indent\indent si vyžádá dvojité odsazení (možno opakovat vícekrát pro vícenásobné odsazení). A konečně explicitní začátek odstavce bez odsazení vynutíte primitivem \noindent.), …), zkontroluje TeX několik věcí. Na začátek horizontálního boxu, který bude později zalámán na jednotlivé řádky v odstavci, se vloží prázdné místo velikosti \parindent (pokud nebyl odstavec zahájen pomocí příkazu \noindent).

Pak se expanduje \everypar, což je seznam tokenů (pseudomakro), které se má vložit na začátek každého odstavce. Přiřazuje se do něj zavoláním \everypar={něco}. Standardně je prázdný. Pak se do horizontálního boxu postupně vkládají znaky, dokud se neobjeví \par.

Nyní se na úplný konec boxu vloží prázdné místo velikosti \parfillskip (standardně \hfil). Pak se TeX pokusí zalámat odstavec s přihlédnutím k nastavenému tvaru odstavce. Každý řádek musí obsahovat nejprve prázdné místo velikosti \leftskip, pak příslušný kus odstavce a pak prázdné místo velikosti \rightskip. Dohromady je vždy široký přesně \hsize.

Poznámka: Pro zjednodušení nyní vynecháváme možnost úpravy tvaru odstavce primitivem \parshape a nastavením \hangindent a \hangafter, které nás čekají v další sérii.

TeX se pokouší zalámat odstavec celkem třikrát. Nejprve v mezerách mezi slovy. Pokud mu to nejde, zkusí rozdělit slova podle pravidel pro dělení slov. Pokud se mu ani toto nepovede, zkusí nepatrně roztáhnout mezery a rozdělit slova. Pokud selže i poslední pokus, vyhlásí chybu, nechá nějaký řádek přetéct a vykreslí slimáka.

Lámání odstavce probíhá najednou, TeX se snaží, aby nebyl jeden řádek ošklivě stažený a hned ten další ošklivě roztažený – má nějaký základní smysl pro estetiku. Nicméně když při druhém a třetím pokusu dělí slova, musí vědět, kde všude může dělit, jinak může odstavec vyjít zbytečně ošklivě. To je ten zásadní důvod, proč jsem v první sérii všem řešitelům bez \language\czech strhával body.

Přesný algoritmus včetně všech podrobností, které jste nikdy nechtěli znát, najdete v TeXbooku v kapitole 14 (nebo v TBN v kapitole 6).

Lepidlo

Prázdné místo je v sazbě důležitá věc. Někdy se s nadsázkou dokonce říká, že celá typografie je věda o prázdném místě. V poslední části tohoto dílu seriálu se naučíme pracovat s jeho roztažností.

TeX nahlíží na prázdné místo jako na kusy „lepidla“, které se může různě roztahovat a smršťovat. Český odborný název je „výplněk“. Je několik druhů roztažnosti:

Pevný výplněk svoji velikost nemění. Je vždy stejně velký:

\hbox{A\hskip 2cm\relax B}

Omezeně roztažitelný výplněk má základní velikost a meze, kam až se může roztáhnout.

\hbox to 15mm{A\hskip 2cm plus 1cm minus 1cmB}
\hbox to 25mm{A\hskip 2cm plus 1cm minus 1cmB}

Roztažnost nemusí být na obě strany stejná: 10mm plus 5mm minus 3mm

Nekonečně roztažitelný výplněk má základní velikost a jinak se může roztáhnout neomezeně podle potřeby.

\hbox to 5cm{A\hskip 2cm plus 1fil\relax B}
\hbox to 1cm{A\hskip 2cm minus 1fil\relax B}

Nekonečných roztažností jsou tři druhy: fil, fill a filll. Čím víc L, tím agresivněji se roztahuje.

Jeden výplněk je nuda. Co kdyby se někde potkalo více výplňků? Když TeX skládá box, u kterého dopředu neví, jak bude velký, tak se vůbec roztažností neřídí. Ideální je vždycky, když se nic natahovat nemusí, takže použije vždy pouze základní velikost. V opačném případě má nařízeno, jak musí být výsledný box velký, a musí se do něj chtě nechtě vejít.

Pokud je nutné roztahovat a stahovat bílé místo, TeX určí správné mezery přibližně takovýmto algoritmem:

1. Zjistí, jakou velikost by měl box, kdyby se použily základní velikosti. Určí rozdíl mezi požadovanou a základní velikostí. Je-li rozdíl kladný, bude nás dále zajímat pouze kladná roztažnost; je-li rozdíl záporný, budeme řešit pouze zápornou roztažnost. Tento rozdíl si označme jako w.
2. Sečte povolenou roztažnost přes celý box – zvlášť omezenou a zvlášť každý druh nekonečné roztažnosti.
3. Vybere nejagresivnější roztažnost, která je nenulová, a tou se bude zabývat.
4. Rozpočítá w mezi všechny výplňky, které přispěly do roztažnosti, podle poměru, ve kterém přispěly.

Vizte příklad:

\hbox{\vrule
\hbox to 6cm{\strut%
  \hskip 5mm plus 3cm
  \vrule width 1cm
  \hskip 1cm plus 1cm minus 1cm
  \vrule width 1cm
  \hskip 5mm minus 2cm
}\vrule}

Vnitřní hbox má být široký 6 cm. Základní šířka boxu vyjde 0,5+1+1+1+0,5=4 cm, w=6-4=2 cm. Zajímá nás tedy kladná roztažnost. Čáry se neroztahují, řešíme tedy jen skipy: 3+1+0=4 cm, jiná roztažnost není.

Potřebujeme tedy rozdělit 2 cm mezi první a druhý skip v poměru 3 : 1, tedy prvnímu skipu se přidělí 15 mm a druhému 5 mm. Box se tedy vysází, jako by byl zadán takto:

\hbox to 5cm{\hskip 20mm\vrule width 1cm
  \hskip 15mm\vrule width 1cm\hskip 5mm}

Druhý příklad bude složitější:

\hbox{\vrule
\hbox to 5cm{%
  \hskip 5mm plus 1fil
  \vrule width 1cm
  \hskip 1cm plus 2cm minus 1cm
  \vrule width 1cm
  \hskip 5mm minus 1fil
}\vrule}

Základní šířka boxu je 5 cm, obsah má základní šířku 4 cm, w=1 cm. Celková kladná roztažnost je 2 cm + 1 fil, takže nás zajímá jen 1 fil. Prvnímu skipu se tedy přidělí celý 1 cm.

Rozmyslete si, co se stane, když:

• poslední hskip nebude mít minus 1fil, ale plus -1fil;
• první hskip bude mít plus 1fill;
• bude hbox to 4cm nebo to 3cm.

Nyní je čas na důležitou poznámku. Roztažnost mají pouze skipy (výplňky), mezi které se počítají i běžné mezery mezi slovy. Všechno ostatní (boxy, čáry) má pevnou velikost, jakmile je to vytvořeno. Není možné vytvořit box, jehož rozměry by byly pružné podle jeho okolí. Najděte si třeba ve své sazbě řádek s hodně roztaženými mezerami a část toho řádku uzavřete do hboxu. Všimněte si, co se stane s mezerami, a zkuste si rozmyslet, proč to tak může být.

Připomínám, že je nanejvýš vhodné si vyzkoušet práci s tabulkami i pokročilou matematikou na uvedených příkladech. Zkuste je dál modifikovat a hrát si s nimi, ať si to všechno důkladně zažijete. Příště budeme konečně programovat.

Úkol 4 [2b]

Vymyslete nastavení parametrů odstavce tak, aby se zarovnal na střed.

Řešení nemusí být univerzální, stačí, aby se zadaný odstavec povedlo vysázet v běžném případě. Nemusíte řešit okrajové případy, kdy je odstavec extrémně krátký apod.

A to bude ze třetí série vše. Těším se na vaše řešení.

Jan „Moskyto“ Matějka

Řešení

Menu