P1 Vánoční InterLoS 2014
Pro navození správné vánoční atmosféry se začaly v celé losí zemi objevovat následující obrázky betlému:
Obrázek 1: Betlém s právě narozeným Ježíškem Obrázek je losí klasika. Bystří a ostražítí losi (a sobi) zpozorněli, protože obsahoval drobné úpravy, kterým nerozuměli. Ani je moc nepřekvapilo, když se přihlásil jistý vyděrač, který požadoval doslovné splnění svých požadavků předaných skrze výše uvedený obraz. Naštěstí jistý tajný agent Squirlo (známý též pod krycím číslem LOO) získal dostatek materiálů pro dešifrování tajné zprávy. Obrázek je tvořen posloupností polí o rozměrech 30x30 pixelů. V každém poli mají všechny pixely stejnou barvu zadanou vždy formátem RGB. Posloupnost polí začíná v levém horním obrázku a postupuje směrem vpravo po řádcích. Po konci řádku pokračuje o řádek níž zase zleva. Na této posloupnosti polí je zaveden pojem předchozího/následujícího pole, což je takové pole, které bezprostředně předchází/následuje v posloupnosti polí. První pole nemá žádné předchozí pole, poslední pole zase nemá žádné následující pole.1 Tajné informace prozrazují, že v jednotlivých polích jsou zakódovány programové instrukce a celý obrázek je tak vlastně program, který je potřeba interpretovat. Barva pole kóduje instrukci, kam se má přejít dál a to následujícím způsobem: Z každé složky barvy (RGB) se vezme poslední bit2 . Podle následující tabulky zjistíme, kterým směrem máme přejít dál. 1
Obzvláště si uvědomte, že pole na konci řádku má následující pole na začátku dalšího řádku. Taktéž pole na začátku řádku má předcházející pole na konci předchozího řádku. 2 Tedy bit nejmenší hodnoty.
1
P1 Vánoční (pokračování) InterLoS 2014
R 0 0 0 0 1 1 1 1
G 0 0 1 1 0 0 1 1
B 0 1 0 1 0 1 0 1
Instrukce (akce) vpravo vlevo nahoru dolů nahoru vpravo dolů vlevo dolů vpravo nahoru vlevo
Vzdálenost, o kterou se daný skok provede, se zjistí z předchozího pole (existuje-li) a to následovně: • Je-li hodnota červené složky lichá, pak se skočí o G mod 4 + 1, kde G je hodnota zelené složky a mod je zbytek po dělení. • Jinak (tedy i v případě, že předchozí pole neexistuje) se skočí o 1. Poznámka: posun například o jedno pole vpravo na konci řádku způsobí přesun na první pole následujícího řádku atp. Program se začíná interpretovat na prvním poli posloupnosti (tedy v horním levém rohu). Interpretace skončí, když by se mělo skočit na pole, které v posloupnosti neexistuje (tedy takové pole je buď před začátkem nebo za koncem posloupnosti). Tajnou zprávu zjistíte tak, že si do obrázku vykreslíte všechna navštívená pole, která určovala směr skoku (pole, která se použila pouze pro zjištění délka skoku nevykreslujete). Pracujte pouze se souborem P1-encoded.bmp (ne s obrázkem z tohoto PDF)! Řešením je jedno smysluplné slovo. BMP formát3 Pro úplnost následuje popis, jak pracovat s obrázkem v BMP formátu (a nestrávit na tom celého InterLoSa). Při načítání můžete hlavičku BMP souboru ignorovat, což znamená přeskočit 54 bajtů hlavičky4 . Pak už můžete číst jednotlivé pixely jako trojici unsigned charů v pořadí B, G, R. Zrada spočívá v tom, že za hlavičkou následují řádky v opačném pořadí. Jako první budete tedy číst poslední řádek obrázku, ale první pixel zleva (tedy pouze řádky jsou obráceně)5 . Při zápisu nového výstupního obrázku použijte hlavičku původního souboru. 3
Diagram: http://upload.wikimedia.org/wikipedia/commons/c/c4/BMPfileFormat.png Dialog z týmovky: Org 1: „BMP formát je strašně easy, podívej na ten obrázek na Wikipedii.“ Org 2: „Ten BMP formát je strašně komplikovanej, podívej, jak je ten obrázek na Wikipedii dlouhý!“ Org 3: „Já používám Python.“ 4 Prostě fseek(file, 54 * sizeof(unsigned char), SEEK_SET)); 5 V našem konkrétním případě mezi řádky není žádný padding, řádky na sebe ihned navazují.
2
P2 Zrcadla InterLoS 2014
Sob Rudolf je velký záškodník, proto se rozhodl škodit svým sousedům. Využívá svůj svítící nos a důmyslný systém zrcadel, aby jim znepříjemnil život červeným blikáním. Aby sob dokázal škodit svým nosním laserem, musí být co nejrychlejší, proto vždy potřebuje mít systém zrcadel nakonfigurovaný v takové poloze, kudy červený paprsek prolétne nejkratší cestou. Vaší úlohou bude v tomto příkladu pomoci Rudolfovi škodit. Mějme Rudolfa na pozici (0, 0) natočeného ve směru (0, 1). V neohraničené nekonečné ploše kolem Rudolfa se nacházejí náhodně rozmístěná zrcadla, která můžete natáčet do dvou poloh označených písmeny A a B (viz obrázek). Vaší úlohou je správně natočit zrcadla tak, aby Rudolf mohl nosem trefit souseda na pozici (42, 0).
Poloha A
Poloha B
Laser se od zrcadel vždy odráží pod stejným úhlem, v jakém dopadá. Zrcadla jsou oboustranná, tedy odráží paprsek na obou svých stranách. Seznam zrcadel najdete v přiloženém souboru P 2 − input.txt, kde na každém řádku je definovaná pozice zrcadla ve tvaru souřadniceX souřadniceY . Pro ilustraci odrážení viz příklad:
Jako výsledné heslo odevzdejte nejkratší sekvenci písmen natočení zrcadel v pořadí, v jakém se od nich laser odráží (v příkladu by bylo řešení sekvence – BA). V případě vícero cest stejné délky odevzdejte lexikograficky nejmenší řešení.
3
P3 CalcuLoS InterLoS 2014
Nález Sobránských svitků u Zamrzlého moře vyvolal již před necelými šedesáti lety mezi losí (i sobí) populací pořádný poprask. . . konečně nějaké písemnosti z rané losí civilizace. Jaké bylo jejich zklamání, když zjistili, že jim prakticky vůbec nerozumí, a že budou muset vynaložit velké úsilí, aby zjistili byť pouhý překlad do moderního dialektu. Jeden z nejstarších svitků náboženství S˚ yi byl složen pouze z písmen INTERLOS. Přičemž dnešní, losům srozumitelný jazyk používá pouze písmena LOS. Po desetiletích bádání dospěly největší vědecké kapacity v čele s profesorem Soozem k tomu, že znaky INTER jsou operátory a umožňují transformovat písmena za nimi na jiné (a důmyslně tak skrývat pravý obsah svitku). Pomocí zkoumání krátkých útržků se jim podařilo odhalit význam jednotlivých operátorů. Potřebují však pomoci s převodem celého svitku, na kopytovou práci je příliš dlouhý. Operátory: M = {I, N, T, E, R} Hodnoty: H = {L, O, S} Operátor I
Operátor N
Typ: H × H → H (Bere dvě hodnoty a vrací jednu)
Typ: H × H → H (Bere dvě hodnoty a vrací jednu)
Je definován I L O L L L O L O S L S
Je definován následovně: N L O S L L O S O O S L S S L O
následovně: S L S O
Operátor E Operátor T
Typ: H × H → H × H (Bere dvě hodnoty a vrací dvě hodnoty)
Typ: H → H (Bere jednu hodnotu a vrací jednu)
Je definován následovně: E x y → y x pro všechny x,y z H
Je definován následovně: T L S O O S L
Operátor R Typ: H → H × H (Bere jednu hodnotu a vrací dvě hodnoty) Je definován následovně: R x → x x pro všechny x z H
4
P3 CalcuLoS (pokračování) InterLoS 2014
Způsob vyhodnocování Celý text je zadán jako lineární posloupnost jednotlivých symbolů (například LOSOSOL). Čtení (vyhodnocování) se provádí zleva: • je-li nalezena hodnota, přeskočí se, pokračuje se dále směrem vpravo, • je-li nalezen operátor, vyhodnotí se za použití argumentů, které ihned následují. Přitom ale může dojít k situaci, že tyto argumenty nejsou hodnotami, ale operátory, pak se musí vyhodnotit nejdříve tyto argumenty.
Příklad LINLRETOS LINLREOS LINLRSO LINLSSO LISSO LOO
Nejprve musíme vyhodnotit T na O → O Pak musíme vyhodnotit E na O a S → SO Následně musíme vyhodnotit R na S → S S Poté musíme vyhodnotit N na L a S → S A nakonec musíme vyhodnotit I na S a S → O Výsledek.
Zadání a odevzdání Celý text zadání naleznete v souboru P3-svitek.txt. Jako řešení odevzdávejte zpracovaný řetězec (v příkladu nahoře by to bylo LOO).
5
L1 Losí spirálové město InterLoS 2014
Zjistěte v plánu losího města polohu 16 budov uvedených na další straně. Žádné dvě budovy přímo nesousedí, ani se nedotýkají rohy. Budovy mohou být libovolně otočené. Domy čísloval opilý projektant, který se městem motal po naznačené spirále z vnějšku doprostřed a každý dílek budovy, který potkal, očísloval, postupně čísly 1 až 40. Součet čísel na dílcích v každém řádku i sloupci je uveden. Navíc je město vstřícné k losím procházkám. To znamená, že všechna políčka neobsazená budovami propojuje jediná uzavřená pěšinka, která prochází vodorovně či svisle mezi středy sousedních políček a každé políčko navštíví přesně jednou, než se vrátí odkud vyšla. Níže je uvedený příklad řešení stejného problému v menším měřítku. Jako výsledné heslo zapište všechna čísla z vilek seřazená podle velikosti za sebe bez mezer.
1×
3
1
4
4
2
3 4
0
1×
0
3
3 5
2
0
3
5
6
2
0
3
3
L1 Losí spirálové město (pokračování)
InterLoS 2014
6 54 16 98 134 72 45 88 117 90 66 34 24 84 31 134 69 14 159 29 94 106 51 25 Kostel
Škola
Obchod Muzeum Panelák Vilka
2× 1×
1×
7
1×
6×
5×
L2 Švédská křížovka InterLoS 2014
1. Točená křížovka:
2. Označkovaná křížovka:
8
L2 Švédska křížovka (pokračování) InterLoS 2014
3. Švédská křížovka:
Použijte dílky pro vyluštění křížovek. Můžete je libovolně otáčet, ale nepřeklápět.
9
L3 Příjmenná úloha InterLoS 2014
(x ˅ ¬x) (x ˅ y) ˄ ¬x ˄ ¬y x ˄ ¬x y ↔ ¬y →(x ˄ ¬x) ¬x ˄ ¬y
00 01 10 11 ¬(x ↔ y)
y
x˅ (y ↔ ¬y)
x
¬(¬x ˄ ¬y)
(x ˅ y)˄ (x ˅ ¬y)˄ (¬x ˅ y)˄ (¬x ˅ ¬y)
(x ˄ ¬y) x˄y ˅ (x ˄ y) y→x
¬y
x˄ x ˄ (x ˄ ¬y) ¬(x ˄ y) ˄ (x ˄ y) ˄ ¬(¬x ˄ y) ˄ (¬x ˄ ¬y) (y ˅ ¬y) (y x)˅ (x ˄ y) ¬(x ˄ ¬y)
(¬x ↔ y) ¬(x ˅ y) (x ˄ ¬x) ˅ (x ˄ y) y ˄ ¬y (y ↔ ¬y) ˄y ˄ ¬y ˄x
10
S1 OEIE InterLoS 2014
1,2,3,4 5 6,2,3,7 3,1,2 8,9,10. OEIE ae aoí ee U aie 10íě 1,2áo, a a ieo. „oe i e5 ou 7áo, y i6áě, eo! o9ee o oa4,8eí, áa ie 3ooy: a ě ae u aeí o ee, 2y oo, y!
S2 Máte jednu dvě pět novou zprávu InterLoS 2014
Byl jeden král a ten měl sto dvacet šest dcer. Jeden policista pokutoval dva výtržníky. Jeden kněz, jeden rabín a jeden pastafarián vtípkovali. Čtyři jeptišky vyrušovaly jednu abatyši. Pět vojáků sestřelilo šest broskví třemi vlašáky. Nula lidí se dostavilo do jedné maringotky. Jeden sněhulák má jednu hlavu. Čeština používá tři plurálové formy. Šest paradoxů dvou mušketýrů. Devět malých černoušků má jednu maminku. Slovenština má též tři plurálové formy. Jeden knedlík na devatenáct jedlíků. Dva kroky od jedné propasti. Jeden den v životě. Jeden pecen, dva litry mléka a jedno máslo. Šest set preclíků plus dvaaosmdesát preclíků je hodně. Angličtina má dvě plurálové formy – což vám s touto šifrou nepomůže. Tamto stádo má nula krav. Jedna tečka za touhle podivností.
S3 Losí Moonwalk InterLoS 2014
Zadání úlohy najdete v přiloženém souboru S3-video.avi.
11
