FRAKTAL - konkurs programistyczny (SPOJ)

Omówienie zadań

Ropuszka
Góry i doliny
Snake case na camel case
Szczęśliwa kurka
Dzwon
Świąteczny rachunek
Mecz
ONP ERROR
Wieża
Nie lubię nieparzystych
Odstępy
Napad
Gra w odejmowanie
Kostka
Aneta, Maciek, karnisz i żabki
Ucieczka z biura
Turysta
Upał
Naszyjnik
Jarmark świąteczny

Mecz

Znając przebieg meczu, określ czy był ciekawy, czy nie.

Mecz jest nudny, jeżeli w którymkolwiek momencie Jaś nudził się podczas meczu.

W rozwiązaniu należy pamiętać, że:

Minuty meczu numerujemy od 1 do N.
Zainteresowanie nie kumuluje się. Dwie bramki w odstępie minuty, nie przedłużają zainteresowania o 30 minut.
Początkowe zainteresowanie meczem trwa 10 minut, więc Jaś zaczyna się nudzić od początku 11 minuty.
Mecz trwa do końca N-tej minuty, więc ta ostatnia minuta też musi być dla Jasia ciekawa.

W zadaniu najważniejsze jest zrozumienie, jak zachowuje się zainteresowanie Jasia.

Jeżeli ciekawa sytuacja (przedłużająca uwagę Jasia o K minut), wydarzy się w minucie X (a dokładnie na początku minuty X), to utrzyma uwagę Jasia do końca tej minuty i przez K-1 kolejnych.
Jeżeli kolejne zdarzenie ma miejsce na początku X+K minuty, zainteresowanie jest podtrzymane.

Przykład:

Jeżeli w 12 minucie padnie bramka (15 minut uwagi), to Jaś straci zainteresowanie meczem na początku 27 minuty.
Jeżeli do 27 minuty nie wydarzy się nic ciekawego, to od 27 minuty mecz będzie nudny.
Jeżeli w 25 minucie zostanie wykonane długie podanie (laga - 7 minut), to uwaga Jasia przedłużona jest do końca 31 minuty. Od 32 minuty będzie się nudził.

Mając powyższe w pamięci należy po kolei przejść po wszystkich sytuacjach na boisku i śledzić co i na jak długo utrzymuje uwagę Jasia.

Ciekawe sytuacje podane są w kolejności chronologicznej, ale ich czas utrzymanej uwagi może się nakładać, więc trzeba to wziąć pod uwagę.

Wróć do listy zadań

ONP ERROR

TBD

Wróc do listy zadań

Wieża

W zadaniu wystarczy zauważyć, że jeśli rozciągniemy bok wieży, to jedna spirala schodów utworzy trójkąt prostokątny, gdzie schody są przeciwprostokątną, obwód wieży - podstawą trójkąta, a wysokość jednej spirali - wysokością trójkąta.

Powyższa obserwacja pozwala policzyć całkowitą długość schodów (należy pamiętać, że schody mogą okrążyć wieżę wiele razy).

Pisząc w C++ należy uważać na możliwość przekroczenia zakresu zmiennych typu int.

Poniższe rzutowanie:

int r;
(long long)(r*r)

może spowodować przekroczenie zakresu i w efekcie błędną odpowiedź.

Należy także używać wartości PI zdefiniowanej w bibliotece matematycznej, a nie definiować samemu.

W C++ dostępne jest makro M_PI (#include <cmath>)
W Python można użyć stałej math.pi dostępnej w module math (import math)

Można też wywołać funkcję acos(-1), która zwraca wartość PI.

Wróć do listy zadań

Nie lubię nieparzystych

TBD

Wróć do listy zadań

Odstępy

TBD

Wróć do listy zadań

Napad

W zadaniu musimy policzyć minimalną ilość paliwa potrzebną, żeby wystartować z określonego wierzchołka w grafie, odwiedzić pewien nieokreślony wierzchołek po drodze i dojechać do punktu wyjścia.

Paliwa musi wystarczyć, żeby odwiedzić dowolny wierzchołek w grafie.

W rozwiązaniu skorzystamy z tego, że po przejściu algorytmem Dijkstry przez graf startując od wybranego wierzchołka, otrzymujemy długość najkrótszej ścieżki do każdego z pozostałych skrzyżowań.

Rozwiązanie naiwne:

Naiwne rozwiązanie to uruchomić przeszukiwanie grafu algorytmem Dijkstry startując z każdego skrzyżowania. Dzięki temu dla każdego skrzyżowania wiemy, jaka jest odległość do sklepu oraz odległość do punktu porzucenia samochodu. Rozwiązaniem będzie skrzyżowanie, dla którego suma tych odległości odległości będzie największa.

Rozwiązanie optymalne:

Uruchomienie Dijkstry dla każdego wierzchołka osobno będzie zbyt wolne.

Można jednak zauważyć, że informacja, która jest istotna z tych wszystkich przebiegów to odległość każdego wierzchołka do punktu startowego oraz do punktu końcowego.

A to można policzyć uruchamiając Dijkstrę tylko dwa razy: dla punktu startowego oraz końcowego!

Czyli wystarczy uruchomić Dijkstrę dwa razy: raz od punktu początkowego oraz raz od punktu końcowego. Najdalszym wierzchołkiem będzie ten punkt, dla którego odległość do punktu startowego plus odległość do punktu końcowego będzie największa. Rozwiązaniem będzie ta największa suma odległości.

Wróć do listy zadań

Gra w odejmowanie

Gra w odejmowanie. Zaczynamy od liczby N, od której można odejmować liczby z przedziału [a − b]. Przegrywa ten, kto nie może wykonać kolejnego ruchu.

W zadaniu należy znaleźć optymalną strategię prowadzącą do wygranej, a następnie zagrać w grę z Mistrzem.

Jeżeli na początku gry znajdujemy się w pozycji wygrywającej, to musimy ją utrzymać do końca rozgrywki.
Jeżeli jesteśmy na pozycji przegrywającej, to musimy 'czekać' (ale wciąż grać), aż Mistrz popełni błąd i wyprowadzi nas na pozycję wygrywającą. Od tego momentu musimy grać optymalnie do samego końca.

Przypomnienie:

Pozycja wygrywająca - sytuacja, w której co najmniej JEDEN ruch prowadzi do pozycji przegrywającej.

Pozycja przegrywająca - sytuacja, w której WSZYSTKIE ruchy prowadzą do pozycji wygrywających.

Ocena aktualnej pozycji względem N (podejście bez używania teorii gier)

Załóżmy, że na wejściu pojawią się liczby A i B (minimalna i maksymalna liczba, którą możemy odjąć od N).

Dla wszystkich

N < A

znajdujemy się w pozycji przegrywającej (nie możemy już wykonać żadnego ruchu).

Dla

N ≥ A and N < A + B

znajdujemy się w pozycji wygrywającej (dla każdej wartości N z danego przedziału, jesteśmy w stanie sprowadzić N do wartości N < A).

Dla

N = A + B

znajdujemy się pozycji przegrywającej (zmniejszenie N o dowolną wartość z zakresu [A, B] sprowadza nas do wcześniejszego przypadku).

Dla N > A + B and N < A + B + A

nadal znajdujemy się w pozycji przegrywającej (zmniejszenie N o dowolną wartość z zakresu [A, B] sprowadza na pozycję wygrywającą).

W tej sytuacji można już zauważyć zależność jak rozkładają się pozycje wygrywające i przegrywające w zależności od N, A i B.

Pierwsze A wartości [0 − (A-1)] są pozycjami przegrywającymi.

Następnie jest B wartości wygrywających [A − (A+B-1)].

Następnie jest A przegrywających [(A+B) − (A+B+A-1)].

Następnie jest B wygrywających.

...

itd.

Rozwiązanie

Wiedząć gdzie są pozycje wygrywające i przegrywające, możemy zacząć grać.

Dla każdej wartości N, obliczamy resztę z dzielenia N przez A+B.

R=N%(A+B)

Jeżeli reszta R jest równa lub większa od A, to znajdujemy się na pozycji wygrywającej.
W swoim ruchu należy odjąć: min(R, B) (przejście na pozycję przegrywającą).

Jeżeli reszta R jest mniejsza od A, to gramy dowolną wartość z przedziału [A, B] i czekamy na błąd Mistrza.

Można dobrać liczby początkowe w taki sposób, że Mistrz nie będzie miał możliwości wyprowadzić nas na pozycję wygrywającą, jednak takie testy nie zostały dodane.

Wróć do listy zadań

Kostka

W zadaniu należy policzyć cień rzucany przez dowolnie obrócony sześcian.

Rozwiązanie 1:

Kilka kluczowych obserwacji, które pozwolą rozwiązać zadanie:

promienia idą wzdłuż osi Z, a to oznacza, że cień powstanie na płaszczyźnie XY.
cień powstanie na płaszczyźnie XY, a to oznacza, że współrzędne Z wierzchołków można całkowicie zignorować (nie trzeba dokonywać żadnej skomplikowanej transformacji z 3D do 2D).
współrzędne Z wierzchołków można całkowicie zignorować, a to oznacza, że otrzymujemy zbiór punktów (X, Y) na płaszczyźnie.
cieniem będzie najmniejszy wielokąt, który zawiera w sobie wszystkie odcinki utworzone z wszystkich par punktów (X, Y).
najmniejszy wielokąt, który spełnia powyższe warunki to wypukła otoczka utworzona z punktów.
punktów jest tylko 8, więc dowolna metoda obliczania otoczki pozwala rozwiązać zadanie.

Rozwiązanie 2:

Obserwacja 1: patrząc na kostkę zawsze widzimy co najwyżej jej 3 boki (3 lub mniej. Nigdy nie zobaczymy więcej). 3 pozostałe boki są zawsze niewidoczne.

Patrząc z góry (z perspektywy źródła światła) widzimy tylko 3 ścianki kostki i to właśnie te płaszczyzny generują cień, który musimy policzyć.

Boki są opisane przez 4 punkty w trzech wymiarach, ale dzięki temu, że patrzymy dokładnie z góry, możemy sprowadzić je do figur na płaszczyźnie 2D (współrzędna Z może być zignorowana).

Rzut każdej ścianki będzie w ogólności równoległobokiem. W specjalnych przypadkach może być rombem, kwadratem lub odcinkiem. Kształt figury nie ma znaczenia. Istotne jest to, że będzie to czworobok, w którym przeciwległe ścianki są tej samej długości (może to być czworobok zdegenerowany).

Obserwacja 2: kostka obserwowana z góry i z dołu wygląda dokładnie tak samo. Po sprowadzeniu boków kostki do figur na płaszczyźnie nie musimy się zastanawiać, która ścianka jest widoczna, a która nie. Jeśli jedna ścianka jest widoczna, to będzie istniała też druga taka sama ścianka, która jest niewidoczna.

Czyli, żeby rozwiązać problem wystarczy policzyć sumę pół równoległoboków otrzymanych z zrzutowania ścianek na płaszczyznę XY (po usunięciu współrzędnej Z) i wynik podzielić przez 2. Żeby policzyć pole równoległoboku polecam omównienie zadania Bramka (część druga - iloczyn wektorowy) z Fraktala XV. Obliczenie pola równoległoboku sprawadza się do obliczenia wartości bezwzględnej z iloczynu wektorowego wektorów utworzonych z dwóch siąsiadujących boków.

Ulepszone rozwiązanie 2:

Dodatkowa obserwacja, która pozwala jeszcze uprościć rozwiązanie:

Jeśli weźmiemy dowolny wierzchołek kostki to trzy ścianki, które się z nim stykają, będą to takie same trzy ścianki, jakie widzimy patrząc na kostkę z góry (nie będą to te same ścianki, ale generowany cień będzie identyczny). Zasada ta nie jest do końca prawdziwa dla przypadków zdegenerowanych (kiedy z góry widać mniej niż 3 ścianki kostki), ale działania cały czas dają dobry wynik, bo niektóre boki nie będą generować cienia (rzut jest odcinkiem).

Powyższa obserwacja prowadzi do rozwiązania:

weź dowolny wierzchołek
weź trzy ścianki, z którymi graniczy
policz pole ich rzutów na powierzchnię XY
dodaj otrzymane pola i wyświetl wynik

Wróć do listy zadań

Aneta, Maciek, karnisz i żabki

TBD

Wróć do listy zadań

Ucieczka z biura

TBD

Wróć do listy zadań

Turysta

Dla danego ciągu liczb V, należy znaleźć spójny podciąg, który zawiera największą sumę. Podciągów nie można wybierać dowolnie. Podciągi muszą spełniać określone warunki.

Można zauważyć, że jeśli istnieje rozwiązanie, w którym najpierw jedziemy w lewo, a potem w prawo, to istnieje też rozwiązanie, gdzie zaczynamy podróż w prawo i wracamy w lewo.

Problem w zadaniu można zdefiniować następująco:

Dla każdej rikszy na pozycji X jadącej w prawo o maksymalnie K obiektów, szukamy riksz (na pozycjach Y_i) z przedziału [X, X + K] jadących w lewo, które mogą pojechać na odległość równą lub większą niż Y_i - X. Dla każdej takiej pary należy policzyć sumę atrakcyjności odwiedzonych budynków i wybrać największą z nich.

Rozwiązanie:

Zapiszmy wszystkie riksze jadące w lewo w inny sposób. Zamiast punktu startowego i odległości, na którą może pojechać, weźmy najdalszy punkt, gdzie riksza może dojechać i tam zapiszmy pozycję startową tej rikszy.

Czyli dla każdego elementu ciągu zapamiętajmy wartości:

jak daleko można pojechać w prawo z danego punktu R_i (dodatnie K_i z treści zadania).
listę riksz jadących w lewo L[], dla których ten punkt jest najdalszym osiągalnym punktem.

Dodatkowo potrzebne będą:

sumy prefiksowe S wejściowego ciągu.
drzewo przedziałowe, do znajdowania największej wartości w przedziale.

W rozwiązaniu iterujemy po ciągu V od lewej do prawej strony.

Dla każego elementu ciągu i:

dla wszystkich riksz L_i z listy L[], wstaw do drzewa przedziałowego wartość S[L_i] (suma elementów o 1 do L_i włącznie) na pozycji L_i.
jeśli z punktu i można pojechać w prawo na odległość R_i, znajdź w drzewie największą wartość z przedziału [i, i + R_i].

Wartości dodawane do drzewa zawierają sumę od 1 do L_i. Gdy dla danego i pytamy o maksymalną sumę to interesuje nas wartość bez pierwszych i-1 elementów. Możemy to łatwo policzyć, odejmując od znalezionego wyniku sumę elementów sprzed i: S[i-1]. Znaleziona wartość to potencjalna największa suma, którą należy maksymalizować.

Wróć do listy zadań