Třetí série dvanáctého ročníku KSP

Zadání úloh

12-3-1 Strýček Skrblík (9 bodů)

Pan Skrblík se jednoho dne začal zajímat, proč má stále tak zoufale málo peněz. Vzal si tedy své účetnictví a jal se zkoumat, ve kterém období prodělal nejvíce. Po chvilce to ale vzdal, protože záznamů bylo příliš mnoho a rozhodl se, že obětuje tak dva tři centy za program.

Vaším úkolem je tedy program napsat. Na vstupu program dostane počet záznamů a potom jednotlivé záznamy. Každý záznam je vlastně jedno celé číslo. Kladné, pokud pan Skrblík vydělal, záporné, pokud prodělal. Program má zjistit souvislý úsek s minimálním součtem a vypsat jeho počátek a konec.

Řešení

12-3-2 Vypočítavý Robin (11 bodů)

Určitě všichni znáte Robina Hooda. Byl známý tím, že uměl skvěle střílet z luku. Jednoho dne se zamyslel nad příslovím zabít pět much jednou ranou a přišel na to, že on by mohl dělat to samé – jedním šípem zabít co nejvíc nepřátel. A tak se rozhodl to vyzkoušet v praxi. Jednoho dne zastavil v lese skupinu šerifových nejlepších rytířů a hned se dal do experimentování. Protože však neměl k dispozici moderní techniku a rytíři nechápali jeho volání: "Postavte se do řady, posloužíte vědě!" (neboť jim věda byla ukradená), skončil nevalně. Než určil, jak zamířit, rytíři ho zajali. Protože Vy nechcete skončit stejně a máte k dispozici moderní techniku, napište si program, který zjistí, máte-li zadáno souřadnicemi N bodů v rovině, maximální počet bodů ležících v nějaké přímce.

Řešení

12-3-3 Palindromický rozklad (10 bodů)

Mějme řetězec P. Řekneme, že P je palindrom, pokud je stejný při čtení zleva i zprava (např. řetězce "oko" nebo "abcddcba" jsou palindromy). Na vstupu máte daný řetězec S. Zjistěte minimální počet palindromů, na které je možno řetězec rozložit, případně napište, že to nejde.

Příklad:

abcbebe
Řetězec lze rozložit na 3 palindromy.

Řešení

12-3-4 Skákací panák (12 bodů)

Anička si jednoho dne všimla, že na chodník před domem někdo nakreslil skákacího panáka. Není to ale jen tak ledajaký panák, je to stromový panák. Ten vypadá tak, že jsou určena místa, kam se může šlápnout a ta jsou propojena čarami. Skákat se může pouze po těchto čarách. Navíc platí, že mezi každými dvěma místy vede po čarách právě jedna cesta. Aničku zajímalo, jestli dokáže celého panáka obskákat tak, aby na každé místo šlápla právě jednou a přitom se vrátila zase na počátek. Protože je ale Anička ještě malá, nedokáže skočit přes více jak tři čáry.

Vaším úkolem je napsat program, který pro panáka daného počtem míst a spojnicemi mezi nimi, nalezne způsob, jak přeskákat po všech polích, vrátit se zpět a přitom nešlápnout na žádné pole dvakrát (vyjma prvního). Navíc se může skákat pouze přes tři čáry.

Příklad:

Počet polí: 6
Spojnice:
1 2
2 3
3 4
3 5
5 6
Návod:
1, 2, 4, 5, 6, 3, 1

Řešení

12-3-5 PRAM (10 bodů)

Vytvořte program, který jako vstup obdrží posloupnost n celých čísel a určí její maximum. Délka posloupnosti bude při spuštění uložena v gmem[0] a posloupnost sama pak v buňkách gmem[1] až gmem[n]. Obsah paměťových buněk před začátkem výpočtu by tedy například mohl být: 5,4,0,4,-2,3. Program určí největší prvek z této posloupnosti a zapíše jej do buňky gmem[0]. V našem příkladě by do gmem[0] tedy zapsal 4.

Úlohu postupně vyřešte na P-CRCW, CREW a EREW PRAMu.

Řešení