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

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

---

• Termín série: 22. října 2012 8:00
• Termín CodExové úlohy: 23. října 2012 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-1-1: Fotografování
• 25-1-2: Stánky na náměstí
• 25-1-3: Řazení hradní stráže
• 25-1-4: Útěk
• 25-1-5: Algoritmus sekretářky
• 25-1-6: Sekání trávy
• 25-1-7: GPS log
• 25-1-8: Sázíme v TeXu

---

25-1-1 Fotografování (12 bodů)

---

Máme N japonských turistů, kteří se mezi sebou navzájem fotí. Typicky, když jeden Japonec vyfotí druhého, ten druhý mu to musí ze slušnosti oplatit.

Japonci mají v oblibě jednu hru: v určitou chvíli někdo oznámí přirozené číslo K, načež si všichni spočítají, kolik ostatních mají nafoceno (což je zjevně počet lidí, kteří fotili je samotné). Každý, kdo má nafoceno méně než K kamarádů, vypadává ze hry.

V druhém kole se počítají pouze ti, kteří nevypadli. Opět ti, kteří mají nafoceno méně než K nevypadnuvších, vypadnou ze hry.

Takto hra pokračuje, dokud se stav mezi dvěma koly mění. Všichni zbylí hru vyhrají.

Víte, které dvojice Japonců se navzájem vyfotily. Určete pro každého z nich, pro jaké maximální K hru vyhraje.

7 bodů dostanete, pokud najdete vyhrávající skupinku pro K=3.

Příklad: Uvažujme situaci pro N=7, přičemž se vyfotily dvojice: 1–2, 2–4, 4–5, 3–1, 3–6, 6–1, 6–2, 6–7, 7–1, 7–2 a 7–4. Pro K>3 nevyhraje nikdo. Pro K=3 vyhrají hráči 1,2,6,7, pro K=2 vyhrají všichni až na hráče 5 a pro K<2 vyhrají všichni.

Řešení

---

25-1-2 Stánky na náměstí (12 bodů)

---

Máme T trhovců. Každý trhovec má vlastní stánek. Při jeho stavbě zkušeným okem určil oblast, odkud na něj turisté nejlépe uvidí, tato oblast má tvar konvexního mnohoúhelníka.

Problém nastává, pokud se dvě takovéto oblasti protínají – potom se trhovci neustále hádají a přetahují si navzájem turisty.

Radní o tomto problému ví a snaží se mu zabránit. Oblasti vám zadají jako T seznamů bodů, kde body jsou vždy zadané podél obvodu. Každý seznam bodů tvoří konvexní mnohoúhelník. Chtěli by vědět, jestli se nějaké dvě oblasti překrývají.

Příklad: Pro T=2 a oblasti určené {[1,1], [2,1], [2,2], [1,2]} a {[2,2], [4,2], [2,3]} se tyto dvě neprotínají (vlevo), ale pro T=3 a oblasti zadané pomocí bodů {[1,1], [2,1], [2,2]}, {[3,1], [4,1], [4,2]} a {[1,3], [2,1], [3,3]} se první a třetí oblast protínají (vpravo).

Řešení

---

25-1-3 Řazení hradní stráže (7 bodů)

---

Při výměně dvou gard stráže ta odchozí nastoupí na nádvoří do řady. Příchozí stráž nastoupí vedle ní.

Obě gardy jsou přirozeně stejně velké – každá má právě N vojáků. Vojáci mají dopředu určeno, na kterém místě hlídají, každý z gardy hlídá na jiném místě.

Pro kontrolu, že jsou všichni a že žádné z míst nezůstane nehlídáno, se příchozí garda musí seřadit stejně jako ta odchozí.

Řazení podle protokolu probíhá tak, že se vždy odpojí poslední v řadě příchozí gardy a zařadí se na libovolné místo. Kolik takovýchto přesunů je nejméně potřeba, aby příchozí garda byla seřazena stejně jako odchozí?

Příklad: Když si vojáky očíslujeme 1… N dle místa, kde budou hlídat, tak pro odchozí řadu 4, 2, 1, 3, 5 a příchozí řadu 1, 3, 5, 2, 4 jsou potřeba dva přesuny.

Řešení

---

25-1-4 Útěk (12 bodů)

---

Úzké uličky tvoří bludiště. V tomto bludišti jsou osoby, které nesmíte potkat. Tyto osoby neběhají chaoticky, mají jistý okruh, po kterém chodí stále dokola.

Bludiště je zadáno jako čtvercová síť o rozměrech W×H, kde 1≤ W, H ≤ 70. V bludišti jsou čtyři typy polí: zeď #, volno ., start S a cíl C. Start je v bludišti právě jeden.

V bludišti je N osob, kterým utíkáte, přičemž 0≤ N ≤ 2. Pohyb každé z osob je dán seznamem souřadnic délky D, jehož konec navazuje na začátek. Osoba se po nich cyklicky pohybuje. Seznam je dlouhý 1 ≤ D ≤ 50 a je vždy platný (osoby neprocházejí zdmi, místa na sebe navazují). Je-li N=2, pak mohou obě osoby stát na stejném místě.

Pohyb v bludišti probíhá po tazích, v tahu se vždy můžete posunout o jedno políčko vodorovně nebo svisle, nebo stát na místě. Nejprve se pohnete vy, poté chytající osoby.

Najděte nejrychlejší cestu ven z bludiště, aniž byste potkali libovolnou z osob.

6 bodů získáte za řešení fungující pro N=0, 3 body pro N=1 a 3 body pro N=2.

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-1-5 Algoritmus sekretářky (7 bodů)

---

Představte si, že sekretářka je naprogramovaná a provádí následující kód:

for i in range (0, N):
  for j in range (0, M):
    if (a[i]==c[j]):
      print b[i]+" "+d[j]+"\n";

Zkuste si rozmyslet, co kód (sekretářka) dělá a s jakou časovou složitostí. Potom zkuste vymyslet vlastní program, který dělá totéž efektivněji, nebo dokažte, že (asymptoticky) to už efektivněji nejde.

Řešení

---

25-1-6 Sekání trávy (10 bodů)

---

Představte si trávník N×M, který chceme posekat. Máme sekačku, kterou se můžeme pohybovat pouze vodorovně nebo svisle.

Začínáme v levém horním rohu a chceme každé políčko projet právě jednou (start je výjimka) a vrátit se na začátek. Na trávníku rostou květiny, které nechceme posekat.

Pro jaké N, M a umístění květin umíme trávník posekat? Pro zjednodušení předpokládejte, že na trávníku rostou květiny jen na jednom políčku.

4 body dostanete, pokud vyřešíte sekání trávníku bez květin.

Řešení

---

25-1-7 GPS log (7 bodů)

---

Máte zadanou posloupnost nadmořských výšek tak, jak je turisté postupně procházeli. Zvládnete z nich vyškrtat co nejméně výšek tak, aby zbylá posloupnost obsahovala maximum, výšky před maximem pouze stoupaly a ty za ním klesaly?

Příklad: Pro posloupnost výšek 1, 3, 2, 2, 3, 4, 6, 7, 7, 5, 6 je jedním ze správných řešení posloupnost 1, 2, 3, 4, 6, 7, 5 (poslední prvek lze nahradit šestkou).

Řešení

---

25-1-8 Sázíme v TeXu (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.

Bylo nebylo, 30. března 1977 obdržel Donald Ervin Knuth testovací výtisk jedné ze svých knih (druhé edice druhého dílu série The Art of Computer Programming). Prohlásil: „Strávil jsem 15 let psaním knih, ale pokud budou vypadat takhle nechutně, tak už žádnou nenapíšu.“ Pak stáhnul knihu z tisku a napsal TeX – sázecí systém a programovací jazyk.

První a zároveň poslední stabilní verzi TeXu vydal v roce 1989. Od té doby se již celý systém prakticky nezměnil. Název se čte „tech“ nebo „tek“, neboť ono X je ve skutečnosti velké řecké písmeno chí. Pokud byste náhodou nezvládli napsat název TeX se sníženým E, tak můžete napsat TeX. Nikdy ne však TEX.

Pojďme si tedy představit program a jazyk, díky kterým letáky KSP skvěle vypadají a dobře se čtou. Naučíme se používat TeX od úplných základů, začneme obyčejnými texty, probereme se matematickými vzorci a nakonec si ukážeme i zběsilé triky. Stanete se TeXniky, jaxepatří.

Instalace

Jak začít? Máte-li Linux, je to jednoduché. Nainstalujte si „TeXovou distribuci“ TeXlive (stačí minimalistická verze) plus československá rozšíření. V Debianu a Ubuntu se jedná o balíky texlive-base a texlive-lang-czechslovak.

Ve Windows je to o něco složitější. Stáhněte si instalační balík z CTANu a rozbalte jej. Máte-li dost místa na disku, můžete spustit install-tl.bat, odklikáte Next a nainstaluje se prakticky všechno, co byste kdy mohli i nemohli potřebovat. Zabere to přes 3 GB.

Pokud nechcete ucpat tolik místa na disku, případně nechcete stahovat tolik dat (to, co teď máte, je jen instalátor), spusťte install-tl-advanced.bat a v otevřeném okně si naklikejte menší instalaci. Pokud nevíte, případně se vám nad tím nechce přemýšlet, použijte tento návod:

1. Jako „Selected scheme“ vyberte „basic scheme“.
2. Z „Language collections“ vyberte československý balík.
3. TEXDIR upravte, pokud chcete změnit místo, kam bude TeX nainstalován.
4. Ujistěte se, že „Default page size“ je A4.
5. „Install TeXworks front end“ přepněte na Yes (poslední bod).
6. Klikněte na „Install TeX Live“. Instalátor stáhne z internetu všechno, co je potřeba, a nainstaluje. Celkem zabere okolo 250 MB.

Ahoj, světe!

Vyzkoušíme si, jak se TeX spouští. Použijeme k tomu testovací vstup:

Ahoj světe
\bye

Na Linuxu si prostě otevřete nějaký textový editor (autor má rád Vim, ale klidně použijte třeba GEdit), vyrobíte soubor ahoj.tex, otevřete si terminál, dokráčíte do příslušné složky příkazem cd a spustíte pdfcsplain ahoj.tex, což vyrobí soubor ahoj.pdf, který si prohlédnete.

Pod Windows bych doporučil použít TeXworks, které jste si před chvílí nainstalovali. Nejdříve trocha nastavování:

1. V menu Edit vyberte Preferences.
2. Na kartě Editor vyberte Encoding: ISO-8859-2.
3. Na kartě Typesetting v rámečku Processing tools klikněte na tlačítko +.
4. Vyplňte pdfCSplain jako Name a pdfcsplain.exe jako Program.
5. Do pole Arguments přidejte $synctexoption a $fullname.
6. Klikněte na OK, nastavte pdfCSplain jako Default a zavřete Preferences klikem na OK.
7. Zavřete TeXworks a otevřete je znovu.

Nyní můžete vepsat testovací vstup. Stiskem zeleného tlačítka se šipkou vlevo nahoře jej přeložíte a zobrazíte.

Poznámky:

• TeXworks existují i pro Linux, ale já mám radši Vim. Ovšem vyberte si dle chuti sami. De gustibus non est disputandum.
• TeX se dá spustit z příkazové řádky pod Windows, ale TeXworks jsou asi o něco příjemnější.
• S případnými problémy s instalací můžeme pomoct, pokud se nám svěříte na fóru.
• Znak \ najdete na české klávesnici na klávese Q při stisknutém pravém Altu.

Sázíme texty do odstavců

Napíšete-li do vstupního souboru libovolný text, TeX jej vysází. Vyzkoušejte si to dle libosti. Chcete-li přejít na nový odstavec, vynechejte prázdný řádek. TeX považuje libovolné nenulové množství mezer a tabulátorů za jednu mezeru.

Taktéž se polykají konce řádků, nejedná-li se tedy o dva konce řádků za sebou (ty značí konec odstavce). TeX také spolyká veškeré mezery a tabulátory na začátku a na konci odstavce.

Některé znaky není možné zadat přímo do vstupního textu, neboť je TeX interpretuje jako speciální. Jsou to znaky #$\%&^_{}~. Pokud chcete napsat #, %, $, &, a _, stačí předřadit zpětné lomítko: \#, \%, \$, \&, a \_. Stříška je považována za diakritické znaménko, takže je potřeba ji nakreslit samostatně: \^\relax (\relax je prázdný příkaz) se vykreslí jako ^.

TeX používá znak \ pro tzv. řídící sekvence. Ty můžou být jednoznakové jako v minulém odstavci, nebo víceznakové složené z písmen. Za písmennými se polykají mezery; kdybyste za nimi potřebovali mezeru vynutit, použijte \␣.

Ostatní (\, {, } a ~) jsou znaky, které se používají prakticky výhradně v matematickém zápise, ten nás čeká za chvíli.

Česká písmena s háčky a čárkami, stejně jako slovenská ľ, ŕ, ĺ, ä, ô apod. je možno napsat přímo do textu. TeX ale umí i ne-úplně-běžná písmena, třeba můžete napsat x̌iltovka nebo gűrű. Existují totiž příkazy, které přidají vhodné diakritické znaménko nad/pod následující písmeno.

Vstup	Výstup
\`o	ò	čárka dozadu
\'o	ó	čárka dopředu
\^o	ô	stříška
\"o	ö	přehláska
\~o	õ	vlnka
\=o	ō	čára nad
\.o	ȯ	tečka nad
\u o	ŏ	půlkolečko nad
\v o	ǒ	háček nad
\c o	o̧	cedilla
\d o	ọ	tečka pod
\b o	o̱	čára pod
\accent23 o	o̊	kroužek nad
\H o	ő	dlouhá přehláska (v maďarštině)
\t oo	o͡o	oblouček spojující 2 písmena

TeX automaticky dělí slova, která se nevejdou na konec řádku. Používá k tomu slovník, který je specifický pro každý jazyk. Základní je angličtina; pokud chcete nastavit češtinu nebo slovenčinu, použijte \language\czech, resp. \language\slovak.

Úkol 1 [2b]

Vysázejte tento text:

Poznatky získané cílevědomě v preadolescentním věku jsou adekvátní poznatkům pořízeným náhodně ve věku seniorském. (Co se v mládí naučíš, ve stáří jako když najdeš.)

Pokud se TeXu nepovedlo vysázet text tak, aby se vešel na řádek, objeví se za ním černý obdélník (slimák). Pak je potřeba řádek zlomit ručně, buď poradit TeXu, kde může lámat slovo, značkou \- (slo\-víč\-ko), nebo třeba přeformulovat text.

Chcete-li vysázet něco tučně nebo kurzívou, použijete \bf nebo \it ve skupině. Skupina je kus vstupu uzavřený mezi složené závorky { a }. Všechno, co se nastaví ve skupině, platí jen v ní, a po ukončení skupiny zase platí původní nastavení.

Takto tedy sázíme tučně a kurzívou:

Takto tedy sázíme {\bf tučně} a {\it kurzívou}:

Úkol 2 [2b]

Vymyslete (vyzkoušejte), co dělá \rm, a dodejte ukázkový kód.

Za zmínku stojí ještě několik českých typografických pravidel. V češtině nesmí zůstat na konci řádku jednopísmenná předložka. Pokud by ji tam TeX nechal, je potřeba mu naznačit, že následující mezera je nedělitelná. K tomu slouží vlnka: K~tomu, u~lesa.

Když píšete české „uvozovky“, použijte řídící sekvenci \uv: \uv{uvozovky}. Pozor, není možné přesahovat uvozovkami přes hranici odstavce. V takovém případě je ale obvykle lepší vyznačit dlouhou přímou řeč třeba jiným řezem písma nebo třeba zúžením okrajů.

Také stojí za zmínku pomlčky a podobné znaky. Spojujeme-li dvě slova, například „česko-slovenský“ nebo „byl-li“, napíšeme to TeXu jako jednu pomlčku.

Pokud používáme pomlčku jako interpunkční znaménko – třeba zde, zapíšeme ji jako dvě pomlčky vedle sebe a oddělíme ji na obou stranách mezerou. Totéž platí pro rozsah, například „pondělí – středa“: pondělí -- středa.

Pro úplnost ještě zmíníme dlouhou pomlčku ---, která se používá zřídka – obvykle na vyznačení náhle ukončené přímé řeči.

„Prosím pozor —“    Nádražní rozhlas zmlknul, světlo zhaslo, notebook se přepnul na baterii. Vypadla elektřina.

Matematický mód

Velké přednosti TeXu jsou v sazbě matematiky. Vyzkoušejme si základní věci. Matematika se v TeXu obaluje mezi dolary ($), neboť v dřevních dobách typografie byla její sazba velmi drahá.

Ty doby byly ve skutečnosti nejen dřevní/dřevěné, ale i olověné. Kdysi se totiž sázelo ručně, uchycovala se olověná písmenka do dřevěných rámů. Vysázet tehdy kvalitně matematiku uměl málokdo a obvykle si za to nechal mastně zaplatit. Kvalita ovšem odpovídala ceně. Tehdejšímu umění ručních sazečů se dnešní počítačová sazba ani zdaleka nevyrovná, natož pak třeba Word nebo LibreOffice.

Jednoduchou matematiku stačí psát. Mezery se v matematickém módu ignorují zcela, TeX je počítá podle poměrně složitého algoritmu a v drtivé většině případů vypadají vysázené vzorce hezky.

$a+b$	a+b
$a+b^2$	a+b2
$a(b + c)$	a(b + c)
$abc + def$	abc + def
$a_1+a_2$	a1+a2
$a+b^{2c}$	a+b2c
$a+b^2c$	a+b2c

Povšimněte si rozdílu mezi posledními dvěma řádky. Je zde využita skupina, která slouží k označení, co všechno má být horním indexem. Stejně se chová dolní index.

Horní a dolní index se vejde pod sebe, jsou-li uvedeny oba. Na našem webu bohužel zatím ne, ale pracuje se na tom.

Zde se objevila sekvence \dots, která vykreslí trojtečku se správnými rozestupy teček. Je možno ji používat i mimo matematický mód … Prohlédněte si rozdíl oproti třem samostatným tečkám ...

TeX umí v matematickém módu mnoho různých značek a symbolů. V prvé řadě umí řeckou abecedu, některá písmena dokonce ve více variantách. Vyzkoušejte:

\alpha, \beta, \gamma, \delta, \epsilon/\varepsilon,
\zeta, \eta, \theta/\vartheta, \iota, \kappa,
\lambda, \mu, \nu, \xi, o, \pi/\varpi,
\rho/\varrho, \sigma/\varsigma, \tau, \upsilon,
\phi/\varphi, \chi, \psi, \omega.

Další zajímavé značky jsou například různé relace nebo operace: =, >, <, ≠ (\ne), ≤ (\le), ≥ (\ge), ~ (\sim), ∈ (\in), ⊆ (\subseteq), × (\times), \ (\setminus), ∩ (\cap),∪ (\cup), ∨ (\vee, \lor), ∧ (\wedge, \land), …

Závorky se píšou svými standardními znaky s výjimkou složených závorek, zapisovaných \{ a \}. Se závorkami jde dělat spousta zajímavých věcí, ale to necháme na nějakou příští sérii, pokud bude místo.

Taktéž některé zajímavé funkce mají své řídící sekvence, například sin, cos, log , min nebo max: \sin, \cos,… Porovnejte: sinx ≠ sin x ($\sin x \ne sin x$).

Poslední, co se dnes naučíme, budou zlomky. Práce se zlomky je jednoduchá, slouží k tomu sekvence \over, kterou zapíšeme mezi čitatele a jmenovatele. Všechno, co je vlevo, je čitatel; napravo je jmenovatel.

Pokud potřebujete vysázet vzorec na samostatnou řádku, obalte jej mezi dvojité dolary: $$a + b + c$$ se vysází takto:

V tomto módu se některé konstrukce sází jinak, protože mají víc místa. Vyzkoušejte si například odmocniny, zlomky nebo ∑ (\sum) a ∏ (\prod).

Poznámky:

• V matematickém módu píšeme i samostatně stojící proměnné apod. Například „proměnná x je nezávislá na funkci f při libovolné volbě parametrů a, b, c“.
• Vlnovky využijeme i zde: proměnná~$x$ nebo funkce~$f$, případně $y$~je. Jednopísmenné vzorce, čísla apod., to všechno by mělo být přivlnovkované k nejtěsněji souvisejícímu slovu.
• Obsáhlý seznam všech značek naleznete v TeXbooku (Donald Ervin Knuth: The TeXbook (Reading, Massachusetts: Addison-Wesley, 1984), ISBN 978-0-201-13448-9) na stranách 434 až 439.
• Název programu (TeX) se vysází jako \TeX.

Úkol 3 [5b]

Vymyslete, jak vysázet tento vzorec, a dodejte zdrojový kód:

Pokud se vám nebude dařit jej zkonstruovat celý, vymyslete aspoň část, budou za to také nějaké body.

Úkol 4 [4b]

Vysázejte TeXem řešení jiné úlohy v této sérii a dodejte zdrojový kód. Měli byste znát dost na to, aby z TeXu vypadnul rozumně hezký výstup. Pokud si nebudete vědět s něčím rady, zeptejte se na fóru a orgové vám rádi poradí.

Řešení

Menu