Druhá série třicátého sedmého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Dostává se k vám druhé číslo hlavní kategorie 37. ročníku KSP.
Letos se můžete těšit v každé z pěti sérií hlavní kategorie na 4 normální úlohy, z toho alespoň jednu praktickou opendatovou. Dále na kuchařky obsahující nějaká zajímavá informatická témata, hodící se k úlohám dané série. Občas se nám také objeví bonusová X-ková úloha, za kterou lze získat X-kové body. Kromě toho bude součástí sérií seriál, jehož díly mohou vycházet samostatně.
Autorská řešení úloh budeme vystavovat hned po skončení série. Pokud nás pak při opravování napadnou nějaké komentáře k řešením od vás, zveřejníme je dodatečně.
Odměny & na Matfyz bez přijímaček
Za úspěšné řešení KSP můžete být přijati na MFF UK bez přijímacích zkoušek. Úspěšným řešitelem se stává ten, kdo získá za celý ročník (hlavní kategorie) alespoň 50 % bodů. Za letošní rok půjde získat maximálně 300 bodů, takže hranice pro úspěšné řešitele je 150. Maturanti pozor, pokud chcete prominutí využít letos, musíte to stihnout do konce čtvrté série, pátá už bude moc pozdě. Také každému řešiteli, který v tomto ročníku z každé série dostane alespoň 5 bodů, darujeme KSP propisku, blok, nálepku na notebook a možná i další překvapení.- Termín série: neděle 15. prosince 2024 ve 32:00 (tedy další ráno v 8:00)
- Odevzdávání: elektronicky přes Odevzdávátko
- Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
- Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.
- Odměna série: Odznáček do profilu na webu si vyslouží ten, kdo ho najde v HTTP bludišti.
Zadání úloh
- 37-2-1: Urychlovač částic
- 37-2-2: Pohoří plné jezer
- 37-2-3: Chov ovcí
- 37-2-4: HTTP bludiště
- 37-2-S: Lexery útočí
- 37-2-X1: Intervalové většiny
37-2-1 Urychlovač částic (10 bodů)
Sára připravuje demonstraci na den otevřených dveří v urychlovači částic. Ráda by návštěvníkům předvedla, jak je možné v urychlovači jeden prvek přeměnit v druhý. Sára během svého výzkumu našla N funkčních nastavení urychlovače, které pro přehlednost očíslovala od 1 do N. Každé z nich dokáže z jednoho specifického prvku vyrobit jiný specifický prvek.
Při přeměně urychlovač různě svítí, bliká a hučí. Sára proto každé nastavení ohodnotila kladným, celým číslem, které nazývá úžasnost. Úžasnost jednoduše vyjadřuje, jak moc se bude daná přeměna návštěvníkům líbit. Návštěvníci nemají až tak dobrou paměť, nevadí jim jednu přeměnu vidět vícekrát.
Během demonstrace bude Sára mít čas na přesně K přeměn. Navíc nebude čas na to, aby v urychlovači vyměňovala vzorky, takže na sebe přeměny budou muset navazovat. Na začátku demonstrace do urychlovače načerpá vodík, kterého mají v ústavu hodně. Chtěla by, aby na konec v urychlovači zbylo hélium, které dětem plánuje napustit do balónků.
Ráda by přeměny naplánovala tak, aby součet jejich úžasnosti byl co největší. Pomůžete jí?
Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.
Formát vstupu: Na prvním řádku dostane tři čísla P, N a K: protonové číslo nejtěžšího prvku, se kterým umí urychlovač pracovat, počet nastavení urychlovače a počet přeměn, na které má Sára čas. Na každém z dalších N řádků bude popsáno jedno nastavení pomocí tří čísel ai, vi a ui: protonové číslo prvku, který musí být v urychlovači před přeměnou, protonové číslo prvku, který v něm zůstane po přeměně, a úžasnost této přeměny.
Vodík má protonové číslo 1, hélium 2.
Formát výstupu: Vypište K řádků, na i-tém číslo i-tého použitého nastavení urychlovače.
3 4 2 1 2 100 1 3 10 3 2 20 3 2 50
2 4
Vysvětlení ukázkového vstupu: První nastavení sice vypadá lákavě, ale po jeho provedení bychom už nemohli provést žádnou druhou přeměnu. Proto nám nezbývá než nejprve vyrobit lithium pomocí druhého nastavení. Udělat z lithia helium umí dvě různá nastavení, nejvyšší úžasnost má to s číslem čtyři.
37-2-2 Pohoří plné jezer (11 bodů)
Kevin má spousty snů a jeden z nich je objevit všechny divy světa. Tak si počkal na prodloužený víkend a naplánoval si výlet na bájné Jezerní pohoří. Jezerní pohoří je známé pro svůj nekončící déšť, který se v slunečním svitu leskne jako perličky. Ale hlavní půvab této oblasti jsou všechna nejrůznější údolí, ve kterých se tvoří jezera.
Bylo potřeba spoustu příprav. Kevin si s sebou vzal pláštěnku, deštník a ještě k tomu nepromokavé oblečení a po dlouhé túře tam konečně dorazil. Bohužel si Kevin nepřečetl dodatečnou informaci, že všechna jezera vysychají mimo sezónu, takže místo překrásných jezer měl před sebou jen nejrůznější prázdná údolí. Kevin si tohle nenechal líbit a rozhodl se, že naplní všechna jezera sám, a aby z toho měl pořádný zážitek, tak je všechny naplní na maximum.
Pohoří si můžeme představit jako mřížku R×S, kde každé políčko má zadanou výšku. Naším úkolem je zjistit, kolik nejvíce vody může celá krajina zadržet. (Jednotku vody můžeme změřit jako zatopení políčka na hladinu o jedna vyšší než jeho výška). Vlivem unikátního reliéfu teče voda pouze směry nahoru, dolů, doleva a doprava. Z krajních políček steče všechna voda do nížin a nedrží se tam. Tedy voda se udrží v nějakém políčku pouze v případě, kdy nedokáže nějakou cestou přetéct přes okraj pohoří.
Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.
Formát vstupu: Na prvním řádku dostanete dvě čísla R a S: počet řádků a počet sloupců v mřížce pohoří. Na každém z dalších R řádků bude S čísel oddělených mezerou označujících výšky políček. Výška políčka je nezáporné číslo, které se vejde do 32-bitového integeru.
Formát výstupu: Výstupem je jediné číslo: počet jednotek vody, které jsou potřeba, aby se naplnila všechny jezera. Pozor, výsledek se nemusí vejít do 32-bitového integeru.
5 5 0 3 6 6 7 2 2 0 1 3 3 6 6 5 7 6 3 0 7 4 5 6 8 3 5
12
Vysvětlení ukázkového vstupu: Ve vstupu si můžeme všimnout dvou oblastí, ve kterých nevyteče voda z pohoří ven. První z nich se nachází na pozicích (1, 2) a (1, 3), kde jsou hodnoty nula a jedna. Výška hladiny této oblasti bude dvě, protože jakékoliv větší množství vody přeteče přes políčka (1, 1) a (1, 0) mimo pohoří. Podobnou úvahu provedeme pro oblast na pozicích (3, 1) a (3, 2), které je obklopené políčky, které přetečou až nad výškou šest. Ve finále jsme pro naplnění potřebovali dvanáct jednotek vody (0 →2, 1 →2, 3 →6, 0 →6).
Pro lepší představu tu máme obrázek zpracovaného vstupu. Šedá políčka znázorňují políčka, která zůstala bez vody a modrá políčka mají vlevo nahoře jejich původní výšku a vpravo dole hladinu vody, kterou udrží.
37-2-3 Chov ovcí (12 bodů)
Ríša se rozhodl skončit s programováním a dát se na chov ovcí. Přestěhoval se na Balkán, koupil si kus půdy a začal zkoumat, jak se ovce chovají. Na důvěryhodném zdroji se dozvěděl, že nejlepší je ovcím vyhradit čtvercový výběh s K keři. Koupil si ale celkem rozlehlý kus půdy, a tak se ptá vás, jestli byste mu správný výběh našli?
Pro N bodů v rovině najděte čtverec o velikosti A×A zarovnaný s osami, ve kterém je právě K bodů. (Nebo řekněte, že neexistuje.) Můžete předpokládat, že K ≪ N (K je řádově menší než N).
Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.
37-2-4 HTTP bludiště (12 bodů)
Vítejte v bludišti! To naše se ukrývá uvnitř webového serveru. Komunikujete s ním po síti protokolem HTTP, jehož popis najdete v kuchařce této série. Vaším cílem je najít klíč – to je nějaký 16-znakový řetězec.
Bludiště má několik částí, které se chovají jako testy open-data úlohy. Když si necháte vygenerovat vstup, dozvíte se URL vchodu do bludiště. Jako výstup pak odevzdáte klíč. Na nalezení klíče máte hodinu, pak si musíte vygenerovat nový vchod.
Pečlivě sledujte, co vám server posílá, a zkoumejte i slepé uličky. Třeba se v nich dozvíte něco, co se bude později hodit.
37-2-X1 Intervalové většiny (10 bodů)
Toto je bonusová úloha pro zkušenější řešitele, těžší než ostatní úlohy v této sérii. Nezískáte za ni klasické body, nýbrž dobrý pocit, že jste zdolali něco výjimečného. Kromě toho za správné řešení dostanete speciální odměnu a body se vám započítají do samostatných výsledků KSP-X.
Kevin se v poslední době začal zajímat o kompresi obrázků a dokonce si již navrhl svůj vlastní algoritmus.
Je však aktuálně příliš pomalý. V jeho průběhu totiž Kevin potřebuje opakovaně pro různé úseky obrázku rychle zjistit, zda v něm má nějaká barva nadpoloviční většinu a to Kevin neumí lépe, než průchodem celého úseku.
Hodila by se mu proto nějaká datová struktura, která by zvládla pro zadaný úsek obrázku rychle odpovědět, zda v něm má nějaká barva nadpoloviční většinu a případnou barvu vrátit.
To bude úkol pro vás.
Na vstupu dostanete obrázek. Ten má pro jednoduchost jen jeden řádek a lze si jej představit jako posloupnost barev. Každá taková barva je v posloupnosti reprezentována jako celé číslo. Upozorňujeme, že čísla barev mohou být poměrně vysoká, takže nemusí být například dobrý nápad s nimi indexovat pole.
Váš program nejprve na základě této posloupnosti postaví potřebnou datovou strukturu. Následně s její pomocí začne vyřizovat příchozí dotazy na jednotlivé úseky posloupnosti. Nelze předpokládat, že je program obdrží najednou, takže musí být schopen na dotazy odpovídat online.
Tím nicméně Kevinovy požadavky nekončí. Je nezbytné, aby výsledná datová struktura vyřizovala jednotlivé dotazy v čase O(1). Vaše řešení tak budeme posuzovat výhradně podle času stráveného předvýpočtem. Ten by se měl v ideálním případě vejít do O(N log c N), kde N je délka posloupnosti a c nějaká konstanta.
37-2-S Lexery útočí (15 bodů)
Letošním ročníkem vás bude provázet seriál. V každé sérii se objeví jeden díl, který bude obsahovat nějaké povídání a navíc úkoly. Za úkoly budete moci získávat body podobně jako za klasické úlohy série. Abyste se mohli zapojit i během ročníku, seriál bude možné odevzdávat i po termínu za snížený počet bodů. Vzorové řešení seriálu proto před koncem celého ročníku KSP uvidí jen ti, kdo už seriál odevzdali.
Lexery útočí
V dnešním díle se vrhneme na sestrojení první analýzy zdrojového kódu – konkrétně lexikální analýzy. Lexikální analýza se provádí v části překladače, které se říká lexer nebo scanner. Jejím úkolem je vzít text, který napsal programátor jako pole znaků, a pospojovat znaky, které spolu patří, do skupinek nazývaných tokeny. Jeden token může reprezentovat nějaké slovo jazyka nebo interpunkci.
Lexer je relativně jednoduchá část překladače. V dnešní době existují šikovné nástroje, které dokážou vygenerovat kvalitní lexer z deklarativního popisu jazyka, ale cílem našeho seriálu je ukázat si, jak tyto věci uvnitř fungují, takže si lexer napíšeme sami.
Příklad tokenu může být PLUS
pro operátor +
, FOR
pro
klíčkové slovo for
nebo GREATER_EQUAL
pro operátor >=
.
Některé tokeny jsou ale složitější. Například budeme mít token pro jména
proměnných nebo pro číselné konstanty použité v programu. Oba tyto typy tokenů
si budou muset pamatovat znaky, ze kterých jsme je vytvořili, abychom později
dokázali rekonstruovat hodnotu čísla nebo jméno proměnné.
Typy tokenů si zapíšeme jako enum
:
enum TokenType {
// Operátory
TK_NOT, TK_EQUAL, TK_GREATER, TK_LESS, TK_MINUS,
TK_PLUS, TK_SEMICOLON, TK_SLASH, TK_STAR,
TK_NOT_EQUAL, TK_EQUAL_EQUAL, TK_GREATER_EQUAL,
TK_LESS_EQUAL, TK_LBRACE, TK_LPAREN, TK_RBRACE,
TK_RPAREN,
// Klíčová slova
TK_ELSE, TK_FOR, TK_IF, TK_PRINT, TK_VAR,
TK_WHILE,
// literály
TK_NAME, TK_NUMBER,
};
Tokeny TK_NAME
a TK_NUMBER
si zároveň musí pamatovat znaky, ze kterých jsme
tento token vytvořili. Proto tento enum zabalíme do malého struct
u.
struct Token {
TokenType type;
// pouze u TK_NAME a TK_NUMBER, jinak ""
std::string value;
Token(TokenType t, std::string v = "")
: type{t}, value{v} {}
};
Tokeny chceme umět vypisovat do konzole, takže si hned napíšeme jednoduchou
funkci, která převede TokenType
na std::string
:
std::string token_type_to_str(TokenType t) {
switch (t) {
case TK_ELSE: return "ELSE";
case TK_EQUAL: return "EQ";
case TK_EQUAL_EQUAL: return "EQUAL_EQUAL";
...
case TK_WHILE: return "WHILE";
}
return "<invalid token value>";
}
Jeden tokenizovaný řádek bychom pak mohli takto vypsat:
var a = 33+2;
VAR NAME(a) EQ NUMBER(33) PLUS NUMBER(2) SEMICOLON
Všimněte si, že pole tokenů nedrží informace o mezerách mezi tokeny.
Dospělé lexery si zachovávají více informací, jako třeba lokaci ve zdrojovém textu, ze které každý token pochází. To se pak používá pro generování přesnějších chybových hlášek, ale přichází se zajímavým problémem: lokace zdroje každého tokenu nafoukne velikost každého tokenu, i když se zdrojová lokace každého tokenu jistě nepoužije. Řešení je například ukládat si lokace pouze každého N-tého tokenu a až při generování chybových hlášek znovu tokenizovat zdrojový kód pro spočítání přesné lokace potřebného tokenu. To sice znamená, že musíme nějaké informace zbytečně počítat znovu, ale ušetřená paměť nám celkový proces zrychlí.
Pro lexování se nám bude hodit pomocná struktura Scanner
. Obsahuje
jednoduchou abstrakci nad procházením pole znaků. Nejdůležitější je funkce
match
, která otestuje, jestli je daný znak první na vstupu, a pokud ano,
přesune se přes něj a vrátí true
, jinak vrátí false
.
#include <cctype>
#include <iostream>
#include <optional>
#include <string>
#include <vector>
struct Scanner {
std::string source;
Scanner(std::string s) : source{s} {}
void advance(size_t i = 1) { source.erase(0, i); }
bool is_at_end() { return source.empty(); }
char peek() {
return source.empty() ? '\0' : source[0];
}
bool match(char c) {
if (peek() == c) {
advance();
return true;
}
return false;
}
};
std::vector<Token> lex(std::string source) {
Scanner sc = Scanner(source);
std::vector<Token> ts;
while (true) {
auto t = lex_one(sc);
if (!t.has_value()) { break; }
ts.push_back(t.value());
}
return ts;
}
int main() {
std::string source = "var a = 33+2;";
std::vector<Token> ts = lex(source);
for (auto t : ts) {
std::cout << token_type_to_str(t.type) << "("
<< t.value << ") ";
}
std::cout << '\n';
}
Tohle je další běžný tvar programu, který člověk najde v překladačích. Máme
(budeme mít) funkci lex_one
, která se podívá na prvních několik znaků vstupu,
které jsme ještě nepřečetli, a usoudí, jaký token se na tomto místě nachází.
Tento token nám vrátí a přesune se ve vstupu přes tento token. Pokud chceme
tokenizovat celý vstup, stačí nám opakovaně volat tuto funkci, dokud nám
neoznámí, že jsme dorazili na konec souboru.
Klasický design překladače volá tuto funkci líně. Až když je příští krok
v překladu plně hotový s procesováním aktuálního tokenu, si překladač řekne
o další token, který opět ihned předhodí dál a čeká, dokud se plně nezpracuje.
Tohle rozhodnutí plynulo z omezení tehdejších počítačů, které měly problém
načíst celý zdrojový kód do paměti! To ale rozhodně není naše situace, takže si
vyrobíme pole pro naše tokeny a všechny si je tam vesele nastrkáme. Zpátky
k lex_one
.
První věc, kterou musí lex_one
udělat, je přeskočit bílé znaky jako třeba
mezery, tabulátory a zalomení řádku:
std::optional<Token> lex_one(Scanner &sc) {
// přeskoč whitespace
while (std::isspace(sc.peek())) {
sc.advance();
}
...?
}
Dalším úkolem je rozpoznat 3 skupiny tokenů: operátory (+
, {
, ...), čísla a
jména. Nejjednodušší je rozpoznávat operátory, takže s tím i začneme. Vyrobíme
si na ně vlastní funkci:
std::optional<Token>
match_operator_token(Scanner &sc) {
Pro rozpoznávání jednoznakových operátorů stačí použít funkci match
:
if (sc.match('(')) return TK_LPAREN;
Dvouznakové operátory jsou trochu složitější. Když na začátku vstupu vidíme
znak <
, nestačí pouze oznámit TK_LESS
a posunout se dál. Může se totiž stát, že
hned další znak je =
a správný token je TK_LESS_EQUAL
.
if (sc.match('<')) {
if (sc.match('=')) {
return TK_LESS_EQUAL;
} else {
return TK_LESS;
}
}
Pokud žádný operátor nenajdeme, vrátíme z funkce null:
return std::nullopt;
}
Úkol 1 – Operátory [3b]
Váš první úkol je dopsat funkci match_operator_token
. Můžete použít naše
kousky kódu, které jsme vám právě ukázali.
Po tomto úkolu stačí zavolat funkci match_operator_token
z lex_one
,
a pokud nevrátí std::nullopt
, tak máme hotovo a vrátíme tento token.
Jinak se musíme zeptat další pomocné funkce, což bude match_digit_token
.
Funkce match_digit_token
funguje velmi podobně jako funkce
match_operator_token
. Důležitá vlastnost všech těchto pomocných funkcí je,
že nekonzumují žádný vstup, dokud si nejsou jisté, že na vstupu je skutečně
token, který rozpoznávají.
Úkol 2 – Čísla [4b]
Druhý úkol spočívá v napsání funkce match_digit_token
. Ta by měla
zkontrolovat, zda na začátku vstupu je číslo, a pokud ano, celé ho přeskočit.
Zároveň si ale musí toto číslo uložit uvnitř tokenu, který pak vrátí. Později
budeme potřebovat převést toto číslo na jeho hodnotu. Nebudeme řešit +
ani -
před číslem. Pro -
máme (budeme mít) unární mínus operátor,
a unární plus operátor nebudeme potřebovat.
Pokud ani match_digit_token
nic nevrátí, pak poslední možnost je, že na
vstupu je jméno nebo klíčové slovo. Na ty si pořídíme další funkci
match_keyword_or_name_token
.
Úkol 3 – Jména a klíčová slova [4b]
Váš třetí úkol je funkce match_keyword_or_name_token
. Jejím úkolem je
rozpoznávat jména. Konkrétně nepřerušované sekvence malých a velkých písmen
abecedy nebo číslic, které nezačínají číslicí. Stačí nám, když funkce bude
pracovat s ASCII, ale pokud se cítíte odvážně, můžete podporovat i UTF-8.
Funkce si musí všimnout, pokud je na vstupu jedno z klíčových slov (else
,
for
, if
, print
, var
, while
), a v takovém případě
místo tokenu NAME
vrátit token tohoto klíčového slova.
Po dokončení prvních tří úkolů by finální funkce lex_one
měla umět
rozpoznávat operátory, čísla, jména a klíčová slova a měla by vypadat přibližně
takto:
std::optional<Token> lex_one(Scanner &sc) {
// přeskoč whitespace
while (std::isspace(sc.peek())) {
sc.advance();
}
auto o = match_operator_token(sc);
if (o.has_value()) { return o; }
auto d = match_digit_token(sc);
if (d.has_value()) { return d; }
auto k = match_keyword_or_name_token(sc);
if (k.has_value()) { return k; }
// jinak jsme museli narazit na konec
assert(sc.is_at_end());
return std::nullopt;
}
Co jsme zatím úplně vynechali je ošetřování chyb. Náš lexer si vůbec neporadí s nevalidním vstupem, což je trochu smutné, jelikož kód je většinu času v nevalidním stavu, protože ho programátor zrovna píše a očekává chytré napovídání od svého editoru. Produkční překladače obsahují algoritmy, které se snaží šikovně ignorovat nesmyslné znaky a domýšlet si chybějící strukturu programu, aby mohly generovat nápovědy nebo podtrhávat sémantické chyby. Generované lexery jsou v této oblasti mnohem horší než ručně psané lexery, takže v praxi se člověk stále setká se spoustou ručně psaných lexerů.
Nám bude stačit velice jednoduché ošetřování chyb. Pokud náš lexer narazí na
něco, čemu nerozumí, vypíše chybu a ukončí překlad. Pokud bychom ale pouze
vypsali Chyba.
a ukončili překlad, tak by z toho programátor byl velice
smutný. Proto mu prozradíme, na který znak vstupu se překladač koukal, když vše
přestalo dávat smysl.
Úkol 4 – Chyby a lokace tokenů [4b]
Váš poslední úkol je naimplementovat vypisování pěkných zpráv při nesmyslném
vstupu včetně řádku a znaku. Budete muset rozšířit Scanner
, aby si pamatoval
aktuální řádek a sloupec. Když už tuto informaci budete mít, uložte ji do
každého tokenu. Bude se nám hodit pro podobně pěkné oznamování chyb
v pozdějších fázích překladu. Po vypsání chybové hlášky z lexeru program
ukončete.
Všechny 4 úkoly odevzdejte najednou jako jeden ZIP soubor obsahující všechen váš zdrojový kód. Oceníme i slovní popis zvoleného řešení, bohatě by měly stačit komentáře v kódu. Když budete mít jakýkoliv dotaz nebo problém, tak se nebojte zeptat na našem Discordu či pomocí emailu.