Zadania na kółko 07.02
Odśnieżanie
W nieskierowanym, ważonym, spójnym grafie wyróżniono cztery wierzchołki. Należy usunąć część krawędzi z grafu tak, żeby nadal istniały ścieżki pomiędzy każdą parą wyróżnionych wierzchołków i żeby suma wag krawędzi, które pozostały w grafie, była jak najmniejsza.
Liczba wierzchołków, krawędzi <= 2 * 10^5
Szkolne porachunki
Jasio ostatnio zadarł z dresami. Niestety, planują oni zamach na niego. Jasio wie, że należy się od nich trzymać z daleka. Niestety, trzeba chodzić do szkoły. Na szczęście dresy do szkoły nie chodzą, więc siedzą w domu nieruszając się (póki Jasio nie przejdzie odpowiednio blisko).
Dana jest prostokątna mapa z zaznaczoną pozycją Jasia, pozycjami dresów, pozycją szkoły oraz pozycjami przeszkód. Odległość między pozycjami mierzymy w metryce Manhattan. Wyznacz największą możliwą odległość od najbliższego dresa na mapie na drodze Jasia do szkoły.
Wysokość i szerokość mapy <= 1000
Spokój
Hotel, w którym odbywa się obóz informatyczny, można przedstawić jako graf (krawędzie to korytarze, wierzchołki to pokoje lub skrzyżowania korytarzy). Każdemu gimbusowi na obozie należy przydzielić dwa różne pokoje - jeden do pracy, drugi do spania. Dodatkowo każdy gimbus musi mieć przydzieloną swoją jednoznaczną trasę (ścieżkę) między pokojami, po której będzie się poruszać. Należy tak przydzielić gimbusom pokoje i trasy, aby trasy dowolnych dwóch gimbusów były rozłączne krawędziowo. Powiedz, ile maksymalnie gimbusów można wziąć na obóz.
Liczba wierzchołków, krawędzi w grafie <= 50000.
Ustawka
W grze Ustawka bierze udział 2n
graczy podzielonych na dwie drużyny po n
osób. Każda z uczestników wybiera sobie jeden cel z przeciwnej drużyny. Zastanawiamy się, czy w trakcie zabawy znajdzie się elitarny zbiór E
, taki że:
- Żaden uczestnik z
E
nie zostanie zaatakowany przez innego uczestnika zE
. - Każdy uczestnik, który nie należy do
E
zostanie zaatakowany przez kogoś zE
.
Mając dany zbiór atakujących się uczestników, znajdź zbiór E
wiedząc, że taki istnieje.
n <= 100 000