Třetí série desátého ročníku KSP

Zadání úloh

10-3-1 Domečkologie (10 bodů)

Ano, jak jste již zaručeně uhodli podle názvu úlohy, opravdu půjde o kreslení domečků jedním tahem. Ale nikoliv jen onoho zprofanovaného domečku z osmi čar, nýbrž domečku obecného: je dáno N bodů v rovině svými souřadnicemi (x1,y1), …, (xN,yN) a M hran (pro každou víte čísla dvou vrcholů, které spojuje, na pořadí nezáleží).

Napište program, jenž nalezne jednotahové nakreslení zadaného domečku (tedy vlastně posloupnost vrcholů takovou, že půjdete-li přes ně v určeném pořadí, nakreslíte každou hranu právě jednou) či odpoví, že domeček nelze jedním tahem nakreslit.

Řešení

10-3-2 Sirky jsou vrženy (11 bodů)

V casinu v Las Miseras hráli podivuhodnou hru pro dva hráče: na stole ležely dvě hromádky zápalek, na počátku na každé z nich leželo N zápalek. V každém tahu mohl jeden z hráčů odebrat k zápalek buďto z první nebo z druhé hromádky, případně stejný počet z obou. Hráči se pravidelně střídali, prohrál ten, který již nic odebrat nemohl.

Navrhněte strategii pro tuto hru a vytvořte program, který ji s vámi (tedy spíše proti vám) bude hrát.

Řešení

10-3-3 Lloydova devítka (10 bodů)

Mějme čtvercovou krabičku rozdělenou na 3×3 políčka, na něž jsou rozmístěny hrací kameny s čísly od jedné do osmi (každý je tam právě jednou) a jedno políčko je volné. V každém tahu můžete posunout na volné políčko libovolný z kamenů, které s ním sousedí. Cílem je dosáhnout konfigurace

1 2 3
4 5 6
7 8 .

Napište program, který vymyslí nejkratší posloupnost tahů vedoucí z konfigurace zadané k cílové, případně sdělí, že to nejde.

Řešení

10-3-4 Hic sunt leones (10 bodů)

Představte si, že vám někdo zadal konvexní mnohoúhelník v rovině souřadnicemi jeho vrcholů

(x1,y1), … , (xn,yn)

přesně v tom pořadí, jak jsou spojeny hranami (hrany tedy vedou vždy z i-tého do (i+1)-ního vrcholu a pak z n-tého do prvního) a vy máte o daném bodě (x,y) rozhodnout, leží-li uvnitř nebo vně tohoto mnohoúhelníka (hranice je také uvnitř).

Zkuste napsat co nejrychlejší program, který to zjistí (předpokládejte, že pro jeden mnohoúhelník budete testovat velké množství bodů, takže klidně můžete trávit nějaký čas předpočítáváním pomocných dat, jen když pak bude vyhledávání co nejrychlejší).

Řešení

10-3-5 Terucempa (10 bodů)

V jedné jeskyni žilo 12 trpaslíků (Arnošt, Břéťa, Cecil, David, Eda, Filip, Gustav, Horymír, Ivan, Janek, Kája a Luděk) a každé ráno hned po rozednění vylezli do nedaleké soutěsky umýt se v potoce. Leč soutěska byla úzká, a tak museli stát ve frontě. Jelikož to byli trpaslíci vzdělaní a ne nějací permoníci mdlého rozumu, domluvili se, že každé ráno budou čekat v pořadí jiném, aby nikdo z nich nebyl ve výhodě proti ostatním.

Když přemýšleli, jak to zařídit, Cecila napadlo, že to vezmou systematicky: každé své pořadí (odborně řečeno permutaci, okamžitě dodal Arnošt) si zapíší jako jedno slovo z písmenek A až L (ejhle, to máme ale šikovná jména, napadlo Janka) a vezmou ta slova podle abecedy – první den to první (ABCDEFGH), druhého druhé (ABCDEFHG) až někdy v budoucnosti (pamatujte, že trpaslíci jsou dlouhověcí, přidal se k rozhovoru Ivan) poslední (HGFEDCBA) a pak zase od začátku.

Na vás je, abyste napsali program odpovídající na otázku, v jakém pořadí stáli trpaslíci ve frontě N-tého dne.

Řešení