Druhá série šestého ročníku KSP

Tyto úlohy pocházejí z desetileté ročenky KSP. Jejich řešení bohužel nemáme v elektronické podobě, takže na ně budete muset přijít sami.

Zadání úloh

6-2-1 ZAZZAAZZZ

V království ZAZZAAZZZ mají n měst. V den, kdy napadne první sníh, se král podívá na mapu a určí, které silnice, mezi kterými městy, budou v zimě udržovány. Žádné dvě silnice se nikde mimo město nekříží a všechny silnice vycházející z nějakého města jsou v tomto městě propojeny. Jelikož mají pouze jeden sypací vůz a král je skrblík, silnice musí být vybrány tak, aby bylo možno vyjet se sypacím vozem z hlavního města, všemi králem vybranými silnicemi projet právě jednou (libovolným směrem) a skončit v nějakém městě.

Vaším úkolem je napsat program, který ověří, zda králem vybrané silnice lze takto projet a pokud ano, tak v jakém pořadí. Vstupem programu je množina dvojic čísel udávajících silnice, kterými je nutno projet (v libovolném směru). Dvojice (X,Y) udává silnici mezi městy X a Y. Města jsou očíslována od 1 do n, 1 označuje hlavní město. Výstupem programu je posloupnost silnic v pořadí, jak jimi budeme projíždět. Pokud zvolené silnice nelze projet, pak je výstupem pouze informace o této skutečnosti.

6-2-2 Barman

Barman má k dispozici dvě nádoby A a B. Objem nádoby A je VA, objem nádoby B je VB. Kromě toho má k dispozici neomezené množství whisky, vodky, malinové šťávy, rumu a mléka. Z těchto ingrediencí míchá koktejly, proto potřebuje přesně odměřovat objemy těchto tekutin. S uvedeným náčiním může provádět následující operace:

  1. nalej tekutinu až po okraj do nádoby A
  2. vylej všechnu tekutinu z nádoby A
  3. přelej obsah nádoby A do nádoby B (při této operaci buď nádobu B naplníme až po okraj nebo nádobu A úplně vyprázdníme.)
  4. to samé jako (3), ale z B do A.

Napište program, který pro zadané objemy VA a VB a požadovaný výsledný objem V vypíše sled operací (1) až (4) takový, že po jejich vykonání budeme mít v nádobě A požadovaný objem tekutiny.

6-2-3 Podmatice

Je dána matice o rozměrech n×n. Hodnotou prvků této matice jsou nuly a jedničky. Matice je zadána postupně hodnotami svých prvků. Vaším úkolem je napsat program, který pro zadanou matici určí největší obdélníkovou podmatici, která obsahuje pouze nulové prvky. Podmaticí rozumíme každou matici, která vznikne z původní matice vynecháním několika (i žádných) prvních nebo i posledních sloupců resp. řádků (tzn. souvislý obdélníkový výřez).

6-2-4 Kompreseeeee

Soubory jsou dlouhé a vše nasvědčuje tomu, že budou ještě delší. Proto lidé vymýšleli a stále ještě vymýšlejí způsoby, jak se tomu bránit. I Vy se zařadíte mezi ně. Způsob, jakým se lidé brání narůstání souborů, je, že píší programy, které z libovolného souboru A udělají soubor B, jenž je co do délky kratší nebo roven až na konstantu délce souboru A. Zároveň však napíší program, který je schopen vzít soubor B a bez ohledu na počasí či jiné povětrnostní okolnosti dokáže na základě tohoto souboru vytvořit soubor C, jehož obsah je totožný s obsahem původního souboru A. Těmto dvěma procesům se říká komprese a dekomprese. Kompresní programy využívají faktu, že hodnoty (čísla, znaky, slova, …) obsažené v souborech se často opakují, jsou pouze z nějakého určitého intervalu atd.

Vaším úkolem je popsat, podle vašeho názoru co nejlepší, kompresní (a k němu příslušný dekompresní) algoritmus, tj. způsob jak komprimovat. Program u této úlohy není podmínkou, hodnotí se nápaditost, efektivita, etc. („opravující má vždycky pravdu“).