Pátá série dvacátého pátého ročníku KSP

Poslední sladká odměna v tomto ročníku se již blíží! Čokoládu dostane každý, kdo z libovolných pěti úloh dostane alespoň polovinu možných bodů, které lze získat za tyto úlohy.

Termín odeslání Vašich řešení této série jest určen na 27. května 2013 8:00. Termín odevzdání CodExové úlohy je pak 28. května 2013 8:00. Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

Zadání úloh

Při tlačenici v metru se muž už po několikáté podíval na hodinky. Byl to pobočník vysoce postaveného důstojníka policie a spěchal do práce. Tedy ne že by byl pobočníkem již nějak dlouho, na tohle místo byl přidělený asi před měsícem, ale už stačil zjistit, že šéf nemá rád nedochvilnost.

Konečně dojel na Malostranskou a rychle vyběhl po eskalátorech. Dělníci stále kopali tramvajové koleje, takže i dnes se musel svézt náhradním autobusem. „Tak co, jednou přijdu pozdě. Snad jen, kdyby ten řidič byl dneska obzvláště rychlý…“ pomyslel si při nastupování do nezvykle vypadajícího vozidla.


25-5-1 Cesta autobusem (11 bodů)


Dopravní podnik testuje nový druh autobusu – autobus s roztažitelnou karosérií. Bohužel vytočit se s ním v úzkých uličkách není vždy snadné a vyžaduje to velké řidičské umění.

Představte si plán města jako klasickou čtvercovou síť, volná místa představují ulice a náměstí, na zaplněných políčkách jsou domy, parky, fontány a jiné věci, přes které by autobus projíždět neměl. Autobus obsazuje několik políček za sebou (tedy je to jakýsi obdélník o šířce jedna a délce k) a může jet buď vodorovně, nebo svisle, a to oběma směry (buď jede dopředu, nebo couvá).

Na plánu města je start, cíl a navíc jsou zde nástupní a výstupní zastávky. Pokud autobus projede přes nástupní zastávku, tak se o jedno políčko do délky natáhne (proti směru, ze kterého na políčko přijel), a pokud naopak přes výstupní, tak se zkrátí. Nemůže se však zkrátit na nulovou délku. Zastávkou nelze projet dvakrát těsně za sebou, je nutné mezitím navštívit alespoň jednu jinou.

Aby se autobus mohl otočit, potřebuje dostatek místa. Otáčí se kolem některého ze svých konců, a to tak, že pokud má délku k, musí stát tímto koncem v rohu volného prostoru rozměru k×k. Pak se otočí jako na obrázku a stojí ho to právě jeden krok. Přirozeně, druhý konec autobusu se také musí nacházet v onom volném prostoru.

Příklad k 25-5-1

Vaším úkolem je nalézt nejkratší cestu ze startu do cíle (nemusíte projet všemi zastávkami) takovou, aby autobus projel a měl dostatek místa na otáčení.

Lehčí variantaLehčí varianta (za 6 bodů): Vyřešte to samé, ale bez zastávek (tedy autobus má jen pevnou délku k a během cesty se jeho délka už nemění).

Řešení

Po klikaté jízdě skrz uličky vyběhl pobočník z autobusu a rychle běžel na stanici, kde se měl se šéfem setkat. Cestou minul na dvoře nějaký policejní nástup, místní poručík si asi přepočítával přítomné policisty. To už ale pobočník vešel do budovy a u dveří kanceláře zaslechl hlas šéfa. Zrovna domlouval nějaké odvolání nepohodlného pochůzkáře na jiné místo, jak pobočník pochopil.

„Tak na to se podívejme!“ zamumlal si potichu, aby to nikdo neslyšel. To by zapadalo do obrázku, který si o svém šéfovi udělal během toho měsíce, který u něj zatím strávil. Podivná setkání, divné zprávy, rozkazy a náhody. Začínal mít vážné podezření, že na něj šéf nehraje čistou hru. Zaslechl od kolegů nějaké zvěsti o rozrůstající se japonské mafii.

Chvíli váhal, ale pak se rozhodl. Tuhle nahrávku musel mít celou. Šéf udělal chybu a tenhle rozhovor vedl přes telefon na stanici, který byl samozřejmě nahráván. Opatrně tedy vešel do vedlejší místnosti, zavřel za sebou dveře a posadil se k počítači.


25-5-2 Telefonní ústředna (9 bodů)


Program telefonní ústředny na policejní stanici zaznamenává všechny provedené hovory. Bohužel věcí, co zaznamenává, je spousta, a proto se musí ukládat komprimovaným způsobem.

Všechny záznamy tvoří dohromady posloupnost 0 a 1 dlouhou n. Hovor je identifikovaný konkrétním vzorcem 0 a 1 o délce s, který se v posloupnosti může vyskytovat jako vybraná podposloupnost (Vybraná podposloupnost vznikne z původní posloupnosti čísel tak, že vynecháme některé její prvky. Pořadí zbylých prvků zůstane zachováno.).

Máme zadaný vzorec námi hledaného hovoru a ptáme se, kolik hovorů si budeme muset přinejhorším poslechnout, abychom nalezli ten pravý. Neboli kolik je možností, jak vybrat z celé posloupnosti daný vzorec.

Příklad: Pro posloupnost 010111 existuje 9 způsobů, jak v ní nalézt vzorec 011.

Řešení

„Konečně, už to mám!“ zaradoval se v duchu pobočník. V tom ale málem dostal infarkt. Těžká ruka mu dopadla na rameno. Za ním se ozval šéfův hlas.

„Jane, co to tu děláte?“

„Já… pane… já…“ rychle se pokoušel schovat okno se záznamy hovorů.

Šéf si výpisu záznamů však všiml. Chvíli stál mlčky s rukou na Janově rameni. Jan skoro cítil, jak šéf v hlavě prochází spoustu možností – nedopadne Jan stejně jako předchozí pobočník, o kterém se povídá, že už ho nikdo nikdy neviděl? Pak si to šéf zjevně rozmyslel a jen suše řekl: „Pojďte Jane, půjdeme se někam najíst.“

Jan, nevěda co očekávat, ho následoval. Skoro mlčky došli do blízké restaurace. Jan přemýšlel, jestli nemá utéct, ale nějaký tajemný pocit mu říkal, že teď šéfovi může věřit. Usadili se v osamělém rohu a objednali si jídlo. Mezitím, co Jan opatrně uždiboval špagety, začal mu šéf líčit spoustu věcí.


25-5-3 Špagety (11 bodů)


Představte si špagety v typické italské restauraci v centru Prahy. Je to jakási směs zamotaných těstovin a člověk musí hodně dávat pozor, jak je nabírat, aby si je na sebe při jídle neplácl. Proto je nejlepší odebírat špagety jen z vrchu talíře a netahat je zespoda.

Talíř špaget si můžeme představit jako trojrozměrnou mřížku. Špageta je vždy nějaký souvislý „had“ složený z trojrozměrných jednotkových krychliček, který se může libovolně kroutit. Jednotlivé špagety se v trojrozměrné mřížce vzájemně neprotínají.

Navíc máme daný směr gravitace, tedy osu, ve které budeme špagety postupně jíst. V každém kroku můžeme vzít právě ty špagety, na kterých ve směru této osy neleží žádná jiná špageta (sama na sobě však ležet může, to nám nevadí). Tím se nám uvolní některé další špagety, které zase můžeme odebrat při dalším kroku, a tak dále. Skončíme ve chvíli, kdy buď sníme celý talíř, nebo už nebudeme mít žádnou špagetu volnou.

Vaším úkolem pro zadaný talíř špaget je tedy spočítat minimální počet kroků pro snězení celého talíře a vypsat špagety odebírané v každém kroku, nebo určit, že špagety sníst nelze. Jako vstup můžete předpokládat popis celého talíře po jednotlivých souřadnicích (tedy buď se na souřadnici nachází kus nějaké určité špagety, nebo je zde volné místo).

Lehčí variantaLehčí varianta (za 5 bodů): Uvažujte jen rovinnou situaci, tedy když se špagety budou proplétat jen ve dvou rozměrech a odebírat je budeme ve směru jedné z os.

Řešení

„To snad nemyslíte vážně, pane!“ řekl Jan, když konečně dojedl špagety. Během uplynulých dvaceti minut se mu úplně převrátil pohled na šéfa. Žádný mafián, agent speciálního útvaru policie to byl!

„Dobře jste všechny okolo vodil za nos. A proč jste si vlastně vybral mě?“

„Inu Jane, to byla součást plánu. Mafiány nejlépe dostanete zevnitř. A proč jsem si vybral vás? Nejste z Prahy, takže vás nemůžou znát, vaše hodnocení ze služby v Brně je přímo ukázkové a můj kamarád, šéf vašeho okrsku, mi vás doporučil. A navíc jste byl rok v Japonsku a prý umíte trochu japonsky, což se možná bude hodit. Ale teď –“ náhle ho přerušil telefon.

Šéf rychle prohodil několik slov do telefonu a pak se na Jana podíval. „Ale teď provedeme pár výslechů, poručíkovi zdejšího oddělení Hamáčkovi se právě povedlo udělat razii v nějakém čínském bistru,“ zlověstně se usmál.


25-5-4 Výslechy (11 bodů)


Policii se povedlo při razii v čínském bistru zadržet několik osob. Bohužel nevíme, kdo z nich je spořádaný zaměstnanec bistra a kdo z nich je mafián. Jediné, co víme, je, že mafiáni vždy lžou a zaměstnanci bistra vždy mluví pravdu.

Máme množinu výroků dvou typů: „A tvrdí, že B je mafián“ a „A tvrdí, že B není mafián“. Protože policisté chtějí mít při rozklíčování této situace alespoň nějaká vodítka, chtějí po vás zjistit počet možných řešení, neboli počet různých způsobů, kterými lze podezřelé označit za mafiány nebo zaměstnance bistra. Počet chceme spočítat modulo nějakou konstantou K (tedy tato úloha není myšlená jako úloha na velká čísla).

Navíc byste měli poznat, pokud si výpovědi nějakým způsobem protiřečí. Přesně řečeno že neexistuje žádné možné rozdělení na mafiány a zaměstnance, které by při daných výrocích dávalo smysl (v tom případě se pak už policisté nějak zařídí).

Příklad: Pro množinu tří osob A, B a C a pro výroky: „A tvrdí, že B je mafián“ a „A tvrdí, že C není mafián“ máme jen dvě možnosti: A a C jsou mafiáni a B zaměstnanec bistra, nebo přesně naopak. Kdybychom k nim však přidali ještě osobu D, tak se nám počet možností zdvojnásobí (protože D může být v obou případech jak mafián, tak zaměstnanec bistra).

Řešení

Výslechy byly zdlouhavé a táhly se až do večera. Nakonec ale Jan se šéfem zjistili něco, co se jim vůbec nelíbilo. Vypadá to, že právě teď se chystá velká dodávka nelegálního zboží.

Aby toho nebylo málo, tak hned venku přinesl nějaký rychlý posel šéfovi zprávu. Šéf si ji přečetl a pak zaklel. To bylo poprvé, co ho Jan slyšel mluvit sprostě.

„Právě dostali mého člověka. Nevím, jak se o něm doslechli, ale leží ve vážném stavu v nemocnici. Dnes večer měl domluvenou tajnou schůzku s konzulem, měl hrát prostředníka jistému bohatému podnikateli.“

Šéf chvíli přemýšlel. Pak ho něco napadlo. Vysvětlil Janovi svůj plán.

Jan chvíli přemýšlel. To, co po něm šéf chtěl, nebylo lehké. Jestli tohle vyjde, můžou nachytat celou japonskou mafii i s konzulem. Ale pokud ne… Ale co na tom, rodinu nemá, o rybičky se mu doma už někdo postará – „Jdu do toho, pane.“

* * *

V drahém obleku se Jan cítil trochu nesvůj, ale už si na něj zvykal. Jen se bez zbraně na boku a odznaku v kapse cítil jako nahý. Před chvílí navíc minul svého starého známého, jednoho z pochůzkářů. Jen tak tak, že ho nepředvedl na služebnu, když přebíral aktovku s dokumenty od jednoho kontaktu.

Teď šel rozvážným krokem k japonské ambasádě. Když už byl skoro u ní, všiml si znaveně vypadajících zahradníků. „Zajímavé, jako by celý den vozili sem a tam trávu,“ podivil se. Teď už to vypadalo, že zahradu u ambasády konečně uklízí.


25-5-5 Úklid trávníku (9 bodů)


Zahradníci starající se o trávník u japonské ambasády jsou po celém náročném dni už silně unavení, ale ještě na ně čeká poslední úkol. Musí z posekané trávy vybrat reprezentativní vzorek, který pošlou do laboratoře na rozbor, jestli je trávník zdravý.

Na sběr trávy používají zmenšenou verzi balíkovacího stroje, kterým se tráva svazuje do malých krychlových úhledných balíků. Do laboratoře chtějí zaslat právě k náhodně vybraných balíků z celého trávníku, ale neví, na kolik balíků sběr vší posekané trávy vyjde.

Chtějí tedy od vás nějaký postup, jak z posloupnosti balíků neznámé délky vybrat právě k balíků. Každá k-tice balíků musí mít stejnou pravděpodobnost, že bude vybrána. Již prošlé balíky nelze vracet (nakládají se na valník a ten je odváží na kompost), tedy nelze si počet balíků nejdříve spočítat a pak teprve vybírat. Vše je nutné udělat během jednoho průchodu.

Lehčí variantaLehčí varianta (za 4 body): Řešte úlohu pro k=1, tedy pokud chceme vybrat jen jeden náhodný balík.

Řešení

To už ale Jan došel na ambasádu a nechal se uvést ke konzulovi. Ještě než mohl konzul cokoliv říct, tak Jan spustil.

„Předně bych vám chtěl poděkovat, pane Yamado. Nevím, jak ten špeh ke mně proklouzl, ale příště budu své lidi mnohem více prověřovat. Jsem vám zavázán. A teď bychom se mohli věnovat započatému obchodu,“ uctivě se uklonil. Pokoušel se držet si sebejistou tvář, ale srdce měl strachem až v krku.

„Takže pan Kebner osobně, jsem rád, že konečně vidím vaši tvář.“ Luskl prsty a rázem přiskočili dva bodyguardi, kteří ho během pár sekund prohledali a pak rychle kývli na konzula. „V pořádku, chtěl jsem si být jistý. Posadíte se a dáte si se mnou partičku Triád? Můžeme nad nimi prodiskutovat tu množstevní slevu, kterou jste navrhoval.“

Jan, potěšen, že mu konzul zatím věří, se s ním posadil nad herní stolek. Bohužel konzul byl příliš dobrý a Jan stále vystrašený, takže konzul snadno vyhrál. Během toho mluvili o obchodu a konzulovi nedalo příliš práce požadovanou slevu srazit na minimum. Však Janovi o peníze vlastně ani nešlo. Navzájem si také potvrdili vše, co už dříve domlouval nyní raněný agent, jen změnili data a časy. Mělo to proběhnout již dnes v noci.

Ještě než se však dostali k samotnému naplánování, přerušila je konzulova žena. „Drahý pane, můj milý muži…“ pokoušela se mluvit česky, ale bylo na ní znát, že se musí hodně soustředit. „Dnes já upekla tento… dort se tomu říká u vás?“ Jan přikývl. „Prosím, dejte si.“

Pak potichu odešla. Jan se na dort podíval. Byl celkem malý a již nakrájený, ale docela nepravidelně. Etiketa sice vyžadovala, aby ho celý nesnědl sám, ale měl už děsný hlad, a tak se ho chtěl najíst co nejvíc.


25-5-6 Dělení dortu (11 bodů)


Praktická CodExová úlohaKulatý dort je nakrájený na jednotlivé kousky různé velikosti, kousky mají tvar kruhové výseče. První strávník si vybere jakýkoliv kousek dortu a ten sní. Pak se postupně střídají s druhým strávníkem, dokud nesnědí celý dort. Poté, co už je odebrán první dílek, je možné odebírat pouze z okraje odebrané výseče (tedy vždy jsou na výběr maximálně dva dílky).

Uvažujte, že oba strávníci chtějí sníst co největší množství dortu a že druhý strávník vždy odebírá optimálně. Jaké největší množství dortu může první strávník sníst při použití optimální strategie?

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í

Poté, co dojedli dort – Janovi se povedlo sníst více, což ho trochu zasytilo a dodalo mu sebejistoty – sáhl konzul někam za sebe a spustil umně ukrytý projektor. Na zdi se za chvíli objevila celkem podrobná mapa Prahy.

„Tohle už asi znáte, pane Kebnere?“ zeptal se. Jan opatrně přikývl, i když mapu v životě neviděl. Na okrajích bylo pár poznámek v japonštině, které s vypětím sil přelouskal. Popisovaly něco o rozmístění policejních hlídek.

„Teď se ale trochu mění situace. Nevím, proč to plutonium a další věci chcete, ale už si po dnešku nemůžu dovolit nechat si to ve svých skladech. Musíme to provést ještě dnes.“

„Povedlo se mi z jistého zdroje získat aktuální rozestavění policie.“ Po konzulových slovech se Jan opět podíval na mapu. V duchu si oddechl, to důležité tam scházelo. Musel naplánovat trasu předání nelegálního zboží tak, aby to konzulovi nebylo podezřelé, ale tak, aby ho dostal tam, kam potřebuje…


25-5-7 Policejní koridor (13 bodů)


Kuchařková úlohaMáme zadanou mapu města jako neohodnocený neorientovaný graf (křižovatky pospojované ulicemi), na některých křižovatkách stojí policejní kontroly. Dále máme zadaný start, sklad a cíl jako nějaké křižovatky a chceme vyjet ze startu, naložit věci ve skladu a dojet do cíle.

Okolo každé policejní kontroly můžeme projet za celou cestu maximálně jednou. Kdybychom okolo ní projeli vícekrát, tak už jí to přijde podezřelé, zastaví nás a podrobí nás prohlídce – a to přesně nechceme. Současně chceme cestu absolvovat co nejrychleji.

Najděte tedy pro zadanou mapu s policejními hlídkami co nejkratší cestu mezi startem, skladem a cílem tak, aby každou křižovatkou s kontrolou procházela nejvýše jednou.

Lehčí variantaLehčí varianta (za 7 bodů): Zjistěte jen, jestli taková cesta existuje.

Řešení

Janovi se konečně povedlo vymyslet trasu, která vypadala alespoň trochu rozumně. Ukázal ji konzulovi. Ten nad ní chvíli taky váhal, ale pak přikývl. „Tohle vypadá dobře. Ano. Ale pojedete s námi, ať máme jistotu.“ S tímhle Jan nepočítal, chtěl odejít. Ale teď tu operaci přece nemůže pokazit, teď už je to nutné dohrát až do konce, ať bude jakýkoliv. „Dobře, kdy vyrážíme?“

Auto se pomalu blížilo k místu setkání. Celý nákladový prostor byl zaskládán nelegálním zbožím a uprostřed něj trůnila zlověstná bedna se znaky radioaktivity na boku. Jelo pomalu, bez světel.

Na smluveném místě z něj vystoupil jeden muž. Došel doprostřed plácku ohraničeného starými průmyslovými budovami. Tam čekalo druhé auto s jedním osamoceným mužem. První muž se rozhlédl, něco mu tady nehrálo. Najednou se ozvalo několik kovových cinknutí.

Jan věděl, co čekat. Vyskočil z auta, pevně zavřel oči a přitiskl si ruce na uši. Okolí najednou zaplavilo nesnesitelné světlo a zvuk o omračující síle. Šokové granáty. Světlo zmizelo stejně rychle, jako se objevilo. Jan otevřel oči, kopem skolil jednoho z japonských bodyguardů a vrhl se do bezpečí mezi průmyslové budovy.

Plácek mezitím zaplavilo světlo z mnoha reflektorů a výkřiky policie. Mafiáni byli natolik zaskočeni, že se nikdo nezmohl na žádný odpor, nikomu nebylo ublíženo. Během několika sekund složili zbraně a policisté je odvedli.

„Dobrá práce Jane,“ ozvalo se nad ním. Byl to šéf a natahoval ruku, aby mu pomohl se zvednout. „Nechcete pro mě pracovat i dál?“

Závěr příběhu vyprávěného z různých pohledů sepsal

Jirka Setnička


25-5-8 Boxy, z TeXu ven! (15 bodů)


SeriálUpozorně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.

Poslední díl seriálu věnujeme převážně výstupním rutinám a stránkovému zlomu. Vysvětlíme si, jak fungují penalty a špatnost sazby, a stručně si ukážeme okolí TeXu – formáty a nadstavby. Nakonec vložíme obrázek a vysázíme barevný dokument.

Stránkový zlom

TeX při sazbě stránky skládá boxy pod sebe do speciálního vertikálního boxu. Ve chvíli, kdy zjistí, že se už nevejde s výškou sazby do \vsize, najde správné místo, na kterém je nejlepší stránkový zlom, a tam uřízne box. Co se nevešlo, to si schová pro příští stranu.

Nejvýhodnější stránkový zlom se počítá tak, že se mezi každými dvěma položkami v boxu spočítá hodnota

c ={
∞,pokud b = ∞ nebo q ≥ 10 000;
p,pokud p ≤ -10 000;
b+p+q,pokud b < 10 000;
100 000,pokud b = 10 000,

přičemž b je „badness“, hodnota určující ošklivost roztažení nebo stažení stránky při zlomu na tomto místě (Badness spočítáme podle vzorce b=min(10 000, 100 · (g / g0)3), kde g je součet roztažení nebo stažení mezer oproti normálu a g0 je celkové maximální povolené roztažení nebo stažení.); p je penalta, hodnota určující nevhodnost zlomu na tomto místě (například mezi prvním a druhým řádkem odstavce); q je hodnota \insertpenalties, což je součet penalt pro speciální objekty jako poznámky pod čarou odpovídající zlomu.

Jediné, co můžete ovlivnit přímo, je penalta. Uvedete-li \penalty 15, vloží se na to místo penalta s hodnotou 15. Čím nižší penalta, tím spíš se na daném místě zlomí. Penalta -10 000 a nižší vyvolá zlom vždy; penalta 10 000 a vyšší zlom zakáže. Pokud se někde vyskytnou dvě penalty za sebou, jejich hodnoty se sčítají.

Navíc je povoleno lámat jen na některých místech. TeX rozlišuje „zahoditelné“ a „nezahoditelné“ objekty. První z nich se za zlomem zahazují. Jedná se hlavně o penalty a výplňky.

Lámat se pak smí jen před výplňkem, před kterým je něco nezahoditelného, nebo na penaltě. V TeXbooku nebo TBN si to můžete přečíst precizně.

Zde se můžou hodit vysvětlit některé zkratky, které jsme dříve definovali bez vysvětlení:

\def~{\penalty 10000 \ } % nedělitelná mezera
  % Mezera se považuje za výplněk a penalta
  % je zahoditelná ...

\def\break{\penalty-10000 } % zlom vždy
\def\nobreak{\penalty 10000 } % nelámej nikdy
\def\allowbreak{\penalty 0 } % povol zlom
% Na některých místech se nesmí lámat,
% například mezi dvěma čarami.
% Na penaltě se smí lámat vždy.

\def\filbreak{\par\vfil\penalty-200\vfilneg}
% \filbreak využívá skutečnosti, že na začátku
% každé stránky se zahodí všechny skipy.
% Přejde na novou stránku a zbytek vyplní
% prázdným místem, tedy pokud je záporná
% penalta dostatečná.
% Jinak se výplně vyruší:
% \def\vfil{\vskip 0pt plus 1fil}
% \def\vfilneg{\vskip 0pt plus -1fil}
\def\goodbreak{\par\penalty-500 }
\def\eject{\par\break}
\def\supereject{\par\penalty-20000 }
% Penalta -20000 se využívá pro požádání
% výstupní rutiny, aby vysázela všechny
% poznámky pod čarou a podobné elementy.

TeX si pak vybere takové místo, pro které je c nejmenší, a tam uřízne box. Co je před řezem, to vloží do vboxu číslo 255 a spustí výstupní rutinu.

Výstupní rutina

Na místo, kde došlo ke stránkovému zlomu, se vloží {, obsah seznamu tokenů \output a }. Cokoli, co vysázíte během výstupní rutiny, se přilepí před to, co zůstalo za stránkovým zlomem, a pokračuje se dál. Takto se tedy může výstupní rutina rozhodnout, že kus materiálu nevysází, a přesunout jej na další stranu. Na konci výstupní rutiny musí zůstat vbox 255 prázdný.

Dejte si pozor na to, že výstupní rutina se může aktivovat pokaždé, kdy vložíte nějaký materiál do hlavního vboxu, mimo jiné tam, kde se objeví \par, vložení boxu, čára, … Pokud tedy v nějakém makru používáte stejné proměnné jako ve výstupní rutině (například \count0\count9), pohlídejte si, aby se nespustila výstupní rutina zrovna v tu chvíli, kdy je máte předefinované.

Ve výstupní rutině se provedou všechny takové věci jako zvýšení čísla stránky, připojení hlaviček, patiček a poznámek pod čarou. Ve chvíli, kdy je poskládaná celá stránka, zavolá se \shipout a za toto primitivum se vloží box, který tvoří stránku. Tento box se ukotví svým levým horním rohem do bodu vzdáleného 1 in od levého i horního okraje. Tyto hodnoty se dají nastavit jako \pdfhorigin a \pdfvorigin.

Vzniklá stránka má rozměry \pdfpagewidth × \pdfpageheight, leda by nějaký z těch rozměrů byl nastaven na nulu. V takovém případě se příslušný rozměr vypočítá jako x = x0 + 2(f+r), kde x0 je rozměr boxu předhozeného primitivu \shipout, f je \hoffset resp. \voffset a r je \pdfhorigin resp. \pdfvorigin.

Veškeré odložené operace (\write apod.) se provádějí ve chvíli, kdy příslušné místo projde \shipoutem. Je tedy potřeba zajistit, aby všechna použitá makra byla definována v místě výstupní rutiny. Dokonce když zadáváte odložený \write, tak nemusíte mít použitá makra definována, stačí uvnitř výstupní rutiny.

Když se objeví \end, zavolá se výstupní rutina. Pokud po ní něco zbylo, vloží se do výstupu \line{}\vfill\penalty-'10000000000 a znova se zpracovává token \end. Zkuste si předefinovat \line, vysázet extrémně dlouhý odstavec, a uvidíte, co se stane. Ve chvíli, kdy už není co zpracovat, TeX skončí.

Známé makro \bye je definováno takto:

\outer\def\bye{\par\vfill\supereject\end}

Výstupní rutina plainTeXu

\output{\plainoutput}
\def\plainoutput{%
  \shipout\vbox{%
    \makeheadline\box255\makefootline}%
  \advance\pageno by 1 }
\def\makeheadline{\vbox to 0pt{\vskip-22.5pt
  \line{\vbox to8.5pt{}\the\headline}\vss}
  \nointerlineskip}
\def\makefootline{%
  \baselineskip24pt\lineskiplimit0pt
  \line{\the\footline}}

Toto je zjednodušená verze výstupní rutiny plainTeXu. Jejím centrem je makro \plainoutput, které pošle stránku do výstupu a zvýší číslo stránky. Stránku poskládá tak, že nahoru vloží \headline (vhodně vysázenou), pak přidá samotnou stránku \box255 a nakonec připojí \footline.

Ve skutečnosti se ve výstupní rutině plainu dělá trochu víc věcí, například se vkládají poznámky pod čarou.

Může se vám hodit umět nahradit kus výstupní rutiny plainu nějakým jiným kódem. V reálné výstupní rutině je například použito makro \pagebody místo \box255, které si můžete předefinovat.

Stejně tak můžete potřebovat například jinak pozicovanou hlavičku nebo patičku stránky. Stačí předefinovat příslušné makro.

Úkol 1 [3b]

Definujte makro \stopoutput, které vložením do zdrojáku způsobí, že od toho místa dál se na výstup nic nepošle. Definujte také makro \startoutput s opačným efektem, které na výstup data pošle. Vaše makro musí fungovat s libovolnou výstupní rutinou – o jejích vlastnostech nesmíte předpokládat prakticky nic.

Při definici neřešte patologické a okrajové případy, stačí, když bude makro fungovat při obvyklém použití (a dokumentujte, co se v tomto případě myslí obvyklým použitím). Například můžete vyžadovat, aby makro nebylo použito uvnitř explicitního hboxu nebo vboxu, nebo zakázat vnoření.

Může se vám hodit vědět, že TeX inkrementuje čítač \deadcycles pokaždé, když vstupuje do výstupní rutiny. Pokud jeho hodnota přeteče 25, skončí s chybou, neboť se domnívá, že máte ve výstupní rutině chybu a jste zacyklení. Čítač se nuluje při použití \shipout, nebo ho musíte snižovat ručně.

Úkol 2 [9b]

Upravte (vaši nebo vzorovou) implementaci \multicolumn z minulé série tak, že bude možno sázet text a další materiál do více sloupců přes více stran, podobně jako sázíme leták KSP.

Neuvažujte poznámky pod čarou, zkuste však implementovat makro tak, abyste umožnili vnoření. \multicolumn uvnitř jiného \multicolumn prostě vysází vícesloupcovou sazbu uvnitř vícesloupcové sazby.

Stejně tak se pokuste o to, aby se makro chovalo stejně jako v minulé sérii v případě, že jej použijete uvnitř jiného boxu.

Nezapomeňte na dokumentaci.

Formát

Samotný TeX je poměrně holá a osekaná kostra. Umí jen to nejnutnější, zbytek se definuje ve formátu, což je soubor v běžné syntaxi TeXu, který končí příkazem \dump. Tím se vygeneruje komprimovaný vnitřní stav TeXu na konci zpracovávání formátu. Během generování formátu platí omezení, že se nesmí vůbec nic vysázet.

TeX tedy umí pracovat ve dvou módech. První z nich jsme používali celou dobu v seriálu. Vezme uložený formát (v našem případě csplain), načte uložené hodnoty do paměti a zpracovává a sází vstup. Ve druhém módu vezme vstup pro formát a vygeneruje jej. Tomu se také říká iniTeX.

Chcete-li TeXu nařídit, jaký formát použít, použijte na příkazové řádce parametr -fmt a za něj připojte název formátu. Chcete-li TeX spustit jako iniTeX, použijte parametr -ini.

Vzpomenete-li si na první díl a instalaci TeXworks, pak stejně jako pdfcsplain si můžete nastavit TeX s libovolným jiným formátem, když do pole Arguments napíšete správné argumenty.

Například známý LaTeX, ConTeXt a další jsou jen různé formáty pro TeX, stejně jako plain.

Nadstavby

Původní TeX má mnohá omezení. Generuje výstup ve formátu DVI („device independent“), což bývalo užitečné v dobách, kdy ještě tiskárny neuměly žádný jednotný jazyk a příkazy v DVI se překládaly přímo do jazyka konkrétní tiskárny jejím ovladačem. Navíc se pracovalo na řádkových terminálech, kde nebylo možné si požadovaný výstup zobrazit.

Současné tiskárny umí prakticky všechny PostScript a před tiskem si prohlížíte PDF. Vytvářet DVI je tedy prakticky zbytečné. Proto vzniknul pdfTeX, který generuje přímo výstup v PDF. Nad rámec toho, co umí TeX, implementuje další užitečné vlastnosti a funkce, například přímé vkládání obrázků, základní práci s barvami apod. Některá z těchto rozšíření jste už v seriálu potkali, konkrétně všechno, co začíná \pdf...

V dnešním multilingválním a internacionalizovaném světě je TeX se svým 8bitovým chápáním vstupu silně zastaralý. Světem hýbe UTF-8. Situaci se snaží zachránit encTeX, rozšíření, díky kterému je možno mapovat sekvence 8bitových znaků (například znaky z UTF-8) na sekvence tokenů.

Všechny funkce pdfTeXu a encTeXu by vydaly na samostatnou sérii, tak jen poznamenejme, že běžně dodávaný formát plain-utf8-cs se zapnutým encTeXem (argument -enc pro iniTeX) je csplain v UTF-8:

% vygenerování formátu
pdftex -enc -ini plain-utf8-cs
% použití formátu
pdftex -fmt plain-utf8-cs vstup.tex

Jako slibný projekt se pak jeví luaTeX, což je implementace TeXu s možností vkládat do vstupního souboru kusy kódu v jazyce Lua. Ten již pracuje v Unicode a otevírá velmi zajímavé možnosti při psaní maker – některé konstrukce jsou v klasickém TeXu dosti nepraktické, až nemožné (složitější cyklus, opakovaná tokenizace, zavěšená interpunkce apod.). Některé z těchto nedostatků se snaží napravit rozšíření eTeX. Ještě jste se v těch TeXech neztratili?

Obrázky

Obrázky se vkládají primitivem \pdfximage (v pdfTeXu). Je možno nadiktovat si rozměry vkládaného obrázku i další parametry vytvářeného objektu ve výsledném PDF. Kompletní syntaxi a možnosti tohoto primitiva najdete v dokumentaci na webu pdfTeXu.

Primitivum \pdfximage pouze vloží obrázek jako objekt do PDF. Pokud jej chcete vložit do stránky, potřebujete primitivum \pdfrefximage, za které patří číslo objektu. To získáte primitivem \pdflastximage pro poslední obrázek vložený do PDF. (Pokud chcete vkládat jeden obrázek do stránky vícekrát, vložte jej do PDF jen jednou a pak se na něj vícekrát odkažte.)

\pdfximage@width@2cm@height@2cm@depth@1cm@{o.jpg}
\pdfrefximage\pdflastximage

Podporované formáty jsou JPEG pro fotografie, PNG pro bitmapovou grafiku, JBIG2 pro dvoubarevné bitmapy a PDF pro vektorovou grafiku.

Obrázek vložený ve stránce se chová jako vrule, resp. hrule. Pokud s ním potřebujete dělat nějaké speciality, zavřete jej do boxu.

Barvy

Každý objekt vykreslený TeXem má nějakou barvu, základní je černá. Její nastavení není v původním TeXu podporováno. V pdfTeXu je nutno vložit přímo kus kódu z formátu PDF.

Nejjednodušší způsob, jak změnit barvu, je přímé nastavení:

\def\red{\pdfliteral{1 0 0 rg}}
\def\black{\pdfliteral{0 0 0 rg}}
\def\green{\pdfliteral{0 0.5 0 rg}}
Černý text, \red červený text, \green
zelený text, \black černý text.

Příkaz rg nastavuje barvu v prostoru RGB. Tři parametry se uvádí před ním, oddělené mezerou. Jsou to reálná čísla v rozsahu 0 až 1. První je červená, druhé je zelená a třetí modrá složka.

Dejte si pozor na to, že přímý zápis do PDF naprosto ignoruje nějaké uzavření do skupin, které vidí TeX, naopak je třeba uvažovat uzávorkování uvnitř PDF. Barva je nastavena obvykle do konce strany.

Chcete-li si uložit na zásobník stav grafiky v PDF, můžete použít příkazy q a Q:

% Ulož stav grafiky
\def\beginpdfgroup{\pdfliteral{q}}
% Vrať stav grafiky
\def\endpdfgroup{\pdfliteral{Q}}

Analogicky k příkazu rg funguje příkaz k se čtyřmi parametry, který pracuje v prostoru CMYK, a příkaz g s jedním parametrem, jenž nastavuje barvu ve stupních šedé. Vyrábíte-li tedy PDF pro tisk, použijte CMYK, pokud se má výstup zobrazovat na obrazovce, použijte RGB.

Celé je to ještě trochu ztížené tím, že uvedené PDF příkazy platí jen pro čáry. Některé objekty se vykreslují jako výplň. Pokud se ve výstupu objevují objekty, které nerespektují nastavení barev, přidejte k nastavení barvy ještě jednou totéž, ale velkými písmeny. Všimněte si zlomkových čar:

\def\red{\pdfliteral{0 1 1 0 k}}
\def\green{\pdfliteral{1 0 1 0 k}}
\def\black{\pdfliteral{0 g}}
\def\Red{\pdfliteral{0 1 1 0 K}}
\def\Green{\pdfliteral{1 0 1 0 K}}
\def\Black{\pdfliteral{0 G}}
\def\fr{{a+b\over c}\quad}
$\displaystyle\fr\red\fr\green\fr\black
\fr\Red\fr\Green\fr\Black\fr$

Formát PDF je daleko mocnější, co se týče barev, ale to už výrazně přesahuje možnosti našeho seriálu. Máte-li zájem o přímé barvy Pantone, ICC profily a další, zeptejte se na fóru.

Úkol 3 [3b]

Implementujte makra pro pohodlnější práci s barvami. Váš balík musí umět definovat barvu v systémech RGB, CMYK a stupních šedé a pohodlně pak definovanou barvu nastavit. Použití může vypadat například takto:

\defrgbcolor\red{1 0 0}
\defcmykcolor\green{1 0 1 0}
\defgrayscalecolor\halfgray{0.5}
\defgrayscalecolor\black{0}

Černý, \red červený, \green zelený,
\halfgray šedý, \black černý text.

Při řešení úkolů se vám možná budou hodit nějaké triky, které se objeví v řešení čtvrté série. Nezapomeňte tam nahlédnout.

A to je vše, přátelé. Doufám, že TeXu zůstanete věrni i nadále.

Jan „Moskyto“ Matějka

Řešení