roury.pas
/ roury.c
/ roury.cpp
roury.in
roury.out
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.
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.
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.
roury.in
roury.out
kameny.pas
/ kameny.c
/ kameny.cpp
kameny.in
kameny.out
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.
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.
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.
kameny.in
kameny.out
kameny.in
kameny.out