Matematická olympiáda – kategorie P

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

P-III-4 Policie zasahuje

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

I v tomto kole se na vás radní Stínové Prahy obracejí s dalším, ještě naléhavějším, problémem. Ve městě se totiž usídlila mafie a její řádění překročilo únosnou mez. Proto byla městská policie pověřena učinit řádění mafie přítrž. Jak už to ale bývá, není dostatek důkazů o činnosti mafie, a tak se policisté rozhodli nějakou dobu sledovat, jak se mafiáni mezi sebou stýkají. Mafiáni jsou však prohnaní a nechodí jen po ulicích, ale využívají ke svým přesunům i kanalizační systém města. Do kanalizace je tedy třeba rozestavit policejní hlídky tak, aby bylo zamezeno tajným kontaktům mezi mafiány. Přesněji, je potřeba, aby na každé cestě mezi domy dvou mafiánů byla alespoň jedna policejní hlídka.

Tento nelehký úkol naštěstí zjednodušuje fakt, že kanalizačním systémem Stínové Prahy lze mezi každými dvěma domy projít právě jedním způsobem. Takže pokud se má mafián dostat kanalizací z jednoho místa na druhé, má jen jedinou možnost, kudy kanalizací projít (pokud nechce jít žádným místem dvakrát). Speciálně to tedy znamená, že kanalizace má „acyklickou” strukturu a je souvislá, jako např. kanalizační systém na obrázku.

Vaším úkolem je napsat program, který pro daný popis kanalizačního systému a seznam domů ve vlastnictví mafiánů určí minimální počet hlídek, které je nutné do kanalizačního systému rozmístit tak, aby na každé cestě mezi dvěma domy mafiánů byla alespoň jedna hlídka. Hlídky lze umísťovat pouze do míst větvení, tj. hlídka nemůže být umístěna uprostřed stoky. Speciálně hlídka, která je umístěna ve větvení, kam je napojen dům některého z mafiánů, odděluje tento dům od všech ostatních domů.

Vstup:

Na prvním řádku vstupního souboru policie.in jsou dvě celá čísla n (3≤n≤100,000) a p (2≤p<n) oddělená jednou mezerou. Číslo n udává počet větvení v kanalizačním systému – větvením rozumíme buď slepý konec nějaké stoky (napojený na dům, který ale nemusí patřit mafiánovi) nebo křižovatku, ze které vedou alespoň dvě stoky. Kanalizační systém města je pak tvořen n-1 stokami, z nichž každá spojuje dvě větvení. Číslo p udává počet domů, které jsou ve vlastnictví mafiánů.

Větvení v kanalizaci jsou očíslována přirozenými čísly od 1 do n. Domy jsou do kanalizace připojeny jen v místech větvení. Na každém z následujících n-1 řádků vstupního souboru jsou dvě celá čísla a_i a b_i (1≤a_i,b_i≤n), která určují větvení spojená i-tou stokou.

Posledních p řádků vstupního souboru obsahuje vždy jedno celé číslo od 1 do n. Tato čísla jsou navzájem různá a určují čísla větvení v kanalizaci, kam jsou napojeny domy mafiánů.

Výstup:

Váš program má do výstupního souboru policie.out vypsat nejmenší možný počet míst, která je třeba obsadit hlídkou, aby na cestě mezi každými dvěma domy mafiánů byla alespoň jedna hlídka.

Příklad:

policie.in

8 5
1 2
1 3
1 4
1 5
5 6
5 7
7 8
2
3
4
6
7

policie.out

2

  (Hlídky je možné umístit na větvení s čísly 1 a 5.)

P-III-5 Rybka

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

Za horkých bezmračných letních dní se voda v rybníce Blaťáku někdy skoro vaří. Slunce nemilosrdně žhne a malé rybky se spěchají skrýt do hlubších a chladnějších částí rybníka. Jen rybka Julka se opozdila za ostatními a už skoro umdlévá.

Taková choulostivá malá rybka, jako je Julka, snáší jen určitý rozsah teplot, řekněme t₁ až t₂ (včetně krajních hodnot). Ráno mají různé části rybníka různou teplotu a jakmile vyjde slunce, všechny části rybníka se ohřívají stejně rychle, a to o 1 stupeň za 1 časovou jednotku. Rybník Blaťák je obdélníkový a je rozdělen na mxn stejně velkých čtvercových polí. Pole na pozici [i,j] má ráno teplotu T[i,j] stupňů (1≤i≤m, 1≤j≤n). Julka je ráno na pozici [J_x,J_y] a potřebovala by se dostat do bezpečí na pozici [C_x,C_y]. Julka se za každou časovou jednotku posune na jedno ze čtyř přes hranu sousedících čtvercových polí nebo zůstane stát. Pak se vždy teplota všech polí zvýší o 1 stupeň.

Samozřejmě se rybička cestou nesmí přehřát ani nachladit, tj. pole, kde se Julka vyskytuje, musí mít teplotu T, t₁≤T≤t₂. Tato teplota musí být dodržena jak v okamžiku, když Julka na pole vplouvá, tak když jej opouští (mezi čímž se teplota zvýšila alespoň o 1 stupeň). Vyjímku tvoří jen cílové pole, na které smí vplout nezávisle na jeho teplotě a tím se dostat do bezpečí. Rybka Julka nesmí samozřejmě na své cestě opustit rybník.

Napište program, který dostane na vstupu Julčin teplotní rozsah < t₁,t₂> (0≤t₁<t₂≤10⁶), velikost Blaťáku mxn (1≤m,n ≤1,000), počáteční a cílovou pozici Julky [J_x,J_y] a [C_x,C_y] (1≤J_x,C_x≤m,1≤J_y,C_y≤n) a počáteční teplotu každého pole rybníka T[i,j] (0≤T[i,j]≤10⁶) a najde pro naši malou rybku cestu do bezpečí respektující teplotní omezení či zjistí, že taková cesta neexistuje. Nalezená cesta má být nejrychlejší možná, tj. má trvat co nejméně časových jednotek. Pokud existuje více nejrychlejších cest, program může vypsat libovolnou z nich. Můžete předpokládat, že všechny teploty t₁, t₂ a T[i,j] jsou celá čísla. Navíc také můžete předpokládat, že rybka je na počátku v poli s pro ni přijatelnou teplotou a že počáteční pole je různé od cílového.

Vstup:

Na prvním řádku vstupního souboru rybka.in jsou čtyři celá čísla m, n, t₁ a t₂ oddělená mezerami, na druhém řádku jsou pak souřadnice J_x, J_y, C_x a C_y. Všechna čísla m, n, t₁, t₂, J_x, J_y, C_x a C_y splňují výše uvedená omezení. Rybník Blaťák je orientován tak, že pole se souřadnicemi [i,j] sousedí severní hranou s polem se souřadnicemi [i,j-1], jižní hranou s polem se souřadnicemi [i,j+1], západní hranou s polem [i-1,j] a východní hranou s polem [i+1,j]. Posledních n řádků vstupního souboru popisuje počáteční teploty jednotlivých částí rybníka, na řádku j+2 se tedy nacházejí čísla T[1,j],T[2,j],T[3,j],..,T[m,j] vzájemně oddělená mezerami.

Výstup:

Do souboru rybka.out vypište Julčinu cestu jako posloupnost pokynů pro pohyb rybky oddělených mezerami. Pokyn je buď jeden znak S, J, V nebo Z, který určuje směr pohybu rybky, nebo kladné číslo udávající počet časových jednotek, po které se rybka nepohybuje. Jednotlivé pokyny jsou odděleny jednou mezerou. Výstupní soubor nesmí obsahovat dvě čísla za sebou a poslední pokyn, který obsahuje, musí být pokynem k pohybu rybky. V případě, že cesta neexistuje, vypište do výstupního souboru řádek s textem „Chudak Julka!”.

Příklad:

rybka.in

3 4 10 20
2 2 3 4
9 7 13
0 18 15
1 15 19
2 3 0

rybka.out (jedna z více možností)
V S 1 Z Z 5 J J J V V

rybka.in

3 2 20 30
1 1 3 1
25 13 25
27 24 0

rybka.out

Chudak Julka!