Čtvrtá série dvanáctého ročníku KSP

Termín odeslání Vašich řešení této série jest určen na 28. dubna 2000. Ř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.

Zadání úloh


12-4-1 Magický zapletenec (10 bodů)


Jak víte, nebo možná nevíte, čarodějové si schovávají svou moc do různých talismanů, prstenů či náhrdelníků. Nejinak to dělal i náš čaroděj Kern. Jedno z jeho kouzel se mu ale poněkud vymklo z ruky a mimo jiné způsobilo, že se v okolí objevil kvákající kocour, mňoukající hrnec a ušatá žába. Nejvíce ale čarodějovi vadilo, že se mu úplně zašmodrchal jeho kouzelný řetízek a stal se tak naprosto nepoužitelným. Protože Kern nehodlal riskovat opravu náhrdelníku magickými cestami, jal se rozmotávat náhrdelník ručně. Brzy ale zjistil, že kouzlo mu pospojovalo některé kroužky, které spojeny nebyly a naopak rozpojilo kroužky, které spojeny byly. Nezbývá tedy, než některé kroužky otevřít, přesunout a pak zase uzavřít. Protože se tím ale řetízek poškozuje, je třeba otevřít co nejmenší počet kroužků. A to už je úloha pro vás. Na vstupu je dán počet kroužků N a zašmodrchaný řetízek. Ten je popsán dvojicemi kroužků, které jsou spojeny (kroužky si budeme číslovat od 1 do N). Vaším úkolem je zjistit minimální počet kroužků, které je třeba rozpojit, aby ze zamotaného řetízku vznikl jeden jednoduchý řetízek.

Příklad 1:

Počet kroužků: 4
Propojení: 1-2, 2-3, 2-4
Je třeba rozpojit alespoň 1 kroužek.
(např. 4, který se pak připojí za 3)
Příklad 2:
Počet kroužků: 5
Propojení: 1-2, 2-3, 3-4, 4-1, 1-5
Je třeba rozpojit alespoň 1 kroužek.
(např 1 - 4 z něj pak můžeme vyvléknout)

Řešení


12-4-2 Pyrus Achras (10 bodů)


Pan Hruška měl sad. Jednoho dne se rozhodl, že si do sadu vysadí novou odrůdu svého nejoblíbenějšího stromu – hrušně – a vyhlédl si pro ni pěkné místo. Bohužel se koupí nového stromu poněkud finančně vyčerpal, a tak již nemá na přikoupení pletiva na plot, který si kolem svého sadu staví. Potřeboval by tedy zjistit, jestli jím vybrané místo leží uvnitř projektovaného oplocení nebo nikoliv. A to je již úkol pro vás.

Na vstupu je počet stromů N a jejich souřadnice. Dále jsou dány souřadnice vybraného místa. Oplocení je projektováno jako nejmenší možné – tedy nejmenší konvexní k-úhelník obsahující všechny dané stromy. Váš program má zjistit, zda vybrané místo leží uvnitř nebo vně příslušného k-úhelníka.

Příklad 1:

Stromů: 5
Pozice: (0, 0), (2, 0), (0, 2), (1, 1), (2, 3)
Nový strom: (2.5, 0.5)
Nový strom leží mimo.
Příklad 2:
Stromů: 3
Pozice: (0, 0), (2, 0), (1, 2)
Nový strom: (1, 1)
Nový strom leží uvnitř.

Řešení


12-4-3 Šachová šlamastika (10 bodů)


Bílá dáma si objednala dláždění do své komnaty. Jak jinak než po vzoru šachovnice. Dlaždiči ovšem místo krásné a pravidelné šachovnice vydláždili na podlahu jiné ornamenty a dáma je teď nešťastná. Bílý král si vás tedy najal, abyste nalezli v komnatě největší oblast, kde by se královna mohla cítit jako doma (tedy na šachovnici).

Na vstupu jsou dány rozměry komnaty M a N a dále popis vydláždění komnaty. Vydláždění je popsáno maticí M×N obsahující nuly a jedničky. Nula je na místě bílého políčka, jednička na místě černého. Vaším úkolem je napsat program, který v dané matici nalezne obdélník s největším obsahem takový, že se v něm budou střídat barvy jako na šachovnici.

Příklad:

Rozměry: 5, 6
00101
11001
01010
10001
11111
Největší šachová podmatice má obsah 6.
Levý horní roh: 4, 2. Rozměry: 2, 3.

Řešení


12-4-4 Barevné intervaly (11 bodů)


Jsou dány neprázdné intervaly (a1, b1)… (an, bn). Každý z intervalů se pokusíme obarvit nějakou barvou z dané sady tak, aby žádné dva intervaly s neprázdným průnikem neměly stejnou barvu. Je asi zřejmé, že ne vždy to jde. Například intervaly (1, 3), (2, 4) a (1, 4) pomocí dvou barev obarvit nelze.

Vaším úkolem je napsat program, který pro dané intervaly zjistí nejmenší počet barev k takový, že intervaly jdou obarvit a dále nalezne příslušné obarvení (barvy pro jednoduchost označujte čísly jedna až k).

Příklad:

Intervaly:
1, 3
2, 4
1, 4
2, 3
0, 2
Jsou potřeba 4 barvy.
Obarvení je:
(1, 3) = 1
(2, 4) = 2
(1, 4) = 3
(2, 3) = 4
(0, 2) = 2

Řešení


12-4-5 PRAM (10 bodů)


V této sérii budeme řešit úlohy dvě, ale zato pouze na P-CRCW PRAMu.

  1. Vytvořte program, který dostane zadanou posloupnost n celých čísel a spočítá posloupnost jejích částečných součtů, tj. a1, a1+a2, a1+a2+a3,… Délka posloupnosti bude při spuštění uložena v gmem[0] a posloupnost sama pak v buňkách gmem[1]gmem[n]. Obsah paměťových buněk před začátkem výpočtu by tedy mohl být například: 5, 4, 0, 4, -2, 3. Obsah paměťových buněk po skončení výpočtu by pak měl být: 5, 4, 4, 8, 6, 9.
  2. Vytvořte program, který jako vstup obdrží číslo n a spočte horní celou část jeho dvojkového logaritmu. Vstupní číslo je zadáno v gmem[0]; výsledek by měl být po skončení výpočtu uložen též v gmem[0]. Váš algoritmus by měl používat právě n procesorů. Je ale samozřejmě možné, že některé z nich nemusí vůbec počítat a mohou se tedy hned v prvním kroku zastavit instrukcí halt.
Obě zadané úlohy řešte pouze na P-CRCW PRAMu.

Řešení