Pátá série třicátého čtvrtého ročníku KSP
Celý leták, který posíláme také papírově, v PDF.
Dostává se k vám poslední (páté) číslo hlavní kategorie letošního 34. ročníku KSP.
Opět se můžete těsit na dvě praktické a dvě teoretické úlohy a také na závěr Manimového seriálu. Společně s termínem této série pak také končí prodloužený termín všech předchozích dílů seriálu a po této sérii zveřejníme ke všem dílům jejich řešení.
Za úspěšné řešení KSP můžete být přijati na MFF UK bez přijímacích zkoušek. Úspěšným řešitelem se stává ten, kdo získá za celý ročník (této kategorie) alespoň 50 % bodů. Také každému řešiteli, který v tomto ročníku z každé série dostane alespoň 5 bodů, darujeme KSP propisku, blok, nálepku na notebook a možná i další překvapení.
- Termín série: neděle 12. června ve 32:00 (tedy další ráno v 8:00)
- Odevzdávání: elektronicky přes Odevzdávátko
- Jak řešit: viz Návod na teoretické úlohy a Návod na praktické úlohy
- Dotazy ohledně zadání: posílejte na ksp@mff.cuni.cz, nebo se ptejte na Discordu KSP.
- Odměna série: Každému, kdo získá aspoň 2 body z každého dílu seriálu, pošleme sladkou odměnu.
Zadání úloh
- 34-5-1: Lehátka
- 34-5-2: Veletrh
- 34-5-3: Jednoznačné cestování
- 34-5-4: Dělení ve velkém
- 34-5-S: Manimujeme – vlastní animace a pluginy
34-5-1 Lehátka (9 bodů)
Šéf prázdninového resortu pro samotářské hrochy řeší vážný problém! Doslechl se, že by k němu mělo následující den dorazit H hrochů, kteří u něj budou chtít strávit co nejvíce samotářskou dovolenou u moře. Se společným stravováním není problém, každý hroch bude snídat a večeřet jindy. Ale vyskytl se velký problém s lehátky na pláži.
Hroši by totiž nejraději trávili většinu dne poleháváním v lehátku na pláži … což ale znamená, že se jich ve stejnou chvíli na pláži sejde mnoho. Lehátka už jsou na pláži rozestavěná a je jich určitě více než H, ale posunout už je bohužel nejde, to by si zase stěžovala estetická prázdninová komise pro rozmístění lehátek. Jediné, co šéf resortu může udělat, je určit, která z lehátek obsadí, aby samotářští hroši byli co možná nejdále od všech ostatních.
Lehátka jsou rozestavěná v jedné linii na dlouhé pláži (a jejich rozestavění rozhodně nemusí být pravidelné). Pomozte šéfovi resortu z L lehátek vybrat H takových, aby vzdálenost mezi dvojicí nejbližších vybraných lehátek byla co největší možná (jinými slovy cílem je maximalizovat minimum ze vzdáleností mezi libovolnými vybranými lehátky).
Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.
Formát vstupu: Na prvním řádku dostanete čísla H a L udávající počet hrochů, kteří přijedou, a počet již rozestavěných lehátek na pláži. Bude vždy platit H < L. Na dalších L řádcích pak dostanete celočíselné vzdálenosti lehátek od začátku pláže uspořádané od nejbližšího lehátka k nejvzdálenějšímu. Na pozice lehátek může být nutný 64-bitový datový typ.
Formát výstupu: Na prvním řádku uveďte jedno celé číslo udávající nalezenou minimální vzdálenost mezi vybranými lehátky. Na dalších H řádcích pak vypište indexy vybraných lehátek ze vstupu (indexujeme od nuly).
4 6 0 2 6 7 9 14
3 0 2 4 5
Příklad: Vybraná lehátka jsou na pozicích 0, 6, 9, 14 a minimální vzdálenost mezi nimi je 3. Větší minimální vzdálenosti již dosáhnout nelze.
34-5-2 Veletrh (12 bodů)
Kevin se Sárou a Petrem se dostali na řešitelský veletrh – veletrh všemožných udělátek, které můžou pomoci řešitelům korespondenčních seminářů v řešení úloh. Věci jako Věčná řešitelova propiska, které nedojde inkoust těsně před deadlinem, Čajomilův samomíchací hrneček na silný čaj pro dlouhé noční řešení úloh, Vyšlův generátor protipříkladů na eliminaci špatných řešení nebo třeba MyšAnOrg – Myšlenkový analyzátor orgů, který prozradí, na co přesně orgové mysleli, když vymýšleli zadání.
Všem třem jdou oči kolem dokola ze všech těch tajů a vymožeností. A tak se rozhodli toho vidět co možná nejvíce. Povedlo se jim sehnat plánek celého veletržního areálu, který se sestává z mnoha místností a cest mezi nimi. Někdo chytrý navíc do plánku poznamenal doby přesunu skrz jednotlivé chodby a to, že některé z nich fungují jenom jednosměrně (Kevin se už těší na jízdu skluzavkou z nejvyššího patra až do suterénu).
Veletrh funguje tak, že v určitých místnostech v určitých časech probíhají události (třeba představení nějakého produktu nebo ukázka, jak ho co nejlépe použít k řešení úloh). Každá událost někdy začíná a trvá celý počet minut.
Protože Kevin, Sára ani Petr nezvládnou předem říci, jestli bude zajímavější Nakopávací připomínač deadlinů nebo snad Deštiodolný zápisník, tak se rozhodli, že budou svoji cestu po veletrhu plánovat čistě podle počtu minut, které se jim povede strávit na nějaké události.
Všechny přesuny mají délku v celých minutách a v libovolné místnosti je možné čekat nějaký celý počet minut. Každá celá minuta strávená v místnosti s probíhající událostí se počítá (bez ohledu na to, jestli jsme přišli na začátek nebo do prostředka události).
Vaším úkolem bude v zadaném grafu veletrhu a pro zadaný rozpis událostí najít co nejlepší trasu (kterými cestami jít a ve kterých místnostech jak dlouho čekat) tak, abyste dosáhli co největšího počtu minut stráveného na nějaké události. Začínáte v místnosti 0 v čase 0 a skončit můžete kdekoliv.
Toto je praktická open-data úloha. V odevzdávátku si necháte vygenerovat vstupy a odevzdáte příslušné výstupy. Záleží jen na vás, jak výstupy vyrobíte.
Formát vstupu: Na prvním řádku vstupu dostanete čísla N, M a U udávající počet místností (vrcholů grafu), chodeb mezi nimi (hran) a událostí. Místnosti číslujeme od 0.
Na dalších M řádcích pak bude vždy trojice čísel Ai, Bi a Ci popisující orientovanou hranu z místnosti Ai do místnosti Bi, jež trvá projít Ci minut.
A nakonec na dalších U řádcích budou trojice čísel Mi, Ti a Di udávající číslo místnosti Mi, ve které se koná i-tá událost, čas začátku události Ti (v celých minutách od začátku veletrhu) a délku trvání události Di v celých minutách. V téže místnosti nikdy neprobíhá více událostí současně. Slibujeme, že pro první dvě třetiny vstupů budou délky událostí vždy 1.
Formát výstupu: Na první řádek výstupu uveďte jedno celé číslo udávající
největší počet minut událostí, které mohou Kevin se Sárou a Petrem stihnout.
Pak uveďte kroky vámi nalezené trasy přes veletrh, každý krok na jednom řádku.
Pro přesun do jiného vrcholu vypište znak P, mezeru a pak index cílového vrcholu (musí existovat hrana
ze současného do cílového vrcholu). Pro čekání v současném vrcholu vypište
znak C, mezeru a nenulový počet minut, které čekáte v tomto vrcholu.
3 4 5 0 1 2 0 2 6 1 2 5 2 0 1 0 1 4 1 4 5 1 10 2 2 0 3 2 4 5
8 C 3 P 1 C 7
Kevin nejprve stráví 3 minuty ve vrcholu 0. Stihne tam první 2 minuty
události 0 1 4, načež odejde do vrcholu 1. Tam dorazí v čase 5,
tedy během události 1 4 5. Z té zažije 4 minuty, pak si dá minutu
pauzu a nakonec v tomtéž vrcholu zažije celou událost 1 10 2.
Celkem tedy stihne 8 minut událostí.
34-5-3 Jednoznačné cestování (12 bodů)
Organizátory řešitelského veletrhu po prvním dni udivilo, že nemají dostatek peněz na provoz veletrhu i následující dny. Proto se rozhodli, že se za průchody chodbami bude platit. Na rozdíl od předchozí úlohy je každou chodbou možné chodit oběma směry a poplatek v obou směrech bude totožný.
Také zjistili, že lidé na veletrhu mnohdy netuší, kudy se vydat do jaké místnosti. Rádi by určili ceny za průchod chodbami tak, aby existovala právě jedna nejlevnější cesta mezi každou dvojicí místností. Současně ale chtějí, aby se účastníci veletrhu moc nenachodili. Nejlevnější cesta mezi dvojici místností by tedy vždy měla být i nejkratší.
Organizátoři po dlouhém zkoušení přiřazování cen za průchody chodbou stále nemůžou najít vyhovující nacenění. Rozhodli se tedy, že požádají o pomoc řešitele (těch mají totiž na řešitelském veletrhu opravdu hodně).
Vašim úkolem tedy bude pro zadaný neorientovaný graf přiřadit hranám kladné celočíselné ceny tak, aby pro každou dvojici vrcholů existovala pouze jedna cesta mezi nimi s nejmenším součtem cen a ta byla současně i tou nejkratší (obsahovala nejmenší možný počet hran).
Vaše řešení bude hodnoceno nejen podle časové složitosti, ale hlavně podle toho, jak velká čísla hranám bude přidávat. Jakožto účastníci totiž chcete platit co nejméně. Zajímá nás ovšem jen asymptotický odhad největší použité ceny podle počtu vrcholů nebo hran grafu. Může se jednat i o hodně velká čísla. V odhadu složitosti algoritmu však můžete uvažovat, že s takto velkými čísly lze stále provádět základní operace v konstantním čase.
34-5-4 Dělení ve velkém (12 bodů)
Ondra se rozhodl, že začne trénovat na soutěžní programování.
Otevřel první úložku, proskenoval zadání a nakódil řešení. Jenže ouha, dostal verdikt Time Limit Exceeded, tedy že jeho řešení je příliš pomalé.
Předpokládá, že problém je v kusu kódu:
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
// V Céčku '/' znamená celočíselné dělení,
// tedy totéž co '//' v Pythonu.
ans += a[i] / a[j];
}
}
Proměnná n (velikost pole a) může být totiž podle zadání velká až 106,
a tedy řešení v čase O(n2) je příliš pomalé.
Ondra tuší, že by se dalo využít toho, že hodnoty v poli jsou kladná celá čísla menší než 106, jenže neví jak. Poradíte mu?
34-5-S Manimujeme – vlastní animace a pluginy (15 bodů)
Vlastní animace
V tomto díle se, jak jsme si slíbili v minulém, naučíme vytvářet vlastní animace. Hodí se všude tam, kde Manimem vestavěné animace nestačí (viz minulý díl a funkceMoveAndFade).
Pojďme si vytváření vlastní animace ukázat na příkladu:
from manim import *
class Roll(Animation):
"""Animace, která otočí objekt o daný úhel, trochu ho při tom zmenší a posune se do strany."""
def __init__(self, mobject: Mobject, angle, direction, scale_ratio=0.85, **kwargs):
"""Konstruktor. Inicializuje potřebné věci animace."""
# bude se nám hodit původní verze objektu, který animujeme
# (v animaci ho otiž budeme měnit)
self.original = mobject.copy()
self.scale_ratio = scale_ratio
self.angle = angle
self.direction = direction
super().__init__(mobject, **kwargs)
def interpolate_mobject(self, alpha: float) -> None:
"""Funkce, která se volá každý snímek, aby se animace animovala."""
# alpha je od 0 do 1, ale animace mohla jako parametr dostat rate funkci
# proto je třeba tuto funkci na alphu aplikovat, aby se animace chovala správně
actual_alpha = self.rate_func(alpha)
# chceme, aby objekt měl na začátku scale 1, v půlce scale_ratio a na konci 1
# tohle možná není nejelegantnější způsob, ale funguje
scale_alpha = 1 - (1 - self.scale_ratio) * 2 * (0.5 - abs(actual_alpha - 0.5))
# chceme, aby objekt měl na začátku startovní pozici, pak se posunul a nakonec se vrátil
direction_alpha = there_and_back(actual_alpha)
self.mobject.become(self.original.copy())\
.rotate(actual_alpha * self.angle)\
.scale(scale_alpha)\
.shift(self.direction * direction_alpha)
class Dissolve(AnimationGroup):
"""Animace, která 'zmizí' objekt. Používáme zde AnimationGroup,
jelikož animace mizení je tvořena dvěma různými animacemi."""
def __init__(self, mobject: Mobject, **kwargs):
"""Konstruktor. Inicializuje potřebné věci animace."""
self.original = mobject.copy()
# způsob, jak do animate syntaxu dostaneme argumenty
a1 = mobject.animate.scale(0)
a2 = Flash(mobject, color=mobject.color)
super().__init__(a1, a2, lag_ratio=0.75, **kwargs)
class StarFox(Scene):
def construct(self):
square = Square(color=BLUE, fill_opacity=0.75).scale(1.5)
self.play(Roll(square, angle=PI, direction=LEFT * 0.75))
self.play(Roll(square, angle=-PI, direction=RIGHT * 0.75))
self.play(Dissolve(square))
Na příkladu jsou vidět dvě nové animace.
První (Roll) dědí ze třídy Animation [doc] a definuje funkci interpolate_mobject [doc], která je scénou volána každý snímek, aby animovaný objekt patřičně změnila.
Druhá (Dissolve) dědí ze třídy AnimationGroup [doc] (která sama dědí ze třídy Animation [doc]) a slouží k definování složených animací.
Pluginy
Když už umíme vytvářet vlastní objekty a animace, tak se nabízí se seznámit s pluginy [doc]. Pluginy rozšiřují základní funkcionalitu Manimu řadou různých způsobů, ať už se jedná o definování nových objektů a tříd, či o editor usnadňující vývoj Manimových animací. V tomto díle se seznámíme s několika zajímavými pluginy.Fyzika
První je plugin manim-physics [GitHub] [doc], který (jak jméno napovídá) přidává objekty pro práci s několika různými odvětvími fyziky.
Instalovat jej můžete přes příkaz pip install manim-physics (v Jupyter notebooku pro tento díl již nainstalovaný je).
Zde je několik příkladů zajímavých fyzikálních simulací vytvořených s pomocí tohoto pluginu:
from manim import *
# příklad z https://github.com/Matheart/manim-physics
# SpaceScene je třída podporující fyzikální interakce
class FallingObjectsExample(SpaceScene):
def construct(self):
circle = Circle().shift(UP)
circle.set_fill(RED, 1)
circle.shift(DOWN + RIGHT)
rect = Square().shift(UP)
rect.rotate(PI / 4)
rect.set_fill(YELLOW_A, 1)
rect.shift(UP * 2)
rect.scale(0.5)
ground = Line([-4, -3.5, 0], [4, -3.5, 0])
wall1 = Line([-4, -3.5, 0], [-4, 3.5, 0])
wall2 = Line([4, -3.5, 0], [4, 3.5, 0])
walls = VGroup(ground, wall1, wall2)
self.add(walls)
self.play(
DrawBorderThenFill(circle),
DrawBorderThenFill(rect),
)
# až doposud se jednalo o normální Manim kód
# nyní použijeme funkce, které objektům přidají fyziku
self.make_rigid_body(rect, circle) # čtverec a kruh jsou rigidní (hýbou se)
self.make_static_body(walls) # zdi jsou statické (nehýbou jse)
# nyní počkáme - funkce výše přidaly objektům updatery
self.wait(5)
from manim import *
# zde stačí Scene, protože používáme pouze nové objekty
# příklad upravený z https://github.com/Matheart/manim-physics
# POZOR: kód trvá postavit opravdu dlouho, doporučuji používat nižší kvalitu
class ElectricFieldExample(Scene):
def construct(self):
charge1 = Charge(-1, LEFT + DOWN)
charge2 = Charge(2, RIGHT + DOWN)
charge3 = Charge(-1, UP)
def rebuild(field):
"""Funkce která přestaví elektrické pole."""
field.become(ElectricField(charge1, charge2, charge3))
field = ElectricField(charge1, charge2, charge3)
self.add(field, charge1, charge2, charge3)
self.play(Write(field), FadeIn(charge1), FadeIn(charge2), FadeIn(charge3))
field.add_updater(rebuild)
self.play(
charge1.animate.shift(LEFT),
charge2.animate.shift(RIGHT),
charge3.animate.shift(DOWN * 0.5),
run_time=2,
)
from manim import *
# příklad upravený z https://github.com/Matheart/manim-physics
# OPĚT POZOR: kód trvá postavit opravdu dlouho, doporučuji používat nižší kvalitu
class MagnetismExample(Scene):
def construct(self):
current1 = Current(LEFT * 2.5)
current2 = Current(RIGHT * 2.5, direction=IN)
def rebuild(field):
"""Funkce která přestaví magnetické pole."""
field.become(MagneticField(current1, current2))
field = MagneticField(current1, current2)
self.play(Write(field), FadeIn(current1), FadeIn(current2))
field.add_updater(rebuild)
self.play(
Rotate(current1, about_point=ORIGIN, angle=PI),
Rotate(current2, about_point=ORIGIN, angle=PI),
run_time=2,
)
from manim import *
# příklad upravený z https://github.com/Matheart/manim-physics
# opět používáme SpaceScene, jelikož animujeme fyzikální interakce
class PendulumExample(SpaceScene):
def construct(self):
# pozice kuliček pendula
bob_positions = [RIGHT * 1.5 + UP, RIGHT * 1.5 + UP * 2]
pendulum = MultiPendulum(
*bob_positions,
pivot_point=UP,
bob_style={"color": WHITE, "fill_opacity": 1, "radius": 0.15},
)
self.make_rigid_body(pendulum.bobs) # kuličky pendula jsou rigidní
pendulum.start_swinging() # a spojené
self.add(pendulum)
# budeme sledovat cestu obou kuliček
for i, bob in enumerate(pendulum.bobs):
self.bring_to_back(TracedPath(bob.get_center, stroke_color=DARK_GRAY))
self.wait(12)
Chemie
Druhý je plugin chanim [GitHub], který implementuje objekty pro animování chemických reakcí.
Instalovat jej můžete, obdobně jako předchozí plugin, přes pip install chanim (v Jupyter notebooku opět již nainstalovaný je).
Zde je příklad animování chemických sloučenin s pomocí tohoto pluginu:
from manim import *
class ChanimExample(Scene):
def construct(self):
# chemická sloučenina
# interně využívá ChemFigový syntax (https://www.ctan.org/pkg/chemfig)
chem = ChemWithName(
"*6((=O)-N(-CH_3)-*5(-N=-N(-CH_3)-=)--(=O)-N(-H_3C)-)",
"Caffeine"
)
chem.move_to(ORIGIN)
self.play(chem.creation_anim())
Úlohy
K odevzdávání úloh lze animaci vytvořit buď online přímo v Jupyteru pro tento díl (na konci dokumentu je kostra pro každou z úloh, do které ji jde přímo doprogramovat), nebo i lokálně, pokud máte nainstalovný Manim.
Odevzdávejte celý zdrojový kód v zazipovaném (a nezaheslovaném) archivu.
Úkol 1 – Vaše hezká animace [15b]
Naprogramujte animaci něčeho, co vás zajímá :).
Můžete použít cokoliv, co jste se v průběhu seriálu (i mimo) naučili. Animace by měla být rozumně dlouhá (alespoň 10 vteřin, ne více než 5 minut).
Plný počet bodů dostane každá animace, na které je vidět snaha vytvořit něco pěkného. Zajímavé nápady jsou například fraktály, animace algoritmů a datových struktur, simulace nějakého fyzikálního jevu nebo grafické odvození matematické konstanty.