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.

Řešení ú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

Čokolády

Zisk čokolády v této sérii byl podmíněn získáním plného počtu bodů za alespoň tři úlohy. To se podařilo 8 řešitelům. Speciální bychom chtěli vyzdvihnout Martina Raszyka, kterému se povedlo vyřešit dokonce 7 úloh na plný počet bodů, gratulujeme.

---

25-3-1 Kontrola docházky (Zadání)

---

S pomocí kuchařky nebyla tato úloha příliš obtížná a je škoda, že jsme nedostali o něco více řešení, neboť všechna byla štědře oceněna. Není těžké poznat, že škrtnutí jedné dvojice je jen drobná úprava klasického příkladu na Čínskou zbytkovou větu.

Naše řešení bude z obvyklého postupu na řešení takového příkladu taky vycházet. Zapomeňme tedy prozatím na škrtání jedné dvojice a stručně si připomeňme, co nám o Čínské zbytkové větě říká kuchařka o teorii čísel. Budeme předpokládat, že s čísly umíme aritmetické operace v konstantním čase a paměti. Protože kvůli stručnosti přeskakujeme některá zdůvodnění a mezikroky, doporučujeme mít při čtení tohoto vzorového řešení po ruce kuchařku.

Bez škrtání dvojice

Když se podle zadání policisté seřadí do řad po M₁ lidech, zbyde jich K₁, když se seřadí po M₂, zůstane jich K₂, a obdobně až do M_N, K_N.

Pro každé i mezi 1 a N vypočítáme „magické“ Q_i, pro které platí Q_i ≡ 1 (mod M_i) , a pro každé j různé od i naopak Q_i ≡ 0 (mod M_j) . Tyto „magické koeficienty“ později použijeme ke zjištění počtu policistů na stanici (bez škrtání dvojice):

Označíme nsn(M₁, … , M_i-1, M_i+1, … , M_N) jako S_i. Protože jsme zvolili M_i v našem zadání jako navzájem nesoudělná, je S_i rovné M₁  · …  · M_i-1  · M_i+1  · …  · M_N.

Algoritmus psaný podle definice ale není moc rychlý: každé S_i by počítal násobením N-1 jednotlivých M_j, na čemž by strávil čas O(N²). Rozumnější je předpočítat si pro každé i násobek A(i) = M₁  · …  · M_i a násobek B(i) = M_i  · …  · M_N. S_i pak dokážeme spočítat snadněji jako A(i - 1)  · B(i + 1). S lineárním časem a pamětí na předpočítání tedy najdeme všechna S_i v lineárním čase.

Lineární paměťová složitost zde příliš nevadí, protože samotné zadání je také lineárně velké. Šlo by si taky spočítat předem součin všech M_j, a S_i spočítat jako podíl tohoto součinu a M_i (dokonce v konstantní paměti).

Když dokážeme S_i (například popsanými způsoby) spočítat rychle, má algoritmus na řešení úloh na Čínskou zbytkovou větu časovou složitost O(N log N).

Se škrtáním dvojice

Jak modifikujeme tento algoritmus tak, aby uměl oprošťovat veřejné činitele od pracovních povinností? Jako první se nabízí zkrátka vyzkoušet všechny možnosti seškrtání, a pro každou z nich znova spočítat výsledek podle popsaného postupu. To by trvalo čas N  · O(N log N) = O(N² log N).

Pěknější řešení vychází ze znalosti čísel S_i. Nejdříve si pomocí ukázaného postupu spočítáme, kolik policistů by mělo být nastoupeno bez podvádění. Výsledek si označme V.

Platí, že když škrtneme (M_i, K_i), bude muset na stanici zůstat V mod S_i policistů. Vskutku: když od V odečteme S_i, snížíme o 1 jeho zbytek po dělení M_i, a ostatní zbytky zůstanou stejné. Nejmenší číslo, které dostaneme opakováním takového kroku, je právě V mod S_i.

Můžeme tedy předpočítat v O(N) všechna S_i, pak v čase O(N log N) spočítat nepodvádějící řešení V, a nakonec vyzkoušet, pro které i je V mod S_i nejmenší. Nalezené i můžeme s čistým svědomím prohlásit za správný výsledek. Protože nejnáročnější krok algoritmu bude řešení kongruencí s časovou složitostí O(N log N), poběží celý algoritmus v čase O(N log N).

Program (C)

Michal Pokorný

---

25-3-2 Zasedání u kulatého stolu (Zadání)

---

Nejdříve si všimneme, že existenci mnohoúhelníka u stolu s N místy stačí ověřovat jen pro všechny k-úhelníky, kde k ≥ 3 a dělí N. Podívejme se tedy, jak ověříme existenci k-úhelníka pro nějaké konkrétní k.

Mnohoúhelník určitě bude obsahovat jedno z prvních N/k míst. Navíc každé z těchto míst nám už jednoznačně určuje celý k-úhelník (ten bude tvořen vybraným vrcholem a každým (N/k)-tým dalším). Pokud ve všech vrcholech některého z těchto k-úhelníků budou jedničky, tak máme vyhráno.

Jeden k-úhelník ověříme v čase O(k), protože se díváme jen do k vrcholů a pro dané k jich ověřujeme N/k, dostaneme tedy O(k  · N/k) = O(N). Tento postup opakujeme pro všechny dělitele čísla N, které jsou rovny alespoň 3.

Kolik takových dělitelů může být? Určitě ne víc jak 2 √N, protože ke každému děliteli ≤ √N existuje jednoznačně určený dělitel ≥ √N a naopak. Tím tedy dostáváme celkovou složitost O(N√N).

To ale není nejlepší řešení, kterého jsme mohli dosáhnout. Pořád jsme zkoušeli zbytečně moc dělitelů. Ono totiž platí, že pokud k=a · b a a,b>1 a existuje k-úhelník, tak určitě existuje i a-úhelník a b-úhelník, protože ty vybírají jen některé vrcholy z celého k-úhelníka. A naopak, pokud neexistuje a-úhelník nebo b-úhelník, tak určitě nemůže existovat ani k-úhelník.

Stačí nám tedy testovat jen prvočíselné dělitele ≥ 3 a pak speciálně otestovat čtverec. Tak si jen N rozložíme na prvočísla, což klidně můžeme udělat jednoduše v O(N), a pak každé prvočíslo v tomto rozkladu otestujeme.

Program (C++)

Karel Tesař

---

25-3-3 Do třetice sekání (Zadání)

---

Přímočarý způsob, jak určit optimální políčko pro zadaný interval, je určit podle definice námahu pro každé políčko a ze spočítaných hodnot vybrat minimum. Zkoušíme tedy až N políček, pro každé z nich potřebujeme projít opět až N políček.

Přímočaré řešení tak má časovou složitost O(N) na určení námahy pro políčko, tedy O(N²) na interval a O(D · N²) celkem. V případech, kdy D je řádově stejně velké jako N, můžeme také psát celkovou složitost jako O(N³). Paměťovou složitost má O(N) (stačí nám pamatovat si jednotlivé hmotnosti trávy).

Lepší řešení

Pojďme se podívat, jestli to umíme lépe. Máme optimalizovat právě pro ty případy, kdy D je řádově stejně velké jako N. To nám celkem jasně napovídá, že si budeme chtít něco předpočítat.

To, co si předpočítáme, budou prefixy a „prefixy prefixů“, a to jak zleva, tak zprava. Za chvilku si ukážeme, že ty nám stačí na to, abychom námahu svozu na dané políčko určili v konstantním čase.

Prefixy prefixů označme jako Cl, resp. Cr. Platí Cl₀ = Cr_N = 0, Cl_i = Cl_i-1 + Pl_i, obdobně Cr_i = Cr_i+1 + Pr_i. Říkají nám, kolik námahy dá svozit na dané políčko všechnu trávu nalevo, resp. napravo od něj. (Rozmyslete si, že to tak skutečně je – chceme-li svozit trávu na políčko i zleva, stojí nás to stejně námahy, jako bychom ji sváželi na políčko i-1, a navíc musíme všechnu svezenou trávu posunout ještě o jedno políčko navíc.)

Prefixy dokážeme spočítat v lineárním čase. Při prvním průchodu spočítáme prefixy zleva, při druhém prefixy zprava. Časová složitost předzpracování tak bude O(N).

Ukažme teď, že tyto prefixy nám skutečně stačí, abychom námahu svozu trávy z intervalu na vybrané políčko určili v konstantním čase. Mějme a,b: 1 ≤ a ≤ b ≤ N a nějaké i: a ≤ i ≤ b.

Víme, kolik námahy nás stojí svoz trávy ze všech políček až do i-1 na políčko i. My od této námahy ale potřebujeme odečíst námahu na svoz trávy z políček 1 až a-1, protože z nich trávu ve skutečnosti svážet nebudeme. Tuto námahu můžeme rozdělit na námahu pro svoz na políčko a a pro následný přesun z a na i.

Už ale víme, kolik námahy stojí svoz na políčko a, je to hodnota Cl_a. Víme ale také to, kolik stojí následný přesun na i. Námaha odpovídá hmotnosti trávy nalevo od a vynásobené vzdáleností a od i, čili Pl_a  · (i - a).

Tím tedy umíme spočítat cenu za svoz trávy v intervalu nalevo od i, je to Cl_i - Cl_a - Pl_a  · (i - a). Podobně dokážeme spočítat cenu za svoz trávy v intervalu vpravo.

Tím jsme složitost snížili na O(N) pro každý interval, celkovou složitost pak na O(N + DN) = O(N²). Paměťová složitost zůstala O(N).

Optimální řešení

To ale pořád není optimální. Jak se změní námaha, když místo na i budeme trávu svážet na i+1? Zvýší se nám o Pl_i+1 (všechnu trávu vlevo od i+1 vezeme o políčko dál) a sníží o Pr_i. Jinak řečeno, námaha se mezi dvěma políčky vždy zvyšuje o rozdíl Pl_i+1 - Pr_i.

Protože máme zaručené kladné hmotnosti trávy, určitě platí, že tento rozdíl bude neklesající (ze začátku záporný a na konci kladný). To znamená, že cena se bude nějakou dobu snižovat (dokud budeme přičítat záporný rozdíl), a pak se zase začne zvyšovat.

Pro nás to má velice příjemný důsledek. Na hledání optimálního políčka tak totiž můžeme použít upravené binární vyhledávání. Místo abychom porovnávali hodnoty s nějakou předem určenou, podíváme se vždy na dvě sousední, a vydáme se tím směrem, kterým se hodnoty zmenšují.

Binárním vyhledáváním zvládneme optimální políčko pro daný interval najít v O(log N), celková složitost tak bude O(N + D log N) = O(N log N).

Pro zájemce ještě ukažme, že při tomto zadání není vůbec potřeba počítat prefixy prefixů ani prefixy zprava.

Všimněte si, že tento postup neříká nic o tom, kolik ta námaha je, pouze najde políčko, pro které je optimální. To ale při našem zadání stačilo.

Za pomoc s úlohou děkuju Martinovi Hořeňovskému.

Program (C) – medián

Program (C) – prefixy

Karolína „Karryanna“ Burešová

---

25-3-4 Zločinná záležitost (Zadání)

---

Výrobní fáze, závislosti mezi nimi… to musí být grafová úloha! A taky je. Fáze jsou jednoduše vrcholy a závislosti orientované hrany (vedoucí ve směru od fáze, která by měla proběhnout dříve).

Navíc je graf acyklický, neboť úloha má vždy řešení. Kdyby byl v grafu orientovaný cyklus, při výrobním procesu dojdeme do situace, kdy musíme zpracovat nějakou fázi z cyklu. Každá je však závislá na jiné fázi z cyklu, takže nelze žádnou z nich zpracovat. Neorientované cykly nám nevadí.

Lehčí varianta

Na vyřešení lehčí varianty úlohy stačilo dokonce jen přečíst si grafovou kuchařku a všimnout si, že topologické třídění (neboli uspořádání) přesně řeší náš problém. Nicméně, vymyslet tento algoritmus z hlavy jistě také není těžké ;-)

Než se pustíme do těžší varianty, topologické třídění si krátce popíšeme. Budeme ho dělat po směru hran, čili obráceně než v kuchařce (chceme, aby hrany vedly z vrcholu s menším číslem do vrcholu s větším číslem). Nejprve najdeme zdroje, tedy vrcholy, do nichž nevede hrana (mají nulový vstupní stupeň). To můžeme udělat třeba při načítání vstupu.

Všechny zdroje si naskládáme do nějaké datové struktury, v níž umíme v konstantním čase odebírat a přidávat prvky, například do fronty. Jak budeme postupně zpracovávat vrcholy, budeme do fronty ukládat všechny vrcholy, které mají po odebrání zpracovaných vrcholů vstupní stupeň 0 (už do nich nevede hrana).

Dále postupně odebíráme z fronty vrcholy, dokud se fronta nevyprázdní. Platí, že k-tý odebraný vrchol bude k-tým v pořadí výrobního procesu. Po odebrání vrcholu z fronty tento vrchol smažeme i z grafu včetně hran z něho vedoucích. Když se nějakému jeho sousedu snížil vstupní stupeň na 0, šoupneme ho také do fronty.

Není těžké nahlédnout, že v grafu bez orientovaných cyklů vždy existuje zdroj a že se fronta vyprázdní až po zpracování všech vrcholů. Na podrobnosti k implementaci algoritmu a zdůvodnění správnosti odkazujeme čtenáře do kuchařky.

Při reprezentaci grafu seznamem sousedů je časová složitost O(N+M), protože v tomto čase najdeme zdroje spočítáním vstupních stupňů a poté se na každou hranu podíváme jen jednou. Paměťová složitost je na tom asymptoticky stejně, kromě grafu máme jen frontu na vrcholy a pro každý vrchol si pamatujeme aktuální vstupní stupeň. Kdybychom však ukládali graf maticí sousednosti, časová i paměťová složitost naroste na O(N²).

Těžší varianta

Pro vyřešení těžší varianty stačilo upravit topologické třídění. Místo jedné fronty budeme mít dvě, každou pro jednu továrnu. Na začátku si vybereme jednu továrnu, a dokud to jde, odebíráme z její fronty. Když je prázdná, provedeme převoz do druhé továrny, odebíráme z její fronty, až se vyprázdní, přesuneme se zpět do první továrny…

V průběhu samozřejmě dáváme vrcholy se vstupním stupněm 0 do fronty té továrny, v níž se má dělat příslušná fáze. Skončíme, když dojdou vrcholy v obou frontách.

Zbývá vyřešit, jakou továrnou začít. Jelikož jsou jen dvě, prostě zkusíme začít nejprve s jednou a pak s druhou a vypíšeme výsledek s méně převozy.

Algoritmus jistě vytvoří topologické uspořádání, nicméně potřebujeme zdůvodnit, že to zvládne na nejmenší možný počet převozů. Prvně jde jednoduše nahlédnout, že když lze nějakou fázi zpracovat bez převozu, můžeme tak učinit hned a neuškodíme si tím. Navíc nezáleží na pořadí výběru fáze ke zpracování, když jich lze zpracovat více bez převozu.

Důležité je, že náš algoritmus vždy zpracuje co nejvíce fázi, než proběhne převoz. Nemůže tedy existovat nějaké jiné pořadí s méně převozy – jednak by si nepomohlo tím, že mezi dvěma převozy vynechá fázi, kterou zpracoval náš algoritmus. Druhak by nemohlo zpracovat mezi dvěma převozy ani nic navíc, protože ty fáze by jinak zpracoval ve stejnou dobu i náš algoritmus (musí mít někdy vstupní stupeň 0).

Korektnost algoritmu je zdůvodněna a časová ani paměťová složitost topologického třídění se úpravou pro dvě továrny nepokazí, pořád činí O(N+M).

Program (C)

Pavel Veselý

---

25-3-5 Histogram (Zadání)

---

Pro úlohu se nabízí vcelku triviální řešení, kdy vyzkoušíme všechny možné začátky a konce posloupností sloupečků a vybereme minimum z výšek v této posloupnosti. To nám určí obdélník. Ze všech takovýchto obdélníků nám stačí vzít ten s maximálním obsahem. Potíž tohoto řešení je jeho časová složitost, která je kvadratická. My si ukážeme řešení pracující v čase lineárním.

Mějme i-tý sloupeček s výškou h_i. Pokud chceme zjistit obsah největšího obdélníku, který obsahuje i-tý sloupeček celý, stačí nám zjistit, kolik sloupečků j s výškou h_j ≥ h_i se nachází bezprostředně před a po i-tém sloupečku.

Nejdřív spočítáme, kolik je sloupečků s menší nebo větší výškou bezprostředně před i-tým sloupečkem (značíme l_i). Analogický postup pak můžeme použít na sloupečky k i-tému přiléhající zprava (značíme r_i).

Pro nalezení l_i (resp. r_i) nám stačí vhodně použít zásobník. Pro každý sloupeček, počínaje prvním, provedeme následující postup. Pokud je zásobník prázdný, přidáme na něj index i a pokračujeme dále. Pokud zásobník prázdný není, budeme z vrcholu mazat indexy j tak dlouho, dokud bude platit h_j ≥ h_i nebo zásobník nebude prázdný. Rozdíl indexu sloupečku na vrcholu zásobníku a indexu i-tého sloupečku je teď evidentně námi hledané l_i. Nakonec na vrchol zásobníku vložíme index i-tého sloupečku.

Zbývá si uvědomit, že zásobník po i-té iteraci je ve stavu, který dá korektní řešení i pro následující sloupečky. To nahlédneme rozborem případů. V případě, že je (i+1)-tý sloupeček menší než byl i-tý, stačí smazat vrchol zásobníku a popřípadě další indexy. Snadno nahlédneme, že to, co bylo smazáno v i-tém kroku, mělo být smazáno.

Naopak, pokud je (i+1)-tý sloupeček ostře vyšší než předchozí, algoritmus ze zásobníku nic neodebere a l_i+1 = 0, což je správně. Pro další sloupečky pak korektnost plyne z matematické indukce podle indexů sloupečků.

Lineární časová složitost plyne z následujícího pozorování. Počet odebrání indexu ze zásobníku bude maximálně tolik, kolik indexů do zásobníku přidáme. A těch přidáme n, přičemž každý právě jednou. Paměti nám stačí taktéž lineárně. Řešení je zjevně optimální, protože vstup musíme minimálně jednou přečíst, tedy lepší než lineární časové složitosti dosáhnout nelze.

Program (C++)

Jan Bok

---

25-3-6 Rytíř a princezny (Zadání)

---

K řešení využijeme takzvaný hladový přístup. Více o tomto přístupu si můžete vyhledat pod heslem hladové algoritmy, resp. greedy algorithms.

Budeme postupovat společně s rytířem jeho trasou a pomyslně zabijeme každého draka, který nám vstoupí do cesty. Když přistoupíme k princezně krásy K (jiné než vytoužené poslední), může se přihodit, že jsme zabili více draků, než jsme mohli. V tom případě si chceme zabití některých draků rozmyslet.

Z našeho seznamu zabitých draků odebereme draky s pokladem nejnižší hodnoty tak, abychom kolem princezny mohli bezpečně projít. Zbude tedy K-1 draků s nejhodnotnějším pokladem. Když přistoupíme k poslední princezně, zkontrolujeme počet zabitých draků a zjistíme, zda jsme uspěli.

Nejdříve si rozmysleme, proč tento naivní přístup bude fungovat. V našem postupu dáváme šanci být zabit každému drakovi a mažeme jej až v situaci, kdy musíme počet draků snížit na K-1 draků a známe K-1 draků, kteří jsou alespoň stejně výnosní a lze je zabít. Tedy draka odebereme tehdy, když jistě víme, že jej odebrat musíme, a na konci nám pak zůstanou draci nejlepší.

Jak bude tento přístup efektivní? V našem řešení potřebujeme datovou strukturu s následujícími dvěma operacemi: vložení prvku a odebrání nejmenšího prvku. Pokud bychom použili obyčejné pole, stálo by vložení prvku konstantní čas a odebrání nejmenšího prvku čas lineární. Tak bychom dosáhli časové složitosti řešení O(N²), kde N je délka rytířovy cesty.

Vhodnější strukturou je binární halda, která obě operace zvládá v logaritmickém čase. Výsledná časová složitost s haldou je O(N log N), paměťová složitost je O(N). Pro seznámení s haldou nahlédněte do příslušné kuchařky o haldách.

Program (C++)

Lukáš Folwarczný

---

25-3-7 Zkratky (Zadání)

---

Díky omezení počtu a délky zkratek malými konstantami se ukázala tato úloha jako velmi jednoduchá. Nejpřímočařejším postupem bylo asi vydat se vstříc této úloze s pomocí dynamického programování.

Vyjdeme z toho, že prázdné slovo (slovo délky nula) určitě ze zkratek poskládat umíme. Pokud na toto prázdné slovo navazuje řetězec (posloupnost znaků) odpovídající některé ze zkratek, umíme poskládat i toto prodloužené slovo. Této počáteční části slova ze vstupu budeme říkat prefix. Takovým způsobem můžeme postupovat dál, dokud se nám nepovede poskládat celé slovo, nebo dokud nezjistíme, že už nemáme žádnou možnost jak pokračovat.

Jak to konkrétně provedeme? Půjdeme na to z druhé strany a budeme postupně pro každý znak slova ze vstupu určovat, jestli v něm končí nějaký poskládatelný prefix. Vezmeme si všechny zkratky a zkusíme je umístit tak, aby končily v právě zpracovávaném znaku.

Pokud se budeme nacházet na K-tém znaku vstupního slova a budeme zkoumat, jestli umíme poskládat tento prefix tak, aby zde končila nějaká zkratka délky S, tak se podíváme, jestli podslovo končící na pozici K-S umíme složit. Pokud ne, nemá smysl tuto variantu dál řešit.

Pokud ale ano, je zde možnost, že za prefix končící na pozici K-S můžeme přidat tuto zkratku a vytvořit tak nový (delší) prefix končící na pozici K. Zkontrolujeme tedy znak po znaku, jestli nám tam tato zkratka sedí. Pokud ano, poznamenáme si to k indexu K a pokračujeme dál. Celé slovo pak lze poskládat právě tehdy, pokud lze poskládat prefix končící posledním písmenem slova.

Správnost jednoduše zdůvodníme následujícím pozorováním. Budeme předpokládat, že pro všechny pozice vlevo od aktuálně zpracovávaného už máme jednoznačně určeno, jestli je umíme poskládat. Každý poskládatelný prefix končící na pozici K můžeme rozložit na dvě části: na nějaký kratší prefix a na některou ze zkratek navazující na tento kratší prefix. Náš postup ale právě takový rozklad najde a tak tuto pozici označí za poskládatelnou.

Naopak, pokud takový rozklad pro tuto pozici neexistuje (a tento prefix tedy poskládat nelze), tak je triviálně vidět, že ani náš algoritmus tuto pozici neoznačí za poskládatelnou. Tím jsme jistě tuto vlastnost dokázali pro další pozici a indukcí dokážeme správnost algoritmu pro celý vstup.

Pro výpočet časové složitosti si označme Z jako součet délek všech zkratek. Pak musíme udělat celkem N kroků algoritmu a v každém projdeme až všechny zkratky, tedy O(NZ). Pokud si dovolíme považovat Z za konstantu, je pak složitost lineární vzhledem k délce vstupu, tedy O(N).

Pokud si uvědomíme, že nám stačí si pamatovat jen tu část vstupu, se kterou aktuálně pracujeme (nemusíme sahat více do minulosti, než je délka nejdelší zkratky), tak nám stačí pouze O(Z), respektive O(1) paměti, pokud opět Z prohlásíme za konstantu.

Program (C)

Jiří Setnička

---

25-3-8 Tabulatika (Zadání)

---

Řešení třetího dílu jste se zhostili velmi úspěšně. Nutno ovšem poznamenat, že během sbírání technických zkušeností s TeXem byste měli také sbírat estetické a typografické zkušenosti. Pořád je co dohánět, rád vidím esteticky dotažená řešení některých z vás, vzápětí však skřípu chrupem nad jiným řešením, kde se jiný řešitel ani nesnažil, aby to nějak vypadalo.

Úkol 1

Řešení prvního úkolu bylo jednoduché:

\settabs\+Uherské Hradiště &Jablonec nad Nisou
	 &30. 12. &Kolik km&\cr
\+\it Odkud&\it Kam&\it Kdy&\it Kolik km\cr
\+Praha&Olomouc&21. 12.&\hfill 250&\cr
\+Olomouc&Uherské Hradiště&30. 12.&
  \hfill 130&\cr
\+Uherské Hradiště&Vyšší Brod&5. 1.&
  \hfill 350&\cr
\+Vyšší Brod&Jablonec nad Nisou&17. 1.&
  \hfill 324&\cr

Použili jste znalosti ze seriálu, verze \settabs se vzorovým řádkem. Někteří z vás použili \settabs 4\columns, což jsem hodnotil jedním záporným bodem, neboť taková verze měla třetí a čtvrtý sloupec šeredně roztahaný.

Všimněte si, že vzorový řádek končí &\cr, neboli na konci řádku vzniká fiktivní pátý sloupec, aby bylo k čemu zarovnat obsah čtvrtého sloupce.

Úkol 2

Tento úkol tvořil téměř půlku všech dosažitelných bodů. Uvedu zde jedno z možných řešení, různých přístupů bylo mnoho. Ukážeme si řešení s fixním počtem úloh.

Nejprve si trochu zvětšíme stránku, ať se vejdeme:

\hoffset-15mm
\advance\hsize by 3cm
\voffset-15mm
\advance\vsize by 3cm

Pak se naučíme zlý trik s \lowercase:

\lccode`\~`\,\relax
\lowercase{%
\def\normalcomma{\def~{,}}
\def\mathcomma{\def~{{,}}}
}
\lccode`\~`\-\relax
\lowercase{%
\def\normaldash{\def~{-}}
\def\omitdash{\def~{}}
}
\normalcomma
\normaldash
\def\pointcell{\mathcomma\omitdash}

Primitivum \lowercase (a jeho bratříček \uppercase) překládají tokeny podle tabulek \lccode a \uccode. Primitivum funguje tak, že ztokenizuje svůj „parametr“ a ve všech tokenech, kromě řídících sekvencí, změní kódy znaků podle příslušné tabulky. V základním nastavení se mění jen velká písmena na malá, resp. obráceně.

Přenastavení nějaké hodnoty se ale zhusta využívá právě uvedeným stylem. Tedy vlnka, která je stadnardně aktivním znakem (token (~, 13)), se uvnitř prvního \lowercase stane aktivní čárkou (token (,, 13)) a uvnitř druhého \lowercase aktivní pomlčkou. Jde to i jinak, ale tohle je asi nejčistší.

Uvnitř tabulky se skóre si totiž nastavíme pomlčku i čárku jako aktivní a na různých místech si přejeme, aby se chovaly různě. Konkrétně jde o buňky s počtem bodů, kde chceme, aby se místo pomlčky vysázelo prázdné místo a aby byly na obě strany okolo čárky stejné mezery.

\def\scoretable{\begingroup
\catcode`\, 13 \catcode`\- 13\relax
\doscoretable}

Další trik. Makro \scoretable je ve skutečnosti bez parametrů. Nejdřív si přenastavíme kategorie znaků a pak si teprve načteme parametry makra.

Následuje definice hlavičky tabulky:

\def\doscoretable#1{%
\line{\hfil\vbox{\halign{\strut%
##\hfil\quad&%
##\hfil\quad&%
##\hfil\enskip&%
\hfil##\hfil\enskip&%
\hfil##\hfil\enskip\vrule&%
\enskip%
\hfil\pointcell##\hfil\enskip&%
\hfil\pointcell##\hfil\enskip&%
\hfil\pointcell##\hfil\enskip&%
\hfil\pointcell##\hfil\enskip&%
\hfil\pointcell##\hfil\enskip&%
\hfil\pointcell##\hfil\enskip&%
\hfil\pointcell##\hfil\enskip\vrule&%
\enskip\hfil\pointcell##\quad&%
\hfil\pointcell##\cr
&\it řešitel&\it škola&\it ročník&\it sérií%
&\it 2521&\it 2522&\it 2523&\it 2524%
&\it 2525&\it 2526&\it 2527&%
\it série&\it celkem\cr
#1
}}\hfil}\endgroup}

Všimněte si zdvojených #. Jsme uvnitř definice makra, tedy je potřeba tento znak zdvojit, aby nebyl interpretován.

Pokud vám chybí \begingroup (protože na konci je samotné volání \endgroup), podívejte se o kousek výš do definice \scoretable.

Ještě by to chtělo definici jednotlivých řádků:

\def\scoreline#1. #2 (#3; #4; #5): #6: #7 #8 {%
\def\m.{}%
#1.&#2&#3&$#4$&$#5$&\scorepoints#6!&$#7$&$#8$\cr
}
\def\scorepoints#1 #2 #3 #4 #5 #6 #7!{%
$#1$&$#2$&$#3$&$#4$&$#5$&$#6$&$#7$%
}

Zde je důležitý trik s dvoufázovým zpracováním parametrů makra. TeX umí zpracovat jen devět parametrů současně, proto jsme seznam bodů za jednotlivé úlohy nejprve prohlásili za jeden argument, který jsme pak nechali zpracovat makrem \scorepoints.

Makro \m slouží k polknutí tečky za pořadím účastníka v případě, že chceme prázdný první sloupec.

A teď už vzorové použití:

\scoretable{
\scoreline \m. {} (; ; ):
           13 11 6 13 8 9 13: 59,0 118,0
\scoreline 1. Rastislav Rabatin (GJHBA; 4; 5):
           13 7,5 - 13 8 9 8,5: 54,8 109,5
\scoreline 2. Ondřej Hlavatý (GJirsíkaČB; 4; 2):
           4 5 - 13 8 4 13: 49,6 102,5
\scoreline 3. Michal Punčochář (GJíroČB; 3; 7):
           6,5 11 - 13 8 - 13: 53,2 98,9
\scoreline 11. Jakub Maroušek (G\_Písek; 3; 2):
           5,5 4 - 4 - 0 10,7: 36,1 73,5
\scoreline 12.--13. Mikuláš Hrdlička (MG; 2; 2):
           4 - 3,5 6 2,5 - -: 26,8 72,9
\scoreline \m. Matej Lieskovský (GOmPha; 3; 7):
           2,5 - 4 - 3 7 9: 30,7 72,9
\scoreline 14. Jakub Svoboda (GKomHavíř; 3; 2):
           - 7 4 4 1,5 2 -: 29,6 71,2
\scoreline 54. Přemysl Šťastný (GZamb; -1; 1):
           - - - - - - -: 0,0 4,7
}

Pokud se vám nepovedlo správně vysázet čárky nebo vyházet pomlčky, nestrhával jsem za to žádné body. Někteří z vás nedodali makro, ale jenom sazbu, což jsem honoroval zhruba půlkou bodů.

Vytvořit verzi, která zvládne proměnlivý počet úloh, by také šlo, dokonce i bez číselných proměnných a bez podmínek, které vysvětlujeme ve čtvrtém dílu, ale bylo by to příliš ošklivé. Úplně stačila verze pro fixní počet úloh.

Úkol 3

Řešení posledního úkolu bylo přímočaré až na jednu drobnost. Spousta z vás přišla o půlbod kvůli nule ve třetím řádku, kterou jste měli příliš nacpanou na zlomek nad ní. To šlo jednoduše opravit přidáním \strut.

$$Z = \left\{\matrix{N > 0:&
  \displaystyle\sum_{i=1}^N
    \left(2\sum_{i<j}
      \log\left|\lambda_i-\lambda_j\right|
      - \sum_{i=1}^N V(\lambda_i)\right)\cr
  N < 0:& \displaystyle-{1\over N^2}\cr
  N = 0:& \strut0\cr
}\right.$$
%% Pravá } tu již není, proto \right jen tak.

Většina z vás si všimla primitiva \displaystyle, díky kterému se daly vysázet hezké velké sumy a zlomky. Někteří použili \limits, čímž přehodili indexy u sum nad znaménka, ale stejný trik se nedal použít na zlomek ve druhém řádku, který tak zůstal malinký.

Úkol 4

Centrovaná sazba v posledním úkolu vám dala kupodivu docela zabrat. Nicméně mnoho z vás se dobralo k nějakému správnému řešení, třeba k tomuto:

%% Odsadit první řádek by bylo divné.
\parindent 0pt
%% Poslední řádek nebude nijak doplněn.
\parfillskip 0pt
%% Zleva a zprava stejné místo, natahovací.
\leftskip 0pt plus \hsize
\rightskip 0pt plus \hsize

Jan „Moskyto“ Matějka

Menu