Matematická olympiáda – kategorie P

Zadání úloh ústředního kola (2. soutěžní den) 51. ročníku

P-III-4

Program: roury.pas / roury.c / roury.cpp
Vstup: roury.in
Výstup: roury.out

Ve výzkumném ústavu potrubí a rour mají opět nový problém. Dostali zakázku od Vodáren a kanalizací města Blatislavy, kde je potřeba pročistit městskou kanalizaci od nánosů bláta. Postup při čištění trubek od bláta je jednoduchý: Čistící robot musí projít každou trubkou právě jednou; kdyby robot prošel již vyčištěnou trubkou, hrozilo by nebezpečí, že jeho silné čistící prostředky tuto trubku poškodí. Robot může do trubky vstoupit z jejího libovolného konce; pokud však již do trubky vstoupí, musí jí celou projít.

Pracovníci výzkumného ústavu si rychle uvědomili, že za těchto podmínek se může stát, že jeden robot na vyčištění celé městské kanalizace nebude stačit. Doporučili tedy do kanalizace poslat více robotů najednou a naprogramovat je tak, aby dohromady pročistili celou kanalizaci.

Nový typ čistícího robota ale není zrovna levný, a proto je potřeba navrhnout takový postup, aby celá kanalizace byla vyčištěna pomocí co nejmenšího počtu robotů. A to je už úkol pro vás.

Kanalizační síť je tvořena n uzly očíslovanými od 1 do n, mezi kterými vede m trubek. Každá trubka spojuje dvojici uzlů a nemá žádné odbočky, ani se nikde nevětví. Mezi každou dvojicí uzlů vede nejvýše jedna trubka.

Soutěžní úloha

Vytvořte program, který pomůže naplánovat trasy pro čistící roboty. Program načte popis kanalizační sítě, určí minimální počet robotů postačující pro vyčištění celé sítě a navrhne jejich trasy tak, aby každou trubkou prošel právě jeden z nich právě jednou.

Formát vstupu

První řádek vstupního souboru roury.in obsahuje dvě kladná celá čísla: počet uzlů n (1<=n<=500) a počet trubek m, oddělená mezerou. Každý z následujících m řádků popisuje jednu trubku; obsahuje vždy dvě čísla oddělená mezerou, což jsou čísla koncových uzlů trubky.

Formát výstupu

Na prvním řádku výstupního souboru roury.out bude zapsáno jediné celé číslo R -- nejmenší počet robotů, který postačuje k vyčištění kanalizační sítě. Následuje R řádků, z nichž i-tý popisuje trasu i-tého robota. Pokud i-tý robot začíná čistící proces v uzlu a_1, odtud pokračuje trubkou do uzlu a_2, pak do a_3, atd. až skončí v uzlu a_k, potom příslušný řádek výstupního souboru obsahuje k čísel a_1,a_2,...,a_k (v tomto pořadí) oddělená od sebe vždy jednou mezerou.

Jestliže existuje více optimálních řešení, váš program má za úkol nalézt a vypsat právě jedno z nich.

Příklad

roury.in 8 8 1 2 1 3 1 4 3 5 4 5 4 6 5 6 7 8 roury.out 3 2 1 3 5 4 1 4 6 5 8 7

P-III-5

Program: kameny.pas / kameny.c / kameny.cpp
Vstup: kameny.in
Výstup: kameny.out

Uvažujme následující hru pro jednoho hráče. Hrací plán je tvořen K políčky uspořádanými do jedné řady. Na začátku hry je na tomto plánu umístěno několik hracích kamenů (na každém políčku leží nejvýše jeden kámen). Je zadána tzv. cílová pozice, tj. rozestavení kamenů, kterého je třeba dosáhnout. V jednom tahu můžeme táhnout kamenem z políčka p tak, že jím přeskočíme kámen ležící na sousedním políčku. Přesněji: Pokud je na sousedním políčku napravo (nalevo) od políčka p kámen a následující políčko tímto směrem je volné, lze kámen z políčka p přesunout na volné políčko a přeskočený kámen odstranit z hracího plánu. Jak již bylo řečeno, úkolem je dosáhnout pomocí těchto tahů cílové pozice. Pokud ze zadané pozice lze cílové pozice dosáhnout, říkáme, že zadaná pozice je vyhrávající.

Například, pokud pozice vlevo na následujícím obrázku je cílová, pak v prostředním sloupci je jedna z vyhrávajících pozic vzhledem k této cílové pozici (s uvedením příslušné posloupností tahů, kterými lze cílové pozice dosáhnout). Naopak pozice v pravé části obrázku není vyhrávající, neboť v ní lze na začátku táhnout jen prostředním ze tří kamenů a tím se dostaneme do pozice se dvěma kameny oddělenými dvěma prázdnými políčky, ze které již nelze dál pokračovat ve hře.

Soutěžní úloha

Vytvořte program, který přečte dvě celá čísla K a N a cílovou pozici a vypíše počet různých vyhrávajících pozic tvořených nejvýše N kameny.

Formát vstupu

Vstupní soubor kameny.in bude obsahovat na prvním řádku dvě celá čísla K a N oddělená jednou mezerou. Na druhém řádku souboru bude zadána cílová pozice jako posloupnost K nul a jedniček oddělených mezerami, kde jednička představuje políčko obsazené kamenem a nula prázdné políčko. Můžete předpokládat, že platí 1<=N<=K<=100.

Formát výstupu

Výstupní soubor kameny.out bude obsahovat jedno celé číslo, které udává počet vyhrávajících pozic tvořených nejvýše N kameny. Můžete předpokládat, že toto číslo nepřesáhne 10 000.

Příklad

kameny.in 6 3 0 0 1 1 0 0 kameny.out 3 kameny.in 8 5 1 0 0 0 0 0 0 1 kameny.out 10