První 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 první čí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í.

Zadání úloh

Praktická opendata úloha37-1-1 Tramvajová zástavka (10 bodů)

Kevin si pozval na návštěvu několik kamarádů. Nikomu se od Kevina nechce odcházet, ale dříve nebo později budou muset jít. Každému kamarádovi jede domů nějaký spoj z blízké tramvajové zastávky, a tak Kevin navrhl, že na zastávku mohou jít všichni naráz v době, kdy se to všem „tak nějak“ bude hodit. Kdy to ale nastane?

Dostanete plán odjezdů příslušných tramvajových linek pro daný den a vaším úkolem bude najít co nejkratší časový úsek, kdy má každá linka alespoň jeden odjezd.

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 K a N. K je počet různých tramvajových linek (čísel tramvají). Na dalších N řádcích dostanete vždy čas odjezdu tramvaje a její číslo. Čas bude v klasickém formátu HH:MM:SS, dvě číslice pro hodiny, dvě pro minuty a dvě pro sekundy, oddělené dvojtečkami.

Spoje budou vypsané chronologicky, tedy časy půjdou vzestupně. Může se stát, že ve stejný čas odjede víc tramvají. Slibujeme, že tramvaj každé linky odjede alespoň jednou za den.

Formát výstupu: Vypište čas začátku úseku (odjezd první tramvaje) a jeho délku v sekundách. Čas začátku zapište opět ve formátu HH:MM:SS. Ve vámi nalezeném intervalu musí odjíždět každá z K linek.

Pozor, hledaný úsek může trvat přes půlnoc (tramvaje jezdí každý den stejně)!

Ukázkový vstup: 
3 6
09:10:00 1
09:13:40 3
09:13:40 1
09:14:32 1
09:15:00 2
09:22:15 3
Ukázkový výstup: 
09:13:40 80

Praktická opendata úloha37-1-2 Povodeň (11 bodů)

Kuchařková úloha

Po velkém požáru Smolince se místní obyvatelstvo rozhodlo zabránit budoucím požárům jednou provždy a postavilo megahydrant. Bohužel při slavnostním přestřihávání pásky omylem starosta zavadil o kohoutek a nyní se Smolincem šíří velká povodeň …

Naštěstí je obyvatelstvo Smolince připraveno na katastrofy všeho druhu a mají zásobu protipovodňových bariér. Sami mají dost práce s evakuací, a tak se na vás obracejí s prosbou: Zjistěte, kam bariéry umístit.

Mapu Smolince si můžeme představit jako mřížku R ×S, kde každé pole je buď prázdné, zastavěné nebo megahydrant. Voda se šíří od megahydrantu pouze skrz prázdná pole. Na prázdné pole můžeme postavit protipovodňovou bariéru, čímž zabráníme šíření vody skrz něj. Nicméně bariéra musí mít pevné podpěry – Abychom na pole mohli postavit bariéru, buď severní a jižní pole musí být zastavěné, nebo východní a západní musí být zastavěné.

Najděte umístění bariér takové, že počet zatopených nezablokovaných polí bude co nejmenší. Pokud takových umístění existuje více, vypište to s nejmenším počtem použitých bariér.

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ů. Na každém z dalších R řádků naleznete S znaků popisujících mapu Smolince. Znak H značí megahydrant, . značí prázdné pole a # značí zastavěné pole.

Formát výstupu: Na prvním řádku vypište číslo M – počet použitých bariér. Na dalších M řádcích vypište čísla xi, yi – sloupec a řádek i-té postavené bariéry.

Ukázkový vstup: 
6 5
##.#.
#H.##
#....
#.###
#.#..
.....
Ukázkový výstup: 
3
3 1
4 3
2 4

Při postavení bariér na příslušná pole bude Smolinec zatopen následovně (B značí bariéru, W vodu):

##B#.
#WW##
#WWB.
#B###
#.#..
.....
Nelze mít méně než 4 zatopená pole. Není možné dosáhnout 4 zatopených polí s méně jak 3 bariérami.

Teoretická úloha37-1-3 Zpřeházená fronta (12 bodů)

Na studijní oddělení Hroší univerzity v Hroším Týnci dorazila skupina N studentů, kteří se dopředu objednali pro vyzvednutí studentského průkazu. Každý z nich stojí na nějaké z vyznačených pozic, které na studijním zůstaly z protipandemických opatření.

Studenti ale dorazili v jiném pořadí, než ve kterém byli objednáni. Nyní je potřeba je správně seřadit, aby se paní úřednici nerozbil informační systém. Každý student ví, na kterou pozici byl předem objednán a na jaké pozici nyní stojí.

Aby se organizace přesunu studentů ve frontě zjednodušila, chtěla by paní úřednice pro každou pozici na studijním oddělení určit, odkud se na ni má patřičný student přemístit.

Je tu však menší problém. Paní úřednice, která studenty potřebuje přeřadit, trpí anterográdní amnézií a nedokáže si pamatovat údaje o všech studentech najednou.

Trochu formálněji: Vyznačené pozice na podlaze studijního oddělení si můžete představit jako pole A, které máte již načtené v paměti a můžete ho měnit. Na začátku výpočtu A[i] říká, na kterou pozici se má přesunout student, který původně stál na na pozici i. Na konci výpočtu má být A[i] rovno původní pozici studenta, který se má přesunout na pozici i. Po celou dobu výpočtu smí pole obsahovat pouze celá čísla od 1 do N. Jediná další paměť, kterou máte k dispozici, je konstantně mnoho proměnných pro celá čísla velká O(N).

Toto je teoretická úloha. Není nutné ji programovat, odevzdává se pouze slovní popis algoritmu. Více informací zde.

Teoretická úloha37-1-4 Nuly a jedničky (12 bodů)

Barnabáš se začetl do Pohádek tisíce a jedné noci. Při tom si uvědomil, jak zajímavé je číslo 1001 – je dělitelné nejen 7, ale také 11 a 13. Tak začal hledat jiná čísla z nul a jedniček, která mají zajímavé dělitele.

Napište mu program, který pro zadané N ≥ 1 najde nejmenší celé kladné číslo dělitelné N, v jehož desítkovém zápisu se vyskytují jen nuly a jedničky. Případně odpoví, že žádné takové číslo neexistuje.

Například pro N = 4 je řešením číslo 100, pro N = 5 je to 10, pro N = 7 je to 1001 a pro N = 11 číslo 11.

Teoretická úloha37-1-X1 Bomberman (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.

Už to bylo chvíli, co slavný Bomberman pokládal výbušniny… Po vlně velké slávy si koupil vzducholoď, se kterou procestoval svět. Poté ale začal stárnout, jeho bomby se začaly rozbíjet a už nemohl chodit jako dřív. Nyní se však rozhodl všem ukázat, že ještě bomby pokládat umí.

Bomberman se rozhodl vyprázdnit mřížku R ×S, kde každé políčko je buď prázdné, nebo zničitelné. Momentálně se nachází ve své vzducholodi, a tak může pokládat bomby na úplně libovolné pole (i zničitelné). Nicméně jeho bomby částečně nefungují. Bomba dokáže zničit buď celý sloupec, ve kterém je položena, nebo celý řádek, ve kterém je položena, ale ne obojí zároveň. Bomberman by měl jít co nejdříve do postele, a proto chce položit co nejméně bomb tak, aby zničil všechna zničitelná políčka. Poraďte mu, kam je má položit.

Seriálová úloha37-1-S Návrat virtuálního stroje (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.

V tomto ročníku jsme si pro vás připravili praktický seriál o překladačích programovacích jazyků. Programovací jazyky a překladače představují obrovskou krajinu k prozkoumávání. Spousta informatiků strávila celé kariéry tím, že se touto zemí procházeli, aniž by někdy dosáhli jejího konce. Pokud do této země právě vstupujete poprvé, vítejte.

V průběhu příštích několika měsíců si ukážeme část této krajiny. Konkrétně si spolu sestrojíme jednoduchý překladač našeho vymyšleného programovacího jazyka. Přiblíží nám to vhled do produkčních překladačů a jazyků, které překládají. Se základními znalostmi jazyka a místních zvyků může každý z vás pokračovat svou vlastní cestou.

Úkolem překladače je přeložit zdrojový kód do kódu strojového. Zdrojovým kódem pro nás bude text v našem vymyšleném programovacím jazyce (který si představíme příště). Strojový kód je sekvence primitivních instrukcí, které nějaký stroj dokáže vykonat. Jeden strojový kód si ukážeme dnes.

Práce překladače se dá rozdělit do několika fází. Každá fáze transformuje vstupní program z jedné reprezentace do jiné (na začátku zdrojový kód, na konci strojový kód). Všechny reprezentace jsou přitom dost různé.

Transformace se dají rozdělit do dvou skupin. První analyzují a vytváří strukturu – těm se říká frontend překladače. Někde v polovině překladu nastane zlom a překladač se pustí do druhé skupiny transformací – backend. Ty pak tuto analyzovanou strukturu rozkládají a tvoří finální reprezentaci.

Celý průběh překladu si můžeme představit jako výlet začínající v údolí Zdrojového Kódu, který pokračuje výlezem na vrcholek hory Programové Analýzy, ze které pak zase musíme slézt dolů na druhou stranu do údolí Strojového Kódu.

V rámci tohoto seriálu si celou tuto stezku projdeme. Inspirovali jsme se ale Georgem Lucasem a dneska začneme uprostřed naší cesty: na útulné horské chatě těsně za vrcholem.

Návrat virtuálního stroje

Skutečné stroje dnešní doby jsou pro naše účely zbytečné složité. Dnes tedy začneme tím, že si vyrobíme simulátor jednoduššího stroje. V příštích dílech si postavíme překladač do tohoto virtuální stroje a na konci seriálu opustíme virtuální stroj a přesuneme se ke strojům fyzickým.

Ačkoliv se může zdát, že virtuální stroj má využití pouze jako mezikrok ke skutečným strojům, interprety jsou v dnešní době velmi populární. Python, JavaScript, a do jisté míry i C# nebo Java jsou všechny založené na nějakých virtuálních strojích. Výhodou tohoto přístupu je například, že stejný kód může běžet na různých fyzických strojích bez jakýchkoliv modifikací. Virtuální stroj slouží jako abstrakce nad skutečným hardwarem a poskytuje identické prostředí na různých platformách. Na druhou stranu virtuální stroj s sebou nese i velkou cenu. Například simulace virtuálního stroje nám často řádově zpomalí běh programu. Stejně jako všechno v životě, je to kompromis. Zpátky k našemu virtuálnímu stroji.

Od našeho virtuální stroje budeme chtít, aby uměl vykonávat primitivní instrukce které operují (zatím pouze) s čísly. Všechny hodnoty, se kterými stroj pracuje, si budeme ukládat na zásobník a instrukce budou uložené v poli. Operace stroje bude vypadat takto:

Vykonání instrukce bude často vypadat přibližně takto:

Jak jste měli možnost si vyzkoušet v 36-2-4 a 35-4-1, programování čistě zásobníkového stroje není úplně přívětivé. Bez instrukce pro indexování zásobníku je to dokonce prakticky nemožné. Kromě zásobníku tedy naučíme náš stroj zároveň pracovat s pojmenovanými proměnnými a přidáme instrukce na zkopírování hodnoty ze zásobníku do proměnné a naopak. Zásobník pak budeme používat primárně pro mezivýsledky a ostatní věci ukládat do proměnných.

Data, se kterými bude náš virtuální stroj pracovat, můžeme reprezentovat například takto:

(V průběhu seriálu budeme používat C++23. Řešení akceptujeme prakticky v libovolném jazyce, ale pokud chcete plný počet bodů, tak svoje řešení napište v jazyku, který sám není interpretovaný. Speciálně považujeme za rozumné: C++ (ehm), Rust, Zig, Go, C#, F#, ML, OCaml, Java, Kotlin, Scala, Nim, Swift, D, Odin, Crystal.)

#include <string>
#include <unordered_map>
#include <variant>
#include <vector>

using namespace std;

enum Opcode {
  OP_PRINT,
  OP_PUSH,

  OP_LOAD,
  OP_STORE,

  OP_ADD,
  OP_SUB,
  OP_MUL,
  OP_DIV,
  OP_DUP,
};

struct Instruction {
  // typ instrukce
  Opcode op;

  // některé instrukce si potřebují
  // pamatovat další hodnoty
  variant<monostate, int, string> value = monostate{};
};

vector<Instruction> instrukce;
vector<int> stack;
unordered_map<string, int> promenne;
int ip;

Úkol 1 – Aritmetické operace [5b]

Prvním úkolem bude naimplementovat instrukce pro základní aritmetické operace (sčítání, odčítání, násobení a dělení) a instrukci DUP. Aritmetické instrukce dělají, co byste ze jména čekali. Odeberou dvě hodnoty ze zásobníku, provedou na nich operaci, kterou mají ve jméně, a výsledek přidají zpátky na zásobník.

Například pokud máme na zásobníku hodnoty 6 12 33 -3, po provedení instrukce OP_MUL bude zásobník vypadat takto: 6 12 -99. Pokud by následovala instrukce OP_SUB, bude zásobník obsahovat hodnoty 6 111.

Budeme chtít, aby druhý operand byla první hodnota ze zásobníku a první operand druhá hodnota ze zásobníku. To se může zdát lehce neintuitivní, ale usnadní nám to práci v příštích dílech seriálu.

Instrukce OP_DUP odebere hodnotu ze zásobníku a ihned jí tam zase dvakrát přidá. Vypadá to, jako kdyby se vrchní hodnota zásobníku duplikovala.

Dnešní úkoly můžete implementovat do následující šablony virtuálního stroje. Nezapomeňte si zkopírovat definice Opcode a Instruction výše.

#include <print>

using namespace std;

void interpret(
    vector<Instruction> const &instrukce,
    vector<int> &zasobnik,
    unordered_map<string, int> &promenne) {
  int ip = 0; // index aktuální instrukce
              // (instruction pointer)
  while (true) {
    if (!(ip >= 0 && ip < ssize(instrukce)))
      break;

    auto ins = instrukce.at(ip);

    switch (ins.op) {
    case OP_PRINT: {
      println("PRINT: {}", zasobnik.back());
    } break;

    case OP_LOAD: {
      zasobnik.push_back(
          promenne[get<string>(ins.value)]);

    } break;

    case OP_STORE: {
      promenne[get<string>(ins.value)] =
          zasobnik.back();
      zasobnik.pop_back();
    } break;

    case OP_PUSH: {
      zasobnik.push_back(get<int>(ins.value));
    } break;

    case OP_ADD: {
      // TODO
    } break;
    case OP_SUB: {
      // TODO
    } break;
    case OP_MUL: {
      // TODO
    } break;
    case OP_DIV: {
      // TODO
    } break;
    case OP_DUP: {
      // TODO
    } break;
    }
    ip += 1;
  }
}

Funkci interpret bychom pak mohli volat takto:

int main() {
  vector<int> zasobnik;
  vector<Instruction> instrukce(
      {Instruction{.op = OP_PUSH, .value = 8},
       Instruction{.op = OP_STORE, .value = "x"},
       Instruction{.op = OP_LOAD, .value = "x"},
       Instruction{.op = OP_PRINT}});
  unordered_map<string, int> promenne;

  interpret(instrukce, zasobnik, promenne);
}

Pro příjemnější vývoj doporučujeme zapnout sanitizátory a varování:

c++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined ./main.cpp

V každém pořádném programovacím jazyce se lze donekonečna zacyklit, ale náš virtuální stroj to zatím vůbec nepodporuje. Pokud jste zvyklí, že podmínky i cykly vyžadují nějaké vnořování bloků, tak se teď možná bojíte, že jejich přidáním všechno zkomplikujeme. Naštěstí je to přesně opačně. Nic jako OP_SLOŽENÁ_ZÁVORKA nebudeme potřebovat a cykly i podmínky vyřešíme jednou triviální instrukcí.

Bude to instrukce podmíněného skoku, typicky nazývaná „branch“. Taková instrukce sebere vrchní hodnotu ze zásobníku a podle ní se rozhodne, jestli bude prostě pokračovat na další instrukci v pořadí, anebo skočí a program bude pokračovat někde jinde. If pomocí této instrukce můžeme nasimulovat tak, že daný blok přeskočíme, pokud podmínka neplatí. While cyklus uděláme velmi podobně, akorát na konec bloku přidáme nepodmíněný skok zpět.

Úkol 2 – Podmíňený skok [5b]

Přidejte instrukci OP_BRANCH, která skočí na instrukci s indexem uvedeným ve value za podmínky, že hodnota sebraná ze zásobníku není nula. Kde bude interpret pokračovat, ovlivníte změnou instruction pointeru ip.

Bude se nám hodit několik dalších instrukcí pro práci s hodnotami TRUE a FALSE. Speciální datový typ nepotřebujeme, FALSE budeme reprezentovat jako nulu a TRUE jako jedničku. Přidejte také následující „logické“ operace:

Úkol 3 – Jednoduchý program [5b]

Dnešním posledním úkolem bude využít všechny funkce virtuálního stroje, které jsme si připravili, a napsat si nějaký jednoduchý program.

Napište program pro váš virtuální stroj na počítání faktoriálů. Můžete si vybrat, jestli vstup zadrátujete jako proměnnou, nebo jako hodnotu na zásobníku. Využijte přitom instrukce pro přesun hodnot mezi proměnnými a zásobníkem, aritmetiku a skoky.

Předpokládáme, že váš program bude i se vstupem zadrátovaný ve funkci main a že výsledek vypíše do konzole pomocí instrukce OP_PRINT.

Všechny 3 ú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