Čtvrtá 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-4-1: Algebrogram
• 4-4-2: Klíče
• 4-4-3: GO
• 4-4-4: Pretty printer

---

4-4-1 Algebrogram

---

Definice:

• <rovnice> je řetězec znaků formátu: <písmena> <znaménko> <písmena> = <písmena>, kde
• <písmena> je řetězec složený ze znaků A, B, C, D, E, F, G, H, I, J
• <znaménko> je jeden ze znaků +, -, *, /.

Řešením rovnice nazveme uspořádanou desetici (a₀,… ,a₉) čísel 0,… , 9 pro kterou platí:

1. a_i ≠ a_j pro i ≠ j
2. pokud za písmena A,… ,J dosadíme ve stejném pořadí zmíněná čísla a₀,… ,a₉, pak rovnice platí.

Řešení soustavy N rovnic je desetice, která je současně řešením každé z N rovnic.

Příklad: Desetice (6,3,0,0,0,0,0,0,0,0) je řešením rovnice A*A=BA.

Úloha: Napište a dokažte program, který načte N rovnic a vytiskne alespoň jedno řešení načtené soustavy.

Poznámka:

1. Pokud řešení neexistuje, tak to program ohlásí.
2. Snažte se, aby program skončil v dohledné době (10! = 3628800)

---

4-4-2 Klíče

---

Všichni jistě víte, jak vypadá klíč. Klíč je popsán celými čísly N, M, L, R a (N+1)-ticí nezáporných celých čísel Y₀, … , Y_N, pro kterou platí:

• Y₀ = L, Y_N = R
• pro všechna i, 0 ≤ i ≤ N je 0 ≤ Y_i ≤ M
• pro všechna i, 1 ≤ i ≤ N je |Y_i - Y_i-1 |≤ 1

Úloha: Navrhněte algoritmus a napište program, který určí počet všech různých klíčů, je-li dáno M, N, L, R.

---

4-4-3 GO

---

Možná někteří znáte japonskou deskovou hru GO. Pro náš příklad budeme trochu modifikovat její pravidla. GO hrají dva hráči, jeden s bílými kameny a druhý s černými, na čtvercové desce o N×N polích. Na začátku hry je deska prázdná. Hráči na ni střídavě pokládají své kameny. Sousední pole na desce jsou ta, která se shodují právě v jedné souřadnici a v druhé se liší právě o 1. Skupina kamenů či kámen je zajat, pokud protihráč položil svůj kámen na poslední volné sousední pole skupiny, tzn. všechna sousední pole skupiny jsou obsazena kameny protihráče. Zajaté kameny se odstraní z desky a ve hře pokračuje druhý hráč.

Poznámka: Volná sousední pole se mohou vyskytovat i uprostřed skupiny kamenů.

Úloha: Napište a dokažte algoritmus a program, který si ze vstupu přečte posloupnost tahů obou hráčů a zobrazí koncový stav kamenů na desce (tzn. provede jednotlivé tahy i s odstraňováním zajatých kamenů z desky).

---

4-4-4 Pretty printer

---

Napište program, který ze standardního vstupu načte zdrojový text programu v Pascalu (můžete předpokládat, že je syntakticky správně) a na standardní výstup pošle „zcivilizovaný“ zápis téhož programu (tzn. zápis v obvyklém tvaru, s odsazením vnořených bloků, deklarací atd.). Nebudeme vám předepisovat, jak má tento „zcivilizovaný“ tvar přesně vypadat, ale předpokládáme, že se budete držet běžných zvyklostí. Co se Pascalu týče, můžete zvolit buď standardní Pascal nebo některý z běžných dialektů (Turbo Pascal, MS Quick Pascal, atd.).

Příklad:Vstup:

program Pretty(input,  output ); var A :  integer; procedure QW;
var A : integer; begin for  A := 1 to  10 do writeln(A ); end;
begin QW; end.

Výstup:

program Pretty(input, output );
var
  A : integer;
procedure QW;
  var
    A : integer;
  begin
    for A := 1 to 10 do
      writeln(A );
  end;
begin
  QW;
end.

Poznámka: Je jasné, že poněkud volné zadání umožňuje vytváření nejroztodivnějších formátů výstupu. Kritériem hodnocení proto tentokrát nebude shoda se zadáním (ani nemůže být), ale přehlednost výstupního textu.

Menu