Třetí série druhé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


2-3-1 Agent 007


Napište program, který k zadanému kladnému celému číslu N vytiskne nějaké kladné celé číslo M takové, že

  1. M je dělitelné číslem N
  2. Desítkový zápis M obsahuje pouze nuly a sedmičky.

Příklad: Pro N=9 program může vytisknout třeba číslo 777777777.


2-3-2 Součtová posloupnost II.


Posloupnost kladných celých čísel nazveme součtovou, jestliže začíná číslem 1 a každý další její člen lze vyjádřit jako součet dvou čísel takových, že se v posloupnosti vyskytla před tímto členem. Například posloupnost 1 2 4 5 3 je součtová, neboť 2=1+1, 4=2+2, 5=1+4 a 3=1+2.

Napište program, který pro zadané kladné celé číslo N vypíše nějakou nejkratší součtovou posloupnost obsahující číslo N. Např. pro N=15 program může vytisknout třeba 1 2 3 5 10 15.

Poznámka: Všimněte si příbuznosti s úlohou spočítat n-tou mocninu co nejmenším počtem násobení.


2-3-3 Zplodiny


Nechť S je řetězec znaků. Zplodinovými operacemi nazveme následující změny řetězce S:

  1. odtržení prvního, resp. posledního znaku neprázdného řetězce S
  2. přidání libovolného znaku na začátek, resp. na konec řetězce S
  3. změna jednoho znaku řetězce S na libovolný znak.

Napište program, který načte ze vstupu řetězce znaků S a Z a vypíše minimální počet zplodinových operací potřebný ke změně S na Z.

Příklad: Pro řetězce S=AXIIYJZB a Z=ADXKKYLZ program vytiskne 6, neboť nejkratší změna S na Z pomocí zplodinových operací je AXIIYJZBDXIIYJZBADXIIYJZBADXKIYJZBADXKKYJZBADXKKYLZBADXKKYLZ.


2-3-4 Wokna


Napište správce woken (window manager), což je soubor podprogramů pro otevírání, zavírání a zápis textových oken na obrazovce počítače. Řádky obrazovky číslujeme shora dolů od nuly, sloupce zleva doprava od nuly. Konstantou VysObr resp. SirObr označme skutečnou výšku resp. šířku obrazovky (udanou ve znacích). Wokno je virtuální textová obrazovka. Je určeno následujícími údaji:

  • (HoRadek,LeSloupec) – pozice levého horního rohu okna na fyzické obrazovce
  • Vyska, Sirka ≥ 1 – výška resp. šířka wokna (ve znacích)
  • (WRadek,WSloupec) – aktuální pozice tisku vztažená k levému hornímu rohu wokna (0≤ VyskaWRadek, 0≤ SirkaWSloupec).
Správce woken obsahuje tyto podprogramy (anglické názvy jsou natolik zavedené, že nepokládáme za vhodné překládat je do češtiny):
  • WInit – inicializace správce woken. Vyprázdní seznam woken a otevře tzv. podkladové wokno voláním WOpen(0,0,VysObr,SirObr), tj. wokno „přes celou obrazovku“.
  • WOpen(HoRadek,LeSloupec,Vyska,Sirka:integer) – otevře dané wokno: přidá na začátek seznamu woken údaje o novém woknu, jehož levý horní roh je na pozici (HoRadek,LeSloupec) a jehož výška a šířka jsou Vyska, Sirka ≥ 1, aktuální pozice tisku je (0,0). Smaže, tj. naplní mezerami, na obrazovce oblast určenou tímto woknem. Wokno na začátku seznamu woken nazveme aktuálním woknem.
  • WClose – zavře aktuální wokno: obnoví původní obsah obrazovky, který byl těsně před otevřením aktuálního wokna podprogramem WOpen (za předpokladu, že všechny zápisy do obrazovky byly prováděny podprogramem WWrite) a odstraní aktuální wokno ze seznamu woken. Je-li však aktuálním woknem podkladové wokno, pouze vrátí informaci o chybě.
  • WGotoXY(Radek,Sloupec:integer) – nastaví aktuální pozici tisku aktuálního wokna (tj. kam bude tisknout příští WWrite) na pozici (Radek,Sloupec).
  • WWrite(Znak:char) – vytiskne Znak na aktuální pozici tisku aktuálního wokna. Je-li levý horní roh (HoRadek,LeSloupec) a aktuální pozice tisku aktuálního wokna (WRadek,WSloupec), vytiskne se Znak na pozici (HoRadek+WRadek, )LeSloupec+WSloupec na obrazovce. Poté nastaví aktuální pozici tisku na další znak v aktuálním wokně.

Abychom potlačili závislost na konkrétní implementaci výstupu na obrazovku ve vašem systému a vytvořili pro všechny stejné podmínky, uvalíme na vás následující omezení: Veškerá práce s obrazovkou ve vašem řešení musí probíhat prostřednictvím těchto podprogramů:

  • Cls – smaže obrazovku
  • GotoXY(Radek,Sloupec:integer) – nastaví pozici tisku, tj. kam bude tisknout příští Write, na (Radek,Sloupec)
  • Write(Znak:char) – vytiskne Znak na pozici za naposledy vytisknutým znakem, resp. na pozici určenou v GotoXY.
  • Screen(Radek,Sloupec:integer;var Znak:char) – v proměnné Znak vrátí znak, který je na obrazovce na pozici (Radek,Sloupec).
Nezajímá nás, jak si tyto podprogramy uděláte (nejsou součástí řešení), musíte však dodržet pojmenování a strukturu parametrů.