Úložky

Navrhněte sadu co nejméně závaží (a dokažte to o ní), se kterými dokážete pomocí rovnoramenných vah určit hmotnost předmětu mezi 1 až 1000 gramy. Předměty přitom mohou vážit jen celočíselný počet gramů.

Máte tři nádoby o kapacitách osm, pět a tři litry. Osmilitrová je na začátku plná, dvě zbylé jsou prázdné. Mezi dvěma nádobami můžete vodu přelévat. Vaším úkolem je nalézt posloupnost přelévání takovou, aby po jejím provedení byly ve dvou nádobách právě čtyři litry vody, případně dokažte, že neexistuje.

Máte šachovnici N krát N s černými a bílými políčky, na začátku jsou políčka obarvena jako při šachách. Povoleným tahem je v libovolné řádce nebo libovolném sloupci změnit černá políčka za bílá a naopak. Najděte takovou posloupnost tahů, aby na šachovnici zbylo právě jedno černé políčko. Pokud to pro některé N nejde, dokažte to.

V mrakodrapu je nataženo N drátů. Dráty se však pomíchaly a nikdo už neví, který z N konců drátů v přízemí patří ke kterému z N konců ve vrchním patře. Jako instalatér začnete v přízemí, můžete libovolné dráty jakkoliv označovat, spojovat a rozpojovat a také umíte zjistit, zda jsou dva konce drátů spojeny či ne. A samozřejmě umíte přecházet mezi přízemím a vrchním patrem.

Navrhněte obecný postup, na konci kteréhož budou konce drátů v přízemí i ve vrchním patře označeny čísly 1 až N a oba konce jednoho drátu budou označeny stejným číslem. Navíc v mrakodrapu nefunguje výtah a proto najděte postup s nejmenším počtem přesunů mezi přízemím a vrchním patrem.

Máte přestěhovat N rodin (rodiny označujeme přirozenými čísly od 0 do N−1), a to tak, aby se rodina i dostala do bytu rodiny (i+K) mod N. Stěhování probíhá po dnech a to tak, že si libovolná rodina může vyměnit byt s libovolnou jinou rodinou, ale každá rodina se může stěhovat nanejvýš jednou během jednoho dne. Vaším cílem je navrhnout obecný postup stěhování (pro libovolná kladná K a N), který zabere co nejméně dní.

Máte šachovnici 8×8 s vykousnutými dvěma protějšími rohy. Vydlážtěte ji dominovými kostkami 2×1, nebo dokažte, že to nelze.

Napište program, který vypíše sám sebe.

Máte 10 pytlů s mincemi. V devíti z nich jsou mince pravé (každá váží jeden gram), v desátém pytli jsou mince falešné (váží 1,1 gramu). Máte k dispozici digitální váhy. Pomocí jednoho měření najděte pytel s falešnými mincemi.

Napište program, který dostane číslo N a posloupnost N−1 neopakujících se čísel v rozmezí 1 až N a zjistí, které z čísel 1 až N na vstupu chybělo.

V jednom nejmenovaném hotelu mají pokoje očíslované 000 až 999. Chtějí nastříkat na dveře všech pokojů jejich čísla a k tomuto účelu si vyrobí čtyřmístné šablony. Jednu šablonu tedy mohou použít pro nastříkání dvou pokojů (např. šablona 1234 poslouží pro pokoje 123 a 234). Navrhněte, jak mají tyto šablony vypadat, aby jich bylo potřeba co nejméně.

Na vstupu dostanete posloupnost čísel. Každé číslo se v posloupnosti vyskytuje dvakrát s výjimkou jednoho, které se vyskytuje pouze jednou. Nalezněte toto číslo.

Napište program v libovolném programovacím jazyce, který zjistí, zda překladač podporuje vnořené komentáře.

Najděte nejmenší složené Carmichaelovo číslo.

Napište program, který lze beze změny přeložit kompilátory dvou vašich oblíbených jazyků a po spuštění vypíše v jakém jazyce byl napsán právě prováděný kód.

Na vstupu dostanete graf s ohodnocenými hranami. Hodnoty hran jsou reálná čísla v intervalu [0,1], které chápejte jako pravděpodobnosti. Navrhněte algoritmus, který nalezne nejpravděpodobnější cestu mezi dvěma danými vrcholy.

Charakterizujte grafy nakreslitelné jedním tahem.

Navrhněte algoritmus, který co nejrychleji nalezne K-tý nejmenší prvek v zadané posloupnosti čísel.

Dokažte, že strom o N vrcholech má N−1 hran. Za další bod dokažte, že je-li graf o N vrcholech souvislý a má-li N−1 hran, pak je to strom.

Napište program řešící Lloydovu devítku.