Hodnocení soutěžních úloh

Kategorie žáci

Soutěž dětí a mládeže v programování – 20. ročník

Krajské kolo 2005/2006

20. a 22. dubna 2006

Převod textu na čísla

Koeficient 1

Na klávesnici telefonního přístroje jsou k jednotlivým číslům vždy přiřazena písmena popřípadě další znaky. Je pravda, že na každém přístroji jsou jednotlivé znaky uspořádány jinak, pro naši potřebu budeme uvažovat telefonní přístroj, který má písmena a znaky rozmístěné na klávesnici takto:

TlačítkoZnaky
1+ - = * / _ . ,
2A B C a b c
3D E F d e f
4G H I g h i
5J K L j k l
6M N O m n o
7P Q R S p q r s
8T U V t u v
9W X Y Z w x y z
0mezera

Napište program, který převede zadané jméno na telefonní číslo podle následujících pravidel:

  1. Jméno má délku přesně 9 písmen, pokud je zadané jméno kratší, bude jeho délka upravena na 9 přidáním mezer za zadané jméno.

  2. Jednotlivá písmena se na čísla převádějí podle výše uvedené tabulky.

  3. Písmena české abecedy bude program považovat za neznámý znak.

  4. Pokud zadané jméno obsahuje znaky, které nejsou uvedeny v tabulce, program oznámí chybu zadání.

  5. Výstupem z programu bude telefonní číslo rozdělené do trojic pro lepší čitelnost.

Příklad 1. Ukázkové převody

Babicka    → ‚Babicka  ‘    →  222 425 200
Lenka      → ‚Lenka    ‘    →  536 520 000
Karolina   → ‚Karolina ‘    →  527 654 620
Aja+Pavel  → ‚Aja+Pavel‘    →  252 172 835
&)@goryla  → chybné zadání
Kůň        → chybné zadání

Dále rozšiřte program o následující funkce:

  1. Převod zadaného telefonního čísla na písmena a znaky podle výše uvedené tabulky. Telefonní číslo má přesně 4 číslice, pokud bude zadáno kratší nebo delší telefonní číslo, program ohlásí chybu zadání. Program vypíše všechny možnosti pro převod zadaného čísla na písmena a znaky.

  2. Program ve výpisu označí ta slova, která jsou snadno vyslovitelná. Za snadno vyslovitelné slovo se přitom považuje slovo splňující následující podmínky:

    • Písmena jsou poskládána k sobě tak, aby výsledkem bylo pokud možno vyslovitelné (nemusí být smysluplné) „slovo“, tj. střídají se za sebou vždy jedna souhláska a jedna samohláska. Bude-li v telefonním čísle zadáno více číslic 5 nebo 7 za sebou, lze za samohlásku považovat i písmena L a R.

    • Výsledná „slova“ musí začínat souhláskou.

    • Číslici 0 převeďte na mezeru a číslici 1 na znak „+“, v posuzovaní vyslovitelnosti se mezera i „+“ berou jako souhlásky.

Příklad 2. Možné převody čísla 2465 na slovo

2465    →    AGMJ
2465    →    AGMK
2465    →    AGML
2465    →    AGMM
2465    →    AGNJ
…
2465    →    *BIML*
…

Příklad 3. Možné převody čísla 7755 na slovo

7755    →    PPJJ
7755    →    PPJK
7755    →    PPJL
7755    →    PPKJ
…
7755    →    *PRKL*
…

Příklad 4. Možné převody čísla 1662 na slovo

1662    →    +MMA
1662    →    +MMB
1662    →    +MMC
1662    →    +MNA
…
1662    →    *+OMA*
…

Příklad 5. Možné převody čísla 1001 na slovo

1001	→    +  +

Číslo 1001 nejde převést na vyslovitelné slovo.


Hodnocení

funkčnost2 bodykontrola délky vstupu, přidání mezer
2 bodykontrola povolených znaků
2 bodyvýpis chyby v případě špatného vstupu
1 bodZadá se babicka, program vypíše 222425200
1 bodZadá se Aja+Pavel, program vypíše 252172835
1 bodProgram vypíše číslo oddělené po třech číslicích
dokumentace1 bodkomentáře, přehlednost, výstižné názvy proměnných, …

Zahrada strýčka Pompa

Koeficient 2

Strýček Pompo má na své zahradě N sousedních záhonů.

     _ _ ___ _
    | | |   | |
    |1|2|...|N|
    |_|_|___|_|

Na každý záhon chce vysadit buď mrkev nebo petržel. Protože je ale mrkev velmi náročná, nemůže být vysazená na dvou sousedních záhonech.

Strýček Pompo se pořád nemůže rozhodnout, jak si má zahradu osázet, a rád by věděl, kolika způsoby to vlastně může udělat.

Vaším úkolem je tedy napsat program, který na vstupu dostane N, počet záhonů, a vypíše, kolika různými způsoby může strýček Pompo svou zahrádku osázet. Protože toto číslo může být opravdu ohromné, stačí, když vypíšete jeho posledních 6 cifer.

Příklad 6. Možnosti osázení pro N = 2

     _ _      _ _      _ _   
    | | |    | | |    | | |  
    |P|P|    |P|M|    |M|P|  
    |_|_|    |_|_|    |_|_| 

Váš program by měl fungovat pro N <= 30.

Součástí řešení by také měl být popis algoritmu a zdůvodnění, proč vámi použitý algoritmus funguje správně.

Hodnocení

Funkčnost programu se testuje pomocí osmi úloh, za každou je jeden bod. Program musí výsledek vrátit do 10 sekund, jinak se za něj bod nepřiděluje.

funkčnost1 bodpro vstup 4, vrátí program 8
1 bodpro vstup 7, vrátí program 34
1 bodpro vstup 10, vrátí program 144
1 bodpro vstup 14, vrátí program 987
1 bodpro vstup 18, vrátí program 6764
1 bodpro vstup 22, vrátí program 46368
1 bodpro vstup 26, vrátí program 317811
1 bodpro vstup 30, vrátí program 178309
dokumentace1 bodpopis algoritmu
1 bodkomentáře, přehlednost, výstižné názvy proměnných, …

Vrtákova šifra

Koeficient 3

Vnislav Rastafarián Trdlifác Ámoklec von Koniklec používá kabelový přenos dat. Takový kabelový přenos vypadá tak, že se data nahrají na disketu, dají do kabely a poslíček kabelu přenese na cílové místo. Protože ale poslíčci četli Vrtákovy soukromé dopisy, rozhodl se své přenosy šifrovat. K tomu chce použít následující šifru.

Máme dvě čtvercové kartičky rozdělené na N×N čtverečků, kde N musí být sudé. Jedna kartička je celá, takzvaná podložka, na druhé je čtvrtina čtverečků vyříznutá. Této druhé kartičce budeme říkat šifrovací.

Navíc platí, že když přiložíme šifrovací kartičku na podložku, vybarvíme na podložce všechna políčka vyříznutá na šifrovací kartičky, pak šifrovací kartičku otočíme o 90° po směru hodinových ručiček, opět vybarvíme, znovu otočíme, vybarvíme a ještě jednou otočíme a ještě jednou vybarvíme, tak vybarvíme každý čtvereček na podložce právě jednou.

Příklad 7. Vybarvování podložky pomocí správné šifrovací mřížky

....
....
....
....
...x
.x..
....
.xx.
...@  ...x  .@@x  @xxx
.@..  @x@.  xxx.  xxx@
....  @...  x.@.  x@x@
.@@.  .xx@  @xxx  xxxx
podložka pro N = 2správná šifrovací mřížkapostup vybarvování podložky

Příklad 8. Vybarvování podložky pomocí špatné šifrovací mřížky

....
....
....
....
...x
.x..
..x.
.x..
...@   ...x   ..@x
.@..   @x@.   x!x.
..@.   .@x.   .x!.
.@..   .x.@   @x.x
podložka pro N = 2špatná šifrovací mřížkapostup vybarvování podložky[a]

[a] položky označené ! jsou vybarvené vícekrát


K zašifrování zprávy tedy potřebujeme šifrovací mřížku a podložku. Ze zprávy vezmeme prvních N2 písmen. Přiložíme šifrovací mřížku na podložku a postupně po řádcích vepíšeme první čtvrtinu písmen zprávy do vyříznutých políček šifrovací mřížky. Poté šifrovací mřížku otočíme o 90° ve směru hodinových ručiček, vepíšeme další čtvrtinu písmen a pokračujeme, dokud nevepíšeme na podložku všech N2 písmen. Poté přečteme podložku po řádcích a získáme tak zašifrovanou podobu prvních N2 písmen zprávy. Pak vezmeme další část zprávy, opět stejně zašifrujeme, a opakujeme, dokud nezašifrujeme celou zprávu.

Příklad 9. Postup šifrování

Máme zprávu „to je ale horko!“ a následující šifrovací mřížku:

...x
.x..
....
.xx.

Postup šifrování je pak následující (velká písmena vždy označují právě probíhající krok):

...T   ...t   .E t   Re t
.O..   Eo .   eo .   eo K
....   A...   a.H.   aOh!
. J.   . jL   O jl   o jl

Výsledný zašifrovaný text je „re teo kaoh!o jl“.


Dešifrování probíhá analogicky. Na začátku se zašifrovaných N2 písmen napíše na podložku, přiloží se šifrovací mřížka a přečtou se písmena, která jsou ve vyříznutých políčkách, mřížka se otočí...

Nyní k programu. Vaším úkolem je napsat program, který umožní:

  1. Editaci šifrovací mřížky: program umožní interaktivně zadávat šifrovací mřížku o rozměrech N×N pro sudé N od 4 do 10. Navíc buď umožní zadávat jenom korektní mřížky (bez překryvu políček při rotacích), nebo bude rozumným způsobem zobrazovat, zda je zadaná mřížka korektní. Mřížky musí jít načítat a ukládat. Formát uložené mřížky si můžete zvolit libovolný.

  2. Šifrovat a dešifrovat soubory: tento úkol se boduje až při splnění předchozího bodu editace šifrovací mřížky. Po zadání/načtení korektní šifrovací mřížky může uživatel zašifrovat či dešifrovat libovolný (i binární) soubor. Pokud nebude velikost souboru dělitelná počtem čtverečků na mřížce, poslední část souboru (obsahuje alespoň jeden a méně než N2 znaků) nechte nezašifrovanou.

Hodnocení

funkčnost1 bodprogram zobrazuje mřížku – síť políček a u políčka je poznat, zda je vyřízlé nebo není
1 bodprogram umožňuje interaktivně vyřezávat/„odvyřezávat“ jednotlivá políčka mřížky, ať už pomocí myši nebo klávesnice
1 bodnačítání a ukládání mřížky
1 bodjde zadávat buď jen korektní mřížky nebo program neustále zobrazuje, zda je mřížka korektní
1 bodjdou editovat mřížky právě pro N=4,6,8,10
1 bodšifrování/dešifrování příkladu 1
1 bodšifrování/dešifrování příkladu 2
1 bodšifrování/dešifrování příkladu 3
efektivita1 bodZvolte libovolnou mřížku velikosti 10x10. Nechte program zašifrovat sebe sama (spustitelný soubor) a pak ho opět rozšifrujte. Výsledný program musí být stejný. Pro porovnání můžete z příkazové řádky použít windowsovy program "fc jmeno_jednoho_souboru jmeno_druheho_souboru"
dokumentace1 bodkomentáře, přehlednost, výstižné názvy proměnných

3 body za šifrování a dešifrování se rozdělí každý za jednu následující úlohu. Za zašifrování je vždy 0.5 bodu, za odšifrování je taktéž 0.5 bodu.

1 bod za příklad ze zadání
 mřížka ...x  text             "to je ale horko!"
        .x..
        ....  zašifrovaný text "re teo kaoh!o jl"
        .xx.

1 bod za
 mřížka ..x.  text          "Nově najatý kůň je příliš žluťoučký
        ...x                 a pěje ódy na maďarské lány!"
        .x..  zašifrovaný   " kNaůntoývňaě j řujšťí ež olpliuadčjy
        x...  text           ek ý p óěnďáaknaé  myrals!"

1 bod za
 mřížka x.... text          "Nově najatý kůň je příliš žluťoučký
        x....                a pěje ódy na prastaré maďarské lány!"
        x....   
        x..x. zašifrovaný   "Ntý kůoň přív lluiěje ťšnajao učký
        xxxx. text           žay na  ptarépr rsměasjkae ódéď lánya!"
        .....

Těžiště soustavy

Koeficient 2

Vytvořte program na stanovení těžiště soustavy. Jako vstup slouží obrázek typu BMP, s černým pozadím, na kterém jsou hmotné body znázorněny tečkami (1×1 pixel) různých odstínů šedi vyjadřující hmotnost bodu. Program nechá uživatele vybrat interaktivně vstupní soubor. Program zobrazí vstupní soubor (obrázek) a vypíše souřadnice těžíště, počet hmotných bodů a hmotnost těžiště. Vysvětlení pojmu těžiště a popis formátu BMP najdete dále v textu.

Pro jednoduchost je zde několik omezení:

  1. Vstupní soubor má vždy velikost 256×256 pixelů.

  2. Vstupní soubor je nekomprimovaný BMP s 8bitovou barevnou hloubkou (paleta stupňů šedé – grayscale).

  3. Vstupních bodů nebude víc než 1024.

  4. Hodnota barvy (indexu) bodu odpovídá hmotnosti.

  5. Obrazová data pro nás začínají vždy o 1078 bajtů za startem souboru a jeden bajt odpovídá vždy jednomu bodu. Jde se po řádcích vzhledem k obrázku zleva doprava zdola nahoru. Tedy první data jsou levý dolní roh (souřadnice [0,0]), poslední pravý horní roh (souřadnice [255,255]). Jeden řádek má vždy 256 bajtů.

Těžiště

Těžiště soustavy hmotných bodů je takový bod, kterým je možno nahradit tuto soustavu jednotlivých bodů tak, aby bylo možno pracovat pouze s jedním náhradním bodem. Hmotnost těžiště je součtem hmotností jednotlivých bodů.

Polohu těžište (T) pro dva body (A a B) je možno stanovit například takto: T leží na spojnici A a B (AB) blíže k těžšímu bodu v poměru hmotností, tedy při stejné hmotnosti bodů (mA=mB) leží T přesně uprostřed. Obecně platí:

Tx = ((Bx − Ax) * mB / (mA + mB)) + Ax
Ty = ((By − Ay) * mB / (mA + mB)) + Ay
mT = mA + mB

Ax – souřadnice bodu A v ose x
Ay – souřadnice bodu A v ose y
Bx – souřadnice bodu B v ose x
By – souřadnice bodu B v ose y
Tx – souřadnice bodu T v ose x
Ty – souřadnice bodu T v ose y
mA – hmotnost bodu A
mB – hmotnost bodu B
mT – hmotnost bodu T (těžiště)

Polohu těžiště pro více bodů můžete stanovit obdobně. Je v jednom jakém pořadí postupně jednotlivé body započítáváme do těžiště. Například pro výpočet těžiště bodů A, B, C, D, E můžeme použít následující postupy:

  1. stanovíme těžiště první dvojice bodů A–B

  2. stanovíme těžiště druhé dvojice bodů C–D

  3. stanovíme těžiště dvojice (A–B)–(C–D)

  4. stanovíme těžiště dvojice E–((A–B)–(C–D))

  1. stanovíme těžiště první dvojice bodů A–B

  2. stanovíme těžiště dvojice bodů (A–B)–C

  3. stanovíme těžiště dvojice bodů ((A–B)–C)–D

  4. stanovíme těžiště dvojice bodů (((A–B)–C)–D)–E

Formát BMP

Formát BMP nabízí několik způsobů, jak ukládat obrázky. Pro naši úlohu můžete na vstupu předpokládat obrázky, které vyhovují výše popsaným omezením. Stačí tedy číst rovnou hmotnost jednotlivých bodů počínaje bajtem 1079. Pro načtení obrázku můžete samozřejmě využít i funkce programovacího jazyka pro práci s formátem BMP.

Hodnocení

funkčnost1 bodprogram nechá uživatele vybrat interaktivně vstupní soubor
1 bodprogram zobrazí vstupní soubor (obrázek)
1 bodprogram vypíše souřadnice a hmotnost těžiště pro obrázek test1.bmp (X=25; Y=35; N=30; M=6200)
1 bodprogram vypíše souřadnice a hmotnost těžiště pro obrázek test2.bmp (X=127,5; Y=127,5; N=125; M=18900)
2 bodyprogram vypíše souřadnice a hmotnost těžiště pro obrázek test3.bmp (X=109,5; Y=150; N=490; M=36669)
2 bodyprogram vypíše souřadnice a hmotnost těžiště pro obrázek test4.bmp (X=119; Y=140; N=987; M=222410)
1 bodProgram má praktické a přehledné rozhraní
dokumentace1 bodkomentáře, přehlednost, výstižné názvy proměnných

Kvůli zaokrouhlovací chybě při výpočtu je možné, že souřadnice těžiště se budou o 1–2 pixely lišit. Za tuto nepřesnost body nestrhávejte.