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

Vzorová řešení


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 = a1, a2,… , an ř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

S1 = s1, s2,… , sn,

kde n-1 ≥ s1 ≥ s2 ≥ … ≥ sn ≥ 1, n ≥ 2 je grafová, právě když je grafová posloupnost S2 = s2-1, s3-1,… , ss1+1-1, ss1+2, ss1+3,… , sn.

Důkaz:

  1. Je-li posloupnost S2 grafová, existuje graf G2 na n - 1 vrcholech u2, u3,… , un takový, že stupeň vrcholu ui je si-1 pro 2 ≤ i ≤ s1+1 a si pro s1+2 ≤ i ≤ n. Potom můžeme sestrojit nový graf G1 tím, že připojíme nový uzel u1 a nové hrany {u_1, u_i} (pro 2 ≤ i ≤ s1+1). Graf G1 ukazuje, že též posloupnost S1 je grafová.
  2. Nechť nyní S1 je grafová posloupnost. Dokážeme, že existuje graf G1 se skóre S1 (stupeň u1 je s1, stupeň u2 je s2…) takový, že vrchol u1 je spojen právě s vrcholy u2, u3,… , us1+1. Potom je S2 zřejmě skórem grafu G1 - {u1}, tj. grafu, ze kterého odebereme vrchol u1 a všechny hrany, které z něj vedou.

    Pro spor předpokládejme, že G1 neexistuje. Vezměme tedy graf G takový, že vrchol u1 není spojen s vrcholem ui a i je maximální (zřejmě i ≤ s1+1). Zřejmě musí existovat vrchol uj, j > s1+1 spojený s u1 hranou. Protože sj ≤ si, musí existovat vrchol uk spojený s si a ne s sj. Když nyní spočteme skóre grafu G' = G - {u1, uj} - {ui, uk} + {u1, ui} + {uj, uk}, zjistíme, že je to S1. 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 s1 větší než počet členů posloupnosti minus jedna, skonči a oznam podvod. Jinak od následujících s1 č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 s1 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ř. S3 = 5, 4, 4, 3, 3, 3, 3, 3, … mohla nastat nejhůř situace S4 = 3, 3, 2, 2, 2, 3, 3,… Pokud odečítání jedničky skončilo uprostřed úseku stejných hodnot, dojde k situaci S4, 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(N2). 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 k10 takovému, že 10k10 | n!, což je rovno min{k2,k5}, kde k2 je největší číslo takové, že 2k2 | n!, analogicky je definováno k5. 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í:

k2 =
n
2
+
n
22
+
n
23
+ ...= ∑
i=1
n
2i
k5 =
n
5
+
n
52
+
n
53
+ ...= ∑
i=1
n
5i
Správnost výše uvedených vztahů je zřejmá, neboť
n
2
udává počet čísel menších nebo rovných n dělitelných dvěma,
n
22
je počet čísel dělitelných 22 atd. Čísla dělitelná právě dvěma přispějí do prvočíselného rozkladu n jednou dvojkou, čísla dělitelá čtyřmi ještě jednou dvojkou (kromě té za dělitelnost dvěma) atd. Analogickou úvahu lze provést pro dělitelnost pěti.
Idea našeho algoritmu bude následující: Ze všech čísel dělitelných pěti, tyto pětky vytkneme, a za každou z nich, vytkneme z nějakého jiného čísla dvojku – tak obdržíme součin nějakých nových čísel ai. Tedy n! převedeme do tvaru 10m Π
n
i=1
ai, kde žádné z čísel ai není dělitelné pětkou a tedy poslední číslice jejich součinu nemůže být nula. Jinými slovy: Poslední číslice jejich součinu je poslední nenulová číslice n!. Výše uvedený součin budeme počítat v několika fázích – nejprve vypočteme součin těch ai, která vznikla z čísel nedělitelných pětkou, potom těch, která vznikla z čísel dělitelných právě pětkou, potom z čísel dělených právě dvaceti pěti atd. Kromě toho v první fázi některá z čísel podělíme dvojkami za čísla dělitelná jednou pětkou, v druhé fázi dělíme za čísla dělitelná dvaceti pěti atd. Dvojkou nebudeme dělit „náhodně vybraná“ čísla, ale za čísla, která končila pětkou, podělíme dvojkou čísla končící dvojkou (vznikne jako poslední číslice jednička nebo šestka), a za čísla, která končila nulou, podělíme dvojkou, čísla končící šestkou (vznikne jako poslední číslice trojka nebo osmička). Tímto přístupem si zajistíme, že v každé fázi budeme schopni v konstantním čase zjistit počet násobených čísel, která končí cifrou jedna, dvě, tři, čtyři, šest, sedm, osm nebo devět. Poslední číslici mohu nyní snadno spočítat modulo 10, což s pozorováním i=i5 mod 10 pro uvažovaná i zvládnu v konstantním čase. Každá z O(log n) fází bude trvat konstantní čas a celkový čas spotřebovaný naším algoritmem tedy bude O(log n).

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 x1 ≤ px1 a x2 ≥ px2, kde x1 a x2 jsou x-ové souřadnice čtverce a px1 a px2 hranice pásu). Dále otestujeme, zda čtverec není úplně obsažen v předchozím (y1 > maxy, kde y1 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 + y1 - y2 - max(maxy - y2, 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(N2).

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ď p1,p2,… rostoucí posloupnost všech prvočísel (jistě si dovedete představit funkci p(n), která spočte n-té prvočíslo). Pak pole hodnot
      x1,x2,… ,xn
      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 xi vynulovali) a poté násobíme tolikrát, na kolik chceme xi 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 μ1 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 μ1. 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í:

R(x) =
0 pokud H(x,x)=1
zacyklí se pokud H(x,x)=0.

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:

  1. 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)
  2. Za slovem const může následovat i hodnota konstanty x={1. Jazyk C toto povoluje.(program 3)
  3. 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)
  4. 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í.

Na ftp://atrey.karlin.mff.cuni.cz/pub/ksp/polyglot.c si můžete 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; /*) {*/}
    
C vs. C++:
  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;}
    
Ostatní jazyky:
  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.