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í.- Termín série: neděle 3. listopadu 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 z každé úlohy série získá alespoň 2 body.
Zadání úloh
- 37-1-1: Tramvajová zástavka
- 37-1-2: Povodeň
- 37-1-3: Zpřeházená fronta
- 37-1-4: Nuly a jedničky
- 37-1-S: Návrat virtuálního stroje
- 37-1-X1: Bomberman
37-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ě)!
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
09:13:40 80
37-1-2 Povodeň (11 bodů)
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.
6 5 ##.#. #H.## #.... #.### #.#.. .....
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.
37-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.
37-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.
37-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.
37-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:
- přečti aktuální instrukci
- vykonej ji
- posuň se o 1 instrukci dál („instruction pointer“ zvyš o 1)
- opakuj
Vykonání instrukce bude často vypadat přibližně takto:
- odeber několik hodnot ze zásobníku
- proveď na nich danou operaci
- přidej výsledek na zásobník
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:
-
OP_NOT
– Sebere hodnotu ze zásobníku. Pokud to byla nula, přidá 1, jinak přidá 0. -
OP_EQ
– Sebere dvě hodnoty ze zásobníku. Pokud se rovnají, přidá 1, jinak přidá 0. -
OP_LT
– Sebere ze zásobníku hodnoty B a A. Pokud je A < B, přidá 1, jinak přidá 0.
Ú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.