Třetí série jedenáctého ročníku KSP

Řešení úloh

• 11-3-1: Telefouňové
• 11-3-2: Ffffaktoriál
• 11-3-3: Obdélníčky
• 11-3-4: Machina Universalis
• 11-3-5: Pascal či Céčko?

11-3-1 Telefouňové (Zadání)

Téměř všichni jste při sestavování algoritmu zapomněli na věc naprosto základní – důkaz správnosti vašeho algoritmu. Když je v zadání příklad výstupu, zachovejte stejný formát výstupu. Většina z vás nepsala na výstup názvy měst.

Chtělo se po vás, abyste vypsali libovolný graf se zadaným skóre, což je problém z teorie grafů. Pro podrobnější prostudování doporučujeme např. Úvod do teorie grafů od Jiřího Sedláčka, vydavatelství Academia. Pro neznalé začneme definicemi: (Neorientovaným) grafef G(V, H) nazveme uspořádanou dvojici množiny vrcholů V a množiny hran H. Hrana je (neuspořádaná) dvojice vrcholů z množiny vrcholů grafu. Stupeň vrcholu X je číslo, jehož hodnota udává počet hran vycházejících z X. Posloupnost stupňů všech vrcholů grafu se nazývá skóre grafu. O posloupnosti kladných celých čísel P = a₁, a₂,… , a_n řekneme, že je grafová, pokud existuje alespoň jeden graf mající skóre P.

Na vstupu byly názvy měst (vrcholy grafu) a počty spojení z měst (stupně vrcholů). Stačilo tedy pouze zjistit, zda je vstupní posloupnost stupňů vrcholů grafová. To vám však činilo potíže. Uváděli jste obvykle nepostačující podmínky pro existenci grafu jako např. součet stupňů vrcholů musí být sudé číslo, největší stupeň nesmí být větší než je počet vrcholů minus jedna. Jak spolehlivě zjistit, zda je posloupnost grafová, říká přesně následující tvrzení.

Havlova věta: Posloupnost celých čísel

kde n-1 ≥ s₁ ≥ s₂ ≥ … ≥ s_n ≥ 1, n ≥ 2 je grafová, právě když je grafová posloupnost S₂ = s₂-1, s₃-1,… , s_s1+1-1, s_s1+2, s_s1+3,… , s_n.

Důkaz:

1. Je-li posloupnost S₂ grafová, existuje graf G₂ na n - 1 vrcholech u₂, u₃,… , u_n takový, že stupeň vrcholu u_i je s_i-1 pro 2 ≤ i ≤ s₁+1 a s_i pro s₁+2 ≤ i ≤ n. Potom můžeme sestrojit nový graf G₁ tím, že připojíme nový uzel u₁ a nové hrany {u_1, u_i} (pro 2 ≤ i ≤ s₁+1). Graf G₁ ukazuje, že též posloupnost S₁ je grafová.
2. Nechť nyní S₁ je grafová posloupnost. Dokážeme, že existuje graf G₁ se skóre S₁ (stupeň u₁ je s₁, stupeň u₂ je s₂…) takový, že vrchol u₁ je spojen právě s vrcholy u₂, u₃,… , u_s1+1. Potom je S₂ zřejmě skórem grafu G₁ - {u₁}, tj. grafu, ze kterého odebereme vrchol u₁ a všechny hrany, které z něj vedou.

   Pro spor předpokládejme, že G₁ neexistuje. Vezměme tedy graf G takový, že vrchol u₁ není spojen s vrcholem u_i a i je maximální (zřejmě i ≤ s₁+1). Zřejmě musí existovat vrchol u_j, j > s₁+1 spojený s u₁ hranou. Protože s_j ≤ s_i, musí existovat vrchol u_k spojený s s_i a ne s s_j. Když nyní spočteme skóre grafu G' = G - {u₁, u_j} - {u_i, u_k} + {u₁, u_i} + {u_j, u_k}, zjistíme, že je to S₁. Potom ale G nemohl být graf s maximálním i, protože pro graf G' je i větší. Spor.

Náš algoritmus vychází přímo z Havlovy věty. Opakovaným použitím věty se zachovává invariant – posloupnost je stále grafová a přitom se při každém použití věty zmenší počet členů posloupnosti stupňů alespoň o jedna. Tedy má-li posloupnost na počátku N členů, pak algoritmus skončí nejpozději po N-1 použitích věty. Náš algoritmus je tedy konečný a korektní. Zde jsou jeho kroky podrobněji:

1. Načti posloupnost stupňů (alespoň 2 členy).
2. Odstraň nulové členy z posloupnosti a posloupnost sestupně setříď.
3. Pokud nemá posloupnost ani jeden člen, skonči.
4. Je-li první člen posloupnosti s₁ větší než počet členů posloupnosti minus jedna, skonči a oznam podvod. Jinak od následujících s₁ členů odečti jedna a při každém odečítání vypiš spojení: název města odpovídajícího vrcholu se stupněm s₁ → název města odpovídajícího vrcholu, jehož stupeň snižujeme o 1. Nakonec odstraň 1. člen posloupnosti.
5. pokračuj krokem 2

První třídění provedeme algoritmem quicksort, se složitostí O(N· log N), kde N je počet měst. Další třídění provádíme rychleji takto: Během kroku 4 se odečítáním jedničky od setříděných členů posloupnosti zachovává setřídění, problém může nastat jen na konci bloku, kde jsme odečítali jedničku. Je-li posloupnost např. S₃ = 5, 4, 4, 3, 3, 3, 3, 3, … mohla nastat nejhůř situace S₄ = 3, 3, 2, 2, 2, 3, 3,… Pokud odečítání jedničky skončilo uprostřed úseku stejných hodnot, dojde k situaci S₄, kdy není posloupnost setříděná. Stačí ale nalézt okraje úseku s původně stejnými hodnotami a celý úsek převrátit. Tím dostáváme opět setříděnou posloupnost. Okraje původního úseku nalezneme po odečtení jedniček snadno. Pravý okraj je nejpravější člen od posledního zmenšovaného členu, který má hodnotu o jedna větší než poslední zmenšovaný člen. Obdobně levý okraj úseku.

Převracený úsek může mít maximálně délku N. Tedy setřídění provedeme v čase O(N). V kroku 4 algoritmu můžeme odečítat maximálně ode všech zbývajících členů. Složitost tohoto kroku je tedy také O(N). Kroky 2 a 4 se opakují maximálně N-1 krát, což jsme zdůvodnili výše. Celková časová složitost algoritmu je tedy O(N²). Pokud algoritmus přímo přepíšeme do programu, nedostaneme ovšem přesný výstup podle příkladu, neboť algoritmus vypisuje průběžně spojení mezi městy a když zjistí podvod, vypíše to. Zadání však vyžaduje vypsat buď obvinění z podvodu nebo seznam spojení mezi městy. To v programu vyřešíme např. tak, že celý postup necháme proběhnout dvakrát, což na asymptotické složitosti nic nemění. Jednou bez vypisování spojení a pokud se nevypíše „podvod!“, pak celý postup zopakujeme, ale s vypisováním spojení, neboť už je jasné, že telefonní síť existuje. Tato úprava nás bude stát dvojnásobné množství paměti na vstupní data. Celková paměťová náročnost je však stále lineární.

Program

Martin Mafi Bělocký

11-3-2 Ffffaktoriál (Zadání)

Nejprve se zkusme nad zadanou úlohou trochu zamyslet. Nechť n je dáno. Počet koncových nul čísla n! je roven největšímu k₁₀ takovému, že 10^k₁₀ | n!, což je rovno min{k₂,k₅}, kde k₂ je největší číslo takové, že 2^k₂ | n!, analogicky je definováno k₅. Tato čísla tedy udávají počet dvojek resp. pětek v prvočíselném rozkladu n!. Protože dvojka i pětka jsou prvočísla, tak platí:

Nyní se na chvíli ještě zamysleme nad následující úvahou (často vídanou ve vašich řešeních): Poslední nenulovou číslici mohu určit tak, že spočítám součin všech posledních nenulových číslic čísel 1 až n různých od pětek a potom za každou poslední číslici rovnou pěti odeberu z tohoto součinu jednu dvojku (tím vyeliminuji dvojky „spotřebované“ na koncové nuly) — což udělám např. tak, že z číslic osm v tomto součinu udělám čtyřky. Tato úvahu je však chybná! Neboť 28/2 je sice 14, ale 38/2=19 a tuto osmičku jsme v žádném případě nahradit čtyřkou nemohli. Proto jsme také v našem řešení museli z některých dvojek dělat jedničky a z jiných šestky.

Program

Daniel Kráĺ

11-3-3 Obdélníčky (Zadání)

Algoritmus pro řešení této úlohy pracuje následujícím způsobem: Do pomocného pole P si uloží všechny hodnoty x-ových souřadnic, na kterých nějaký čtverec začíná nebo končí. Toto pole následně setřídí. Je vidět, že pás mezi přímkami x=P[i] a x=P[i+1] už neobsahuje žádnou svislou hranu, takže si náš stůl rozdělíme na takovéto pásy a spočítáme obsah pokryté části v každém pásu.

Budeme potřebovat pole čtverců, setříděné podle dolní y-ové souřadnice. V tomto poli postupujeme po jednom čtverci a u každého čtverce nejprve zkontrolujeme, zda má s daným pásem neprázdný průnik (tedy x₁ ≤ px₁ a x₂ ≥ px₂, kde x₁ a x₂ jsou x-ové souřadnice čtverce a px₁ a px₂ hranice pásu). Dále otestujeme, zda čtverec není úplně obsažen v předchozím (y₁ > maxy, kde y₁ je horní y-ová souřadnice čtverce a maxy maximální y-ová souřadnice z předchozích čtverců). Pokud není, připočteme jeho výšku k celkové výšce čtverců v tomto pásu a odečteme výšku průniku s předchozím čtvercem (v = v + y₁ - y₂ - max(maxy - y₂, 0), maximum zajišťuje, že nám průnik nevyjde záporný). Pak jen stačí celkovou výšku vynásobit šířkou pásu a přičíst k prozatimnímu obsahu. Toto se opakuje pro všechny pásy.

Časová složitost: vytvoření pomocného pole P spotřebuje O(N) (každý čtverec přidá maximálně dva pásy), jeho setřídění O(N log N), setřídění čtverců podle dolní y-ové souřadnice O(N log N), spočítání celkové výšky čtverců v pásu O(N). Celkem tedy O(N²).

Paměťová složitost: několik polí o délce O(N) a pár pomocných proměnných. Celkem O(N).

V popisu programu jsou vynechána některá triviální místa. Jejich implementaci byste jistě zvládli sami.

Program

Michal Píše

[Pozn.: Existuje i řešení v čase O(N log N), ale je poměrně složité. Idea: Opět si rovinu rozřežeme na svislé pásy, ale jejich zaplnění počítáme efektivněji. Na počátku si setřídíme všechny hodnoty y-ových souřadnic vrcholů obdélníků a sestavíme vyvážený binární strom, jehož listy budou odpovídat intervalům na y-ové ose, v nichž žádný obdélník nezačíná ani nekončí, a pro každý z těchto intervalů si budeme průběžně udržovat, kolik obdélníků v daném pásu tento interval pokrývá. Obsah průniku všech obdélníků v pásu je pak roven celkové délce všech pokrytých intervalů vynásobené šířkou pásu. Stačí pouze dořešit, jak do tohoto stromu vkládat a odstraňovat intervaly a aktualizovat si současně celkovou délku intervalů, to vše v čase O(log N)… –M.M.]

11-3-4 Machina Universalis (Zadání)

Nejdříve doplníme "bílá místa v zadání":

• Převod všech Pascalských datových typů na wordy:
  • Celočíselné typy bez znaménka můžeme přímo nahradit wordem.
  • Celočíselné typy se znaménkem nahradíme recordem, jehož první prvek bude absolutní hodnota a druhý znaménko.
  • Ostatní ordinální typy nahradíme ordinálními čísly.
  • Typ real můžeme ukládat jako record obsahující mantisu a exponent, případně čitatele a jmenovatele zlomku.
  • Record obsahující wordy (speciálně tedy cokoliv, co umíme zakódovat do wordu) nahradíme polem wordů.
  • Pole wordů indexované wordem (tedy vlastně pole čehokoliv indexované čímkoliv, za předpokladu že jsme všechno schopni wordem popsat) je jediné, co vám působilo větší problémy. Ukážeme si jeden z mnoha možných přístupů, který využívá toho, že každé kladné celé číslo má jednoznačný rozklad na prvočinitele.
    Buď p₁,p₂,… rostoucí posloupnost všech prvočísel (jistě si dovedete představit funkci p(n), která spočte n-té prvočíslo). Pak pole hodnot
    x₁,x₂,… ,x_n
    zakódujeme číslem
    p

    x1

    1

    ·p

    x2

    2

    ·… ·p

    xn

    n

    .
    Indexovat takto reprezentované pole je velice jednoduché: spočteme si prvočíslo odpovídající indexu a zjistíme, kolikrát je kód pole možno beze zbytku tímto prvočíslem vydělit. Změna jedné hodnoty v poli je také snadná: opět nalezneme příslušné prvočíslo, dělíme jím kód, dokud to jde (tím jsme x_i vynulovali) a poté násobíme tolikrát, na kolik chceme x_i nastavit.
  • Dynamické proměnné a pointery: celou paměť lze reprezentovat jako
    memory:array [word] of word,
    čímž je problém vyřešen.
• Rozklad cyklů a podmínek na podmíněné skoky:
  • if A then B else C
    → if A then goto 1; C; goto 2; 1: B; 2:
  • while A do B
    → goto 1; 2: B; 1: if A then goto 2;
  • repeat A until B
    → 1: A; if not B then goto 1;
  • Cyklus for snadno převedeme na while.
• Převod triviálních operací:
  • Sčítání: viz příklad v zadání.
  • Odčítání: analogicky, pouze INC 0 na předposledním řádku nahradíme instrukcí DEC 0. Navíc pro x<y vyjde x-y=0, což se nám bude hodit.
  • Skok podmíněný rovností: přímo instrukcí JEQ.
  • Skok podmíněný nerovností x≤ y: testujeme x-y=0 (ostatní nerovnosti analogicky, případně negací již odvozené podmínky).
  • Ještě potřebujeme přiřazení, ale to vyřešíme jednoduchou úpravou sčítacího podprogramu: budeme inkrementovat najednou dvě paměťové buňky, čímž si výsledek „rozmnožíme“ a potom pro přiřazení x:=y provedeme v:=y+0 (tím jsme přišli o obsah y) a (x,y):=v+0 (opraveno a zkopírováno).

Nyní již stačí odvodit universální programy a budeme hotovi.

Sestrojíme program P v Pascalu, který bude interpretovat program v mikroassembleru zadaný jako pole čtveřic čísel (kódů instrukcí), samozřejmě reprezentované jedním wordem. Tento program je natolik přímočarý, že pokládáme za zhola zbytečné jej zde uvádět. Nyní spojíme-li v zadání popsaný překladač z μ₁ do Pascalu s tímto programem, vznikne nám universální program pro Pascal a naopak přeložíme-li program P tímto překladačem, vznikne universální program pro μ₁. Toť vše.

Zvídavého čtenáře samozřejmě dříve či později napadne záludná otázka „a k čemu je tohle všechno dobré?“

To, že Pascal je výpočetně stejně silný jako Mikroassembler (to znamená, že se v obou těchto výpočetních modelech dá spočítat to samé) a že jsme též dokázali, že totéž platí o Pascalu a nedeterministickém Pascalu (viz druhá série), naznačuje, že i na první pohled velice odlišné programovací prostředky umí vlastně to samé. Tak řečená Churchova teze říká, že toto platí pro všechny rozumné výpočetní modely (bohužel ji není možno dokázat, protože není jasné, co vlastně znamená formulace „rozumný výpočetní model“).

Existence universálního programu nám pro změnu naznačuje, že s programy je možné nakládat jako s přirozenými čísly, kterým právě universální program přiřazuje význam. Na universální program se tak můžeme dívat jako na nějakou funkci U(p,x), která má za parametry číslo programu p, který má interpretovat a vstup x pro tento program a platí U(p,x)=p(x) [přičemž za jednu z možných hodnot výstupu považujeme také stav „nedoběhne“].

Z tohoto pozorování můžeme vyvodit spoustu užitečných věcí, například dokázat, že neexistuje žádný algoritmus rozhodující Halting Problem (to jest zjišťující, zda se daný program pro daný vstup zastaví či nikoliv). Předpokládejme pro spor, že takový algoritmus existuje – mějme tedy funkci H(p,x), která vrací jedničku v případě, že se p(x) zacyklí a nulu, pokud se zastaví. Potom také můžeme sestrojit program R(x) následujícího znění:

Nyní si ovšem položme otázku, jak odpoví R na svůj vlastní kód, tedy kolik je R(R). Pokud se R(R) zastaví, znamená to, že H(R,R)=1, tudíž že se R(R) dle funkce H zastavit neměl. Naopak, pokud se nezastaví, bylo H(R,R)=0, tedy se dle H zastavit měl. Takže se nemůže ani zastavit, ani nezastavit, což je spor. Tudíž žádný program H s touto vlastností neexistuje.

Martin Mareš

11-3-5 Pascal či Céčko? (Zadání)

Většina z vás správně pochopila, že ve zdrojáku je nutno nakombinovat vhodně komentáře, a tak jediným problémem zůstalo zahájení programu. Způsobů je hned několik:

2. Nejobvyklejší bylo klíčové slovo const. Pak je možno navázat např. struct {, které v Pascalu deklarovalo konstantu struct a otevíralo komentář, zatímco v C se tímto pouze deklaroval záznam. Další pokračování je zřejmé z přiloženého programu. Jinou možností je enum {.(programy 1,2)
3. Za slovem const může následovat i hodnota konstanty x={1. Jazyk C toto povoluje.(program 3)
4. Jeden z nejkratších způsobů je (*x);. Toto v Pascalu otevírá komentář, zatímco v C deklaruje proměnnou typu ukazatel na int, nicméně zastaralým způsobem podle originální normy jazyka C; novější standardy to již jen mlčky připouštějí a návrh standardu C9x dokonce zakazuje. Tomu se dá samozřejmě předejít uvedením oblíbeného const int (*x);.(programy 4,5)
5. Existují i další neportabilní řešení, např. využívající proměnné randseed v Borland Pascalu. Toto začíná begin(randseed){. V C takto začíná deklarace funkce, v Pascalu již samotný program.(program 6)

Většina vašich řešení nechala ignorovat text za závěrečným Pascalovským end. Standard toto myslím předepisuje, nicméně některé kompilátory (např. gpc) se podle toho neřídí. Čistší je zbylý text v Pascalu zakomentovat.

Další elegantní řešení má úloha zabývající se rozlišením C a C++. Marek Sterzik využil toho, že překladače C a C++ se chovají jinak při práci s pojmenovanými strukturami (viz zdrojový text na konci řešení).

Výraz sizeof(struct a) v každém případě vrátí velikost struktury. Ale výraz sizeof(a) pochopí každý překladač jinak. Překladač C vypočítá velikost proměnné, zatímco překladač C++ si automaticky doplní klíčové slovo struct a zabývá se opět strukturou.

Dále se dá snadno rozlišit, zda překladač C/C++ podporuje C++ komentáře //. Konstrukce 1//**/2 si totiž vyloží buď jako 1 nebo jako 1/2.

Několik prográmků napsaných pod jinými programovacími jazyky je uvedeno na konci řešení.

Můžete si prohlédnout ještě jeden pěkný program nalezený na Internetu. Jeho autor o něm tvrdí, že je napsán v těchto jazycích: COBOL, Pascal, Fortran, C, PostScript, shellový skript a spustitelný program v MS-DOSu. V každém z těchto jazyků by měl program vypsat pozdrav `Hello polyglots'. Neměl jsem možnost otestovat Fortran ani COBOL, ale v Pascalu, C a PostScriptu program skutečně funguje. Při spuštění v shellu bash vypisuje tento množství chybových hlášek, ale nápis je rovněž vypsán. Když jsem se ho pokusil spustit pod MS-DOSem, tak spadl.

Robert Špalek

Pascal vs. C:

1. const struct {/*} =1; begin writeln('Pascal'); end.
   (*/} a; int main() { printf("C\n"); return 0; /*) {*/}
   

2. const enum {/*} =1; begin writeln('Pascal'); end.
   (*/x} a; int main() { printf("C\n"); return 0; /*) {*/}
   

3. const x={1/*}1; begin writeln('Pascal'); end.
   (*/}; int main() { printf("C\n"); return 0; /*) {*/}
   

4. const int (*a); int main(){ printf("C\n"); return 0;
   /*) =1; begin writeln('Pascal'); end. {*/}
   

5. (*x)(); int main(){ printf("C\n"); return 0;
   /*) begin writeln('Pascal'); end. {*/}
   

6. begin (randseed) {/*}:=0; writeln('Pascal'); end. (*/
   return 0; } int main(){ printf("C\n"); return 0; /*) {*/}
   

1. int a[2]; int main(){ struct a{int b;};
   printf(sizeof(a)==sizeof(struct a) ? "C++\n" : "C\n"); return 0;}
   

2. int main(){ printf("does%s support //\n",1//**/2
   ?"":" not"); return 0;}
   

1. Martin Zlomek: jednoduché propojení assembleru TASM a C.

   ;/*
   .model tiny
   .code
   org 100h
   start:
   	mov ah,9
   	mov dx,offset text
   	int 21h
   	xor ah,ah
   	int 21h
   text	db 'ASM',13,10,'$'
   end start
   */ int main(){printf("C\n"); return 0;}
   

2. Zdeněk Dvořák: celkem mazané propojení Prologu (odzkoušeno na LPA win Prolog) a C.

   //// . ?-op(50,fx,int). a:-
   int X=3%2; int main(){printf("C\n");return 0;}
   ; //// . ?-write('Prolog'),nl.
   

3. Zdeněk Dvořák: propojení Prologu (odzkoušeno na LPA win Prolog) a Basicu (Q-Basic).

   'Basic-comment'. ?-op(50,xf,x). ?-op(50,xfy,:). a:-
   X = 0: 'a'. a:-
   PRINT X; "Basic": 'Basic-comment'. ?-write('Prolog'),nl.