Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Kodikovi na [email protected]
Jednej noci o polnoci mladí vedúci idú spať,
v tú chvíľu Adam zo svojej skrýše vylieza a šepká: “Budeme sa hrať.”
Odbyla polnoc,
dúfam, že nie ste unavení,
vyskočím na chodbu,
tak berte nohy na ramená.
Nato Dávid chytá nervy,
stojí na chodbe, sleduje Adama.
Adam v strachu nahlas skríkne : “Čo horšieho sa mi môže stať?”
Kubo z druhej strany vraví :”Dohral si sa kamarát.”
Adam sa klepe a kričí :”No tak musím ujsť!”
Dávid aj Kubo sa rozbehnú a idú ho chytiť.
Máme $n$ metrov chodby. Na každom metre chodby je buď Adam, Dávid alebo Kubo (z každého môže byť viac). Každý Dávid má práve jedného Kuba s ktorým chytá. Navyše platí, že keď si tieto dvojice predstavíme ako dvojice zátvoriek kde Dávid je ( a Kubo je ), tvoria správne uzátvorkovanú postupnosť na chodbe^[Teda napríklad DKADK znamená []A() a nie [)A(].]. Keď sa Dávid stretne s Kubom tak to obja vzdajú a idú spať, lebo im Adam ušiel. Dávid by chcel zistiť, koľko Adamov nedokážu chytiť, teda koľko je takých Adamov, ktorí sa nenachádzajú medzi žiadnou dvojicou Dávida a Kuba ktorí spolu chytajú.
Na prvom riadku je celé číslo $n$ ($1 \leq n \leq 1\,000\,000$) udávajúce dĺžku chodby v metroch.
Na ďalšom riadku sa nachádza reťazec písmen “A”, “D”, a “K” dlhý $n$ znakov – zápis chodby, kto kde stojí.
Na výstup vypíšte jedno celé číslo - počet Adamov, ktorých nechytia.
Existujú 2 sady vstupov. Platia v nich nasledovné obmedzenia:
| Sada | 1. | 2. |
|---|---|---|
| $1 \leq n \leq$ | $100$ | $1\,000\,000$ |
| Body | 30 | 70 |
9
DKDDDAKKK
0
10
DAAKADKAAA
4
Prví dvaja Adamovia sú obklúčení, ostatní nie su obklúčení.
Adam je chytený len ak sa nachádza medzi Dávidom a Kubom, to si vieme v tiež pomerne ľahko odsimulovať. Ak si chceme pamätať či existuje nejaký Davíd ktorý sa zatiaľ s Kubom nezrazil a teda on by mohol Adama chytiť, tak si ho vieme ukladať do zásobníku. Pokiaľ narazíme na Adama a náš zásobník má veľkosť(nie je prázdny) tak vieme že by ho niektorý Dávid by ho vedel chytiť, ak narazíme na Adama tak sa s Dávidom zrazí a môžme ho odstrániť(Dávida) zo zásobníku. Teda iba by sme vždy keď narazíme na Adama pripočítali +1 do výsledku. Niektoré bystré hlavy si mohli všimúť, že nám vlastne nezáleží čo je v zásobníku ale iba koľko a teda vieme ho nahradiť premennou kam iba pripočítavame a odpočítavame. Naše riešenie má časovú zložitosť O(n), pamäťovú zložitosť O(n). Pokiaľ by sme načítavali vstup po charakteroch tak dostaneme pamäťovú zložitosť O(1).
Súťaž PRASK zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre stredoškolákov
Tímová matematicko-fyzikálna súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
