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

• 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 úžasností 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 a_i, v_i a u_i: 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.

Řešení

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ží.

Řešení

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.

Řešení

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.

Řešení

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.

Nápověda

Protože se nikomu nepodařilo tuto úlohu vyřešit, rozhodli jsme se, že prodloužíme její deadline do konce 3. série. Navíc vydáváme následující nápovědu, která vám snad pomůže k řešení.

Může pomoci nejprve vyřešit následující úlohu:

Máme zadanou posloupnost prvků a₁ až a_n a nějakou binární operaci ⊗ nad těmito prvky, o které víme jen, že je asociativní a že ji umíme počítat v konstantním čase. Vybudujte datovou strukturu, která umí pro zadaný interval posloupnosti mezi i a j spočítat

v konstantním čase. Zkuste též zařídit, aby byla binární operace zavolána během dotazu jen jednou.

Následně upravte vaše řešení tohoto problému na řešení skutečné úlohy. K tomu pomůže několik šikovných vlastností nadpolovičních většin.

Řešení

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

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.

Prokop Randáček, Standa Lukeš & Ondra Machota

Řešení