Druhá série čtvrté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

4-2-1 Bludiště

Je dána čtvercová síť o rozměru M×N polí. Každé pole je určeno svými souřadnicemi 1≤ x≤ M, 1≤ y≤ N. Sousední pole jsou ta, která se shodují právě v jedné souřadnici a v druhé se liší právě o 1. Pro lepší srozumitelnost budeme nyní místo slova pole používat „místnost“; čáru oddělující dvě pole nazveme „dveře“. Místnost [1,1] označíme jako Start, místnost [M,N] je Cíl. Dveře mezi dvěma místnostmi mohou být buď otevřené, nebo zavřené. Po obvodu sítě dveře nejsou. Jistě jste si již všimli, že různým odemykáním a zamykáním dveří vzniká vlastně bludiště. Vaším úkolem je navrhnout datové struktury pro uložení tohoto bludiště a napsat program, který pro dané M, N vygeneruje bludiště splňující následující podmínky:

  1. Mezi každými dvěma místnostmi existuje právě jedna cesta (speciálně: existuje právě jedna cesta Start–Cíl).
  2. Bludiště je náhodné, tzn. program při každém spuštění generuje s pravděpodobností blízkou 1 jiné bludiště.
  3. Bludiště není triviální, tzn. existují místnosti, v nichž jsou otevřeny více než dvoje dveře.

Poznámka: Jako funkci generující náhodná čísla používejte pouze funkci

function RND(Horni:integer):integer;

která vrací náhodné celé číslo v rozsahu <0,Horni-1>. Důležitý bude o tohoto příkladu důkaz správnosti a konečnosti algoritmu!

4-2-2 Rubikova tyč

Všichni jistě znáte Rubikovu kostku. Rubikova tyč je „Rubikova kostka“ o rozměru 2×2×3. Navrhněte datové struktury pro uchování informací o stavu tyče a napište program, který:

  1. Načte stav tyče ve vámi zvolené formě.
  2. Vypíše posloupnost tahů vedoucích ke složení tyče, pokud taková posloupnost existuje. V opačném případě oznámí neřešitelnost úlohy.
Dodržujte označení stěn a tahů:

4-2-3 Konstantní podmatice

Plochou obdélníkové podmatice matice A (A má velikost m ×n) určené dvěma prvky P1=A[i1,j1] a P2=A[i2,j2] nazveme počet jejích prvků, tj.

(i2-i1+1)·(j2-j1+1),

přičemž platí i2≥ i1 a j2≥ j1. Napište a dokažte co nejrychlejší algoritmus a program, který pro zadanou matici A:array [1..M,1..N] of integer; nalezne obdélníkovou podmatici s co největší plochou složenou ze samých stejných čísel a vytiskne souřadnice prvků, které ji určují.

4-2-4 Mečování

  1. w-řetězec je znakový řetězec, který může obsahovat alfanumerické znaky a wildcard(y).
  2. Wildcard je označení pro znaky * a ?. Jejich význam ve w-řetězci je následující: na pozici * lze umístit libovolný (tedy i prázdný) znakový podřetězec, neobsahující žádný wildcard, na pozici ? libovolný alfanumerický znak (rozumí se právě jeden znak různý od * a ?). Tuto záměnu wildcardu řetězcem, resp. znakem nazýváme rozvojem wildcardu. Rozvoj všech wildcardů ve w-řetězci nazýváme rozvojem w-řetězce.
  3. Dva znakové řetězce jsou shodné tehdy a jen tehdy, jestliže jsou stejně dlouhé a na odpovídajících si pozicích mají stejné znaky. Velká a malá písmena se rozlišují.
  4. Dva w-řetězce jsou shodné tehdy a jen tehdy, jestliže pro každý z nich existuje rozvoj do znakového řetězce takový, že získané znakové řetězce jsou shodné podle bodu 3.

Napište funkci matchstring(r1,r2:string):boolean, která jako parametry dostane dva w-řetězce a která vrací hodnotu true, jsou-li tyto w-řetězce shodné; jinak vrátí false.

Příklad:

A = "Nazdar ty*"
B = "Na* ty*"
C = "???ty?ol?"

w-řetězce A a B jsou shodné, A a C nejsou shodné, B a C jsou shodné.