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:

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):

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ů:

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ů.