Čtvrtá série třicátého ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 14. května 2018. Řešení můžete odevzdávat jak elektronicky, tak klasickou poštou na známou adresu.

Dotazy ohledně zadání můžete posílat na adresu ksp@mff.cuni.cz, nebo se ptát přímo na diskusním fóru KSP.

Odměna série: Sladkou odměnu si vyslouží každý, kdo odevzdá alespoň tři úložky alespoň týden před termínem a získá za ně kladný počet bodů.

Zadání úloh


Teoretická úloha30-4-1 Černobílé hádání (9 bodů)


Náš kamarád má pole o n černých a bílých políčkách. Je ale poněkud stydlivý, takže nám pole nechce ukázat. Po krátkém přemlouvání nám prozradil aspoň hodnotu n a také to, že v poli je přesně m souvislých úseků stejné barvy (například v poli ###..## jsou tři), přičemž m je řádově menší než n. Kamarád je navíc ochoten odpovídat na dotazy „Je v úseku [a, b] aspoň jedno políčko bílé/černé?“ Na co nejméně dotazů zjistěte, jak vypadá celé pole.


Teoretická úloha30-4-2 Kočka na stromě (10 bodů)


Kuchařková úlohaKočka vylezla na strom a neumí slézt. Hasiči ji jedou zachránit. Potřebují dorazit co nejrychleji, takže se vydají po nejkratší cestě. Mohlo by se ale stát, že tato cesta nebude průjezdná. Chtějí tedy vyslat ještě jedno záložní auto po jiné nejkratší cestě, která nebude s trasou prvního auta mít společné nic kromě začátku a konce.

Poněkud matematičtěji řečeno, máte zadán ohodnocený neorientovaný graf a dva vrcholy označené jako start a cíl. Vaším úkolem je najít mezi nimi dvě vrcholově disjunktní nejkratší cesty, pokud existují. Tím myslíme dvě cesty, které jsou obě nejkratší (tedy stejně dlouhé) a nemají žádný společný vrchol kromě startu a cíle.

Na následujícím obrázku vidíte příklad grafu s vyznačenými dvěma vrcholově disjunktními nejkratšími cestami (délky 7):

Graf se dvěma vrcholově disjunktními nejkratšími cestami

Ale například pro následující graf řešení neexistuje – obsahuje celkem čtyři nejkratší cesty, jenže všechny procházejí jedním společným vrcholem:

Graf se dvěma nejkratšími cestami, které nejsou vrcholově disjunktní

Teoretická úloha30-4-3 Hippocoin (10 bodů)


Na soustředění KSP vznikla nová kryptoměna hippocoin. Chceme využít situace a vydělat obchodováním s hippocoiny co nejvíce peněz. Hippocoin lze kupovat a prodávat za peníze. Každý den je vyhlášena nákupní a prodejní cena a my pak máme možnost koupit, nebo prodat libovolný počet hippocoinů. Kupní cena je přitom vždy vyšší, nebo rovná prodejní a všechny ceny jsou kladné. Na začátku máme dané množství peněz a v průběhu obchodování nikdy nesmíme mít záporné množství hippocoinů ani peněz.

Hippocoiny i koruny jsou libovolně dělitelné – lze obchodovat s libovolně malým zlomkem hippocoinu. Máme k dispozici předpověď, jaká bude nákupní a prodejní cena hippocoinu v každém z následujících k dní. Chceme zjistit, jak obchodovat (tedy kolik hippocoinů který den nakoupit či prodat), abychom na konci k-tého dne měli co nejvíce korun, pokud se bude cena vyvíjet přesně podle naší předpovědi.

Lehčí variantaLehčí varianta (za 7 bodů): Vyřešte úlohu pro případ, kdy nákupní cena je vždy stejná jako prodejní.


Teoretická úloha30-4-4 Malování 2.0 (12 bodů)


Právě vyšla nová verze programu Malování! Umí sice jenom černobílé obrázky o n ×m pixelech, ale zato nabízí skvělý nový nástroj: magický štětec. Ten všem pixelům ve čtverci k×k okolo místa, kam jsme klikli, prohodí barvu na opačnou. Zatím jsme nepřišli na to, kde se velikost čtverce dá nastavit, takže k považujeme za konstantu.

Přesněji: Pokud klikneme na políčko se souřadnicemi (a,b), prohodí se barva všem pixelům (x,y) takovým že, a≤ x<a+k a b≤ y<b+k. Čtverec nesmí přečnívat přes okraj obrázku, tedy musí platit a+k < n, b+k < m.

Zajímá nás, které obrázky se magickým štětcem dají nakreslit. Dostaneme zadaný černobílý obrázek velikosti n×m a velikost štětce k. Máme zjistit, zda lze tento obrázek vytvořit používáním magického štětce na zpočátku bílou plochu.


Praktická opendata úloha30-4-5 Frňákovník (10 bodů)


Na tržišti se objevil tajuplný stánek, v němž bělovlasá stařena s bradavicí na nose prodává džus z frňákovníku. Jak jistě víte, stačí ho vypít jedinou sklenku a nos se vám prodlouží do nevídaných rozměrů, k velkému pobavení širého okolí. Jaký by to byl skvělý dárek na narozeninovou párty vašeho nejlepšího nepřítele!

Stařena je ovšem poněkud vybíravá v tom, komu a jak džus prodá. Každý si musí přinést své vlastní nádoby, které mu naplní až po okraj. Navíc je ochotna prodat pouze takové celkové množství džusu, které je násobkem 7 dl.

Pořídili jste si N různých nádob s celočíselnými kapacitami k1, …, kNdl a chcete z nich vybrat takové, aby součet jejich objemů byl násobkem 7 dl a přitom byl co největší. Vymyslete algoritmus, který tyto nádoby najde.

Toto je praktická open-data úloha. V odevzdávacím systému 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 celé číslo N udávající počet nádob. Na každém z dalších N řádků dostanete celé číslo udávající objem jedné nádoby v decilitrech.

Formát výstupu: Na první řádek vypište dvě celá čísla oddělená mezerou: největší množství džusu, které lze zakoupit, a počet nádob, které při tom budou naplněny (k). Na dalších k řádků vypište pořadová čísla použitých nádob. Nádoby číslujeme od nuly v pořadí, v jakém se objevily na vstupu. Pokud existuje více správných řešení, vypište libovolné. Pokud neexistuje žádné řešení, vypište jen první řádek obsahující 0 0.

Počet nádob a jejich objemy jsou menší než 231, ale na součty už můžete potřebovat 64-bitová čísla (long long v Céčku).

Ukázkový vstup:
5
2
3
2
2
17
Ukázkový výstup:
21 3
0
3
4

Teoretická úloha30-4-6 Takřka nudná úloha (14 bodů)


Na vstupu máme dva textové řetězce. Chceme najít jejich nejdelší společnou podposloupnost. Co se tím myslí? Podposloupnost vznikne z posloupnosti vyškrtáním některých prvků: například abc, acdf nebo prázdný řetězec jsou podposloupnostmi řetězce abcdef. Nevyškrtnuté prvky přitom musí zůstat v původním pořadí. Naším cílem je najít nejdelší řetězec, který je podposloupností obou zadaných řetězců.

Nuda, řeknete si – tohle je přeci dobře známá úloha, na kterou existuje algoritmus s časovou složitostí O(n2) a paměťovou také O(n2) pro dva řetězce délky n. Najdete ho například v naší kuchařce o dynamickém programování.

Kdepak, žádná nuda to nebude. Zadané řetězce jsou totiž tak dlouhé, že si nemůžeme dovolit víc než lineárně mnoho paměti. Vymyslete proto co nejrychlejší algoritmus na nalezení nejdelší společné podposloupnosti, kterému stačí O(n) paměti. Prozradíme ještě, že by se k tomu mohla hodit i kuchařka na metodu Rozděl a panuj.

Tuto velmi zajímavou sérii úloh vám zcela jistě přinesli organizátoři KSP, ne pan Nápověda. Na to se můžete stoprocentně spolehnout.