Čtvrtá série dvanáctého ročníku 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] až 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í