FRAKTAL - konkurs programistyczny (SPOJ)

Omówienie zadań

Nowe buty do biegania
Policz budynki
Zbieranie drużyny
Scena
Harmonijny wyraz
Kalendarz
Znajomi II
Trener Fraktaliusz
Dwa ciągi
Bramka
Foordle
World of Bajtcraft

Nowe buty do biegania

Rozwiązanie zadania polega na sprawdzeniu dwóch warunków w podanej poniżej kolejności:

Jeżeli k ≥ 500 × 1,609344 to wypisujemy TAK i kończymy działanie programu.
Jeżeli k ≥ 300 × 1,609344 to wypisujemy SPRAWDZIMY TWOJE OBECNE BUTY i kończymy działanie programu.

Jeżeli żaden z powyższych warunków nie został spełniony to wypisujemy NIE.

Złożoność czasowa: O(1)

Do rozwiązania zadania możemy użyć techniki zliczania na indeksach. Z treści zadania wiemy, że budynki mogą mieć numery od 1 do 1000. W takim wypadku definiujemy 1001-elementową tablicę liczb całkowitych. Komórki o indeksach od 1 do 1000 będą przechowywały wartość 1 jeżeli dany budynek jest zamieszkany albo 0 w przeciwnym wypadku.

Początkowo wszystkie komórki mają wartość 0. Następnie dla każdego wczytanego numeru budynku zapisujemy na odpowiadającym mu indeksie tablicy wartość 1. Po wczytaniu wszystkich danych naszą odpowiedzią będzie suma wartości zapisanych w komórkach od 1 do 1000.

Złożoność czasowa: O(n)

Wróć do listy zadań

Zbieranie drużyny

Do rozwiązania zadania możemy użyć techniki zliczania na indeksach. Z treści zadania wiemy, że zawodnicy mogą mieć numery od 1 do 100. W takim wypadku definiujemy 101-elementową tablicę liczb całkowitych. Komórki o indeksach od 1 do 100 będą przechowywały wartość 1 jeżeli dany zawodnik zagra albo 0 w przeciwnym wypadku.

Początkowo wszystkie komórki mają wartość 0. Następnie dla każdego wczytanego numeru zawodnika oraz słowa robimy dwa sprawdzenia:

Jeżeli słowo jest równe: bede, ja albo gram to w tablicy na indeksie odpowiadającym numerowi zawodnika zapisujemy 1.
Jeżeli słowo jest równe: odpadam albo rezygnuje to w tablicy na indeksie odpowiadającym numerowi zawodnika zapisujemy 0.

Po wczytaniu wszystkich danych liczymy sumę wartości zapisanych w komórkach od 1 do 100 i w zależności od jej wartości wypisujemy zdanie określające czy gramy czy nie gramy.

Złożoność czasowa: O(n)

Wróć do listy zadań

Scena

Rozwiązanie sprowadza się do sprawdzenia ile spośród punktów określających zajęte miejsca należy do odcinka 0,0 — x_j,y_j. Żeby punkt x,y należał do odcinka musi spełniać 3 warunki:

x < x_j
y < y_j
Punkty 0,0, x,y oraz x_j,y_j muszą być współliniowe.

Sprawdzenie dwóch pierwszych warunków jest proste, ale jak sprawdzić czy powyższe punkty są współliniowe?

Zauważmy, że jeżeli punkt x,y jest współliniowy z punktami 0,0 oraz x_j,y_j to stosunek współrzędnych x i y powinien być równy stosunkowi współrzędnych x_j i y_j. Wystarczy więc, że sprawdzimy czy ułamki x/y i x_j/y_j są sobie równe. Możemy to sprawdzić sprowadzając je do wspólnego mianownika i porównując liczniki. Innymi słowy sprawdzamy czy x × y_j = x_j × y.

Złożoność czasowa: O(n)

Wróć do listy zadań

Harmonijny wyraz

Na potrzeby tego omówienia przyjmijmy sobie, że:

A - oznacza dowolną samogłoskę.
B - oznacza dowolną spółgłoskę.

Wiemy, że żeby wyraz był harmonijny to nie może zawierać dwóch sąsiadujących samogłosek lub dwóch sąsiadujących spółgłosek. Przekładając to na powyższe oznaczenia w wyrazie nie może wystąpić AA lub BB. Na tej podstawie możemy wywnioskować, że każdy wyraz harmonijny ma jedną z poniższych postaci:

ABABAB... - na przemian samogłoska, spółgłoska.
BABABA... - na przemian spółgłoska, samogłoska.

Rozwiązanie zadania polega zatem na policzeniu ile operacji musimy wykonać żeby doprowadzić wczytany wyraz do każdej z powyższych postaci. Odpowiedzią będzie mniejsza z liczb operacji.

Złożoność czasowa: O(n)

Wróć do listy zadań

Kalendarz

Oznaczmy wczytany rok jako y. Zauważmy, że nie musimy znać rzeczywistego dnia tygodnia od jakiego zaczyna się y. Możemy założyć, że jest to dowolny dzień, niech to będzie poniedziałek. Rozwiązanie zadania sprowadza się do znalezienia najbliższego roku x takiego, że:

y < x
p(x) = p(y), gdzie p(i) to numer dnia tygodnia od jakiego zaczyna się rok i (0 - poniedziałek, 1 - wtorek, ... itd.).
d(y) = d(x), gdzie d(i) to funkcja zwracająca liczbę dni w roku i.

Głównym problemem jaki nam pozostał do rozwiązania jest wyznaczanie kolejnych wartości p(x). Zauważmy, że znając p(x) oraz d(x) możemy łatwo wyznaczyć p(x + 1):

p(x + 1) = (p(x) + d(x)) mod 7

Wiedząc jak wygenerować wszystkie potrzebne informację możemy przechodzić w pętli przez kolejne lata, aż do momentu znalezienia roku x spełniającego powyższe warunki.

Złożoność czasowa: O(n)

Wróć do listy zadań

Znajomi II

Ponieważ liczba użytkowników portalu społecznościowego wynosi maksymalnie 1000, to możemy zastosować rozwiązanie siłowe.

Nasze rozwiązanie będzie się składało z dwóch zagnieżdżonych pętli przechodzących po tablicy wczytanych indeksów. Zewnętrzna pętla wybiera indeks, dla którego będziemy szukać anagramów. Pętla wewnętrzna przechodzi przez wszystkie indeksy i liczy ile z nich jest anagramami tego wybranego w pętli zewnętrznej. Jeżeli aktualnie wybrany indeks utworzył większą grupę niż największa dotychczasowa to zapisujemy go.

Po zakończeniu dwóch pętli opisanych powyżej przechodzimy jeszcze raz przez wszystkie indeksy. Jeżeli indeks jest anagramem zapisanego przez nas indeksu największej grupy to wypisujemy go.

Pozostaje kwestia tego jak sprawdzić czy dwa indeksy są anagramami. Możemy to zrobić na wiele sposobów jednak najprostszym wydaje się posortowanie liter w obydwu indeksach i sprawdzenie czy otrzymaliśmy takie same wyrazy.

Złożoność czasowa: O(n²)

Wróć do listy zadań

Trener Fraktaliusz

W zadaniu danych jest n treningów. Wiemy, że każdy kolejny trening ma dystans większy od poprzedniego. Naszym zadaniem jest policzenie dla każdego zawodnika sumy kilometrów jaką przebiegnie zanim trafi na trening, którego dystans będzie przekraczał jego możliwości. Ponieważ maksymalna liczba treningów n i maksymalna liczba zawodników wynoszą 10⁶ to oznacza, że nie możemy wyszukiwać treningu w pętli, bo przekroczymy dostępny limit czasu.

Ponieważ w zadaniu mamy zapewnienie, że każdy kolejny trening ma dystans większy od poprzedniego to żeby przyspieszyć znalezienie pierwszego treningu, którego zawodnik nie jest w stanie spełnić możemy skorzystać z wyszukiwania binarnego. W tym celu generujemy drugą tablicę, w której obliczamy długość każdego z treningów. Po utworzeniu tablicy możemy wykonywać na niej wyszukiwanie binarne.

Złożoność czasowa: O(q log n)

Wróc do listy zadań

Dwa ciągi

W zadaniu mamy wykonać q operacji na ciągu a, a następnie odpowiedzieć na pytanie czy po wykonaniu tych operacji ciąg a jest równy ciągowi b.

Najprostszym rozwiązaniem jest aktualizowanie w pętli elementów ciągu od pozycji l do pozycji r, dla każdej operacji. Złożoność czasowa tego algorytmu to O(qn). Ponieważ maksymalna liczba operacji q i maksymalna długość ciągu n wynoszą 10⁵ to takie rozwiązanie nie zmieści się w limicie czasu.

Złożoność czasową naszego rozwiązania możemy poprawić stosując tablicę różnic.

Tablica różnic powinna mieć rozmiar o 1 większy od tablicy, na której chcemy przeprowadzać zmiany. W naszym wypadku musimy utworzyć tablicę o rozmiarze n + 1. Każda komórka tablicy różnic przechowuje informację jaka jest różnica wartości pomiędzy nią samą, a komórką znajdującą się przed nią.

Załóżmy teraz, że chcemy dodać wartość k na pozycjach do l do r. Jak taka zmiana powinna zostać odwzorowana w naszej tablicy różnic?

Wiemy, że począwszy od pozycji l wszystkie wartości mają być większe o k. Oznacza to, że musimy dodać wartość k na pozycji l, bo o tyle zmieni się wartość pomiędzy pozycjami l - 1 i l.

Wiemy również, że dodanie wartości k ma zostać zakończone na pozycji r. Oznacza to, że musimy odjąć wartość k na pozycji r + 1, bo o tyle zmieni się wartość pomiędzy pozycjami r i r + 1.

W ten sposób odwzorowujemy w tablicy różnic każdą z q operacji. Następnie liczymy sumy prefiksowe dla naszej tablicy różnic. W ten sposób na pozycji i-tej otrzymamy wartość o jaką powinien zmienić się i-ty element ciągu a po wykonaniu q operacji.

Pokażmy działanie tablicy różnic na teście przykładowym.

Tablica różnic:

1 2 3 4 5 6 7 8 9

0 0 0 0 0 0 0 0 0
Tablica różnic po operacji 1 5 2:

1 2 3 4 5 6 7 8 9

2 0 0 0 0 -2 0 0 0
Tablica różnic po operacji 8 8 2:

1 2 3 4 5 6 7 8 9

2 0 0 0 0 -2 0 2 -2
Tablica różnic po operacji 2 2 2:

1 2 3 4 5 6 7 8 9

2 2 -2 0 0 -2 0 2 -2
Tablica różnic po operacji 7 8 2:

1 2 3 4 5 6 7 8 9

2 2 -2 0 0 -2 2 2 -4
Tablica różnic po operacji 5 5 2:

1 2 3 4 5 6 7 8 9

2 2 -2 0 2 -4 2 2 -4
Tablica różnic po policzeniu sum prefiksowych:

1 2 3 4 5 6 7 8 9

2 4 2 2 4 0 2 4 0

1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0

1	2	3	4	5	6	7	8	9
2	0	0	0	0	-2	0	0	0

1	2	3	4	5	6	7	8	9
2	0	0	0	0	-2	0	2	-2

1	2	3	4	5	6	7	8	9
2	2	-2	0	0	-2	0	2	-2

1	2	3	4	5	6	7	8	9
2	2	-2	0	0	-2	2	2	-4

1	2	3	4	5	6	7	8	9
2	2	-2	0	2	-4	2	2	-4

1	2	3	4	5	6	7	8	9
2	4	2	2	4	0	2	4	0

Jeżeli dodalibyśmy powyższe wartości do elementów ciągu a = (2, 0, 2, 2, 0, 4, 2, 0) to otrzymamy ciąg b = (4, 4, 4, 4, 4, 4, 4, 4).

Ponieważ elementy ciągu są obracane, to musimy pamiętać aby po zwiększeniu wartości elementu ciągu a policzyć jego resztę z dzielenia przez 10.

Złożoność czasowa: O(q + n)

Wróć do listy zadań

Bramka

W zadaniu należy sprawdzić, jaki będzie efekt strzału na bramkę ("gol", "słupek" lub "pudło").

Dane na wejściu:

współrzędne prawego słupka P_x, P_y
współrzędne lewego słupka L_x, L_y
kierunek strzału D_x, D_y

Gol jest wtedy, gdy piłka minie prawy słupek z lewej strony i lewy słupek z prawej strony.

Rozwiązanie 1: liczenie kątów

Policzmy kąty, jaki tworzy dodatnia oś X z
a_p: odcinkiem o początku w punkcie (0,0) i końcu (P_x, P_y)
a_l: odcinkiem o początku w punkcie (0,0) i końcu (L_x, L_y)
a_d: odcinkiem o początku w punkcie (0,0) i końcu (D_x, D_y)

Każdy kąt będzie w przedziale [0, 360). Ponieważ współrzędne mogą znajdować się we wszystkich ćwiartkach układu współrzędnych,
dla ułatwienia można policzyć kąt dla dodatnich współrzędnych:

a = atan(abs(y)/abs(x))

i w zależności od tego, w której ćwiartce znajdują się współrzędne, odpowiednio zmodyfikować kąt.
Np 180 - a, dla drugiej ćwiartki (x < 0, y > 0).

Równocześnie należy uwzględnić przypadki specjalne przypadki, gdy x jest równy 0 (a = 90 lub a = 270).

Po wyznaczeniu kątów, można odpowiedzieć na zadane pytanie:

jeśli a_d == a_p lub a_d == a_l, odpowiedzią jest: słupek
jeśli a_d < a_l oraz a_d > a_p (dla a_l > a_p), odpowiedzią jest: gol
jeśli a_d < a_l lub a_d > a_p (dla a_l < a_p - bramka przechodzi przez dodatnią oś X), odpowiedzią jest: gol
pudło w pozostałych przypadkach

Rozwiązanie 2: iloczy wektorowy 2d

Trochę teorii:
Weźmy dwa wektory A = (A_x, A_y) i B = (B_x, B_y)

Zdefiniujmy iloczy wektorowy 2D jako:
cp(A, B) = A_x*B_y - A_y*B_x

Interpretacją geometryczną iloczynu wektorowego jest pole równoległoboku wyznaczonego przez odcinki: [(0,0), A], [A, A+B], [(0,0), B], [B, B+A]
(abs(cp(A, B)) jest polem tej figury).

Istotną właściwością iloczynu wektorowego, z której skorzystamy w rozwiązaniu, jest:
cp(A, B) = -cp(B, A)

Zmiana kolejności wektorów, powoduje zmianę znaku wyniku.
Powyższa właściwość pozwala łatwo stwierdzić, po której stronie prostej wyznaczonej przez wektor znajduje się dany punkt.

Jeżeli cp(A, B) jest większe od 0, wektor B "skręca" na lewo od wektora A.
Jeżeli cp(A, B) jest mniejsze od 0, wektor B "skręca" na prawo od wektora A.

Przez "skręca" rozumiemy, że mniejszy kąt między A i B idzie w kierunku przeciwnym do ruchu wskazówek zegara (przy skręcie w lewo).

Jeżeli cp(A, B) jest równe 0, wektory są współliniowe.
UWAGA: cp równy 0, nie mówi nam nic o zwrocie wektorów. Zwroty mogą być takie same lub przeciwne.

Przykład 1:
Weźmy wektor kierunkowy D = [(1, 2), (5, 6)] i punkt P = (4, 8).
Obliczamy wektory A i B (wektory A i B muszą mieć wspólny początek leżący w punkcie (0, 0)):
A = (5 - 1, 6 - 2) = (4, 4)
B = (4 - 1, 8 - 2) = (3, 6)

cp(A, B) = 4*6 - 4*3 = 24 - 12 = 12

Wartość dodatnia oznacza, że punkt P leży po lewej stronie prostej wyznaczonej przez wektor D.

Przykład 2:
Weźmy wektor kierunkowy D = [(4, -2), (-2, 3)] i punkt P = (-5, 8).
A = (-2 - 4, 3 - (-2)) = (-6, 5)
B = (-5 - 4, 8 - (-2)) = (-9, 10)

cp(A, B) = -6*10 - 5*(-9) = -60 - (-45) = -60 + 45 = -15

Wartość ujemna oznacza, że punkt P leży po prawej stronie prostej wyznaczonej przez wektor D.

Wykorzystajmy teraz iloczyn wektorowy do rozwiązania zadania:

Mamy wektory:
P - prawy słupek
L - lewy słupek
D - wektor kierunkowy strzału

Gol jest wtedy, gdy piłka minie prawy słupek z lewej strony i lewy słupek z prawej strony, czyli:
cp(D, L) > 0 oraz cp(D, P) < 0

Słupek będzie jeśli piłka minie prawy słupek z lewej strony i trafi dokładnie lewy słupek, czyli:
cp(D, L) == 0 oraz cp(D, P) < 0

Drugi słupek będzie jeśli piłka minie lewy słupek z prawej strony i trafi dokładnie prawy słupek, czyli:
cp(D, L) > 0 oraz cp(D, P) == 0

W pozostałych przypadkach nie trafiamy w bramkę.

Złożoność czasowa: O(1)

Wróć do listy zadań

Foordle

W zadaniu mamy stwierdzić czy na podstawie informacji zwrotnej otrzymanej po dotychczasowych q próbach odgadnięcia wyrazu jesteśmy w stanie odgadnąć go w następnej próbie.

Wiemy, że nasz wyraz zawsze ma długość 5 liter. Wiemy, że alfabet angielski składa się z 26 liter. Stwórzmy zatem dwie tablice:

Tablicę dwuwymiarowa D[5][26]. Komórka D[i][j] będzie miała wartość 1 jeżeli na i-tym indeksie w szukanym wyrazie może wystąpić j-ta litera alfabetu angielskiego albo 0 w przeciwnym wypadku. Początkowo wszystkie komórki tablicy powinny mieć wartość 1.
Tablicę jednowymiarową M[26]. Komórka M[j] będzie przechowywała wartość 1 jeżeli wiemy, że j-ta litera alfabetu angielskiego występuje w szukanym wyrazie albo 0 jeżeli tego nie wiemy. Początkowo wszystkie komórki tej tablicy powinny mieć wartość 0.

Mając utworzone tablice musimy nanieść na nie informacje zwrotne uzyskane w dotychczasowych q próbach odgadnięcia szukanego wyrazu. W tym celu analizujemy 5-cyfrowe ciągi z informacją zwrotną.

Załóżmy, że analizujemy próbę, w której Maciek podał wyraz HABED i otrzymał dla niego ciąg 02100.

Dla liter H, E oraz D otrzymał cyfrę 0, co oznacza, że dane litery nie występują w szukanym wyrazie. W związku z tym dla każdego indeksu i od 0 do 4 ustawiamy D[i][3] = 0 (litera D), D[i][4] = 0 (litera E) oraz D[i][7] = 0 (litera H).
Dla litery B otrzymał cyfrę 1, co oznacza, że dana litera występuje w szukanym wyrazie, ale na indeksie innym niż 2. W związku z tym ustawiamy D[2][1] = 0. Jednocześnie wiemy, że litera B musi wystąpić w szukanym wyrazie, a zatem ustawiamy M[1] = 1.
Dla litery A otrzymał cyfrę 2, co oznacza, że dana litera występuje na indeksie 1. W związku z tym dla każdego indeksu j od 1 do 25 (litery od B do Z) ustawiamy D[1][j] = 0. Jednocześnie wiemy, że litera A musi wystąpić w szukanym wyrazie, a zatem ustawiamy M[0] = 1.

W ten sposób nanosimy informacje dla każdej z q prób odgadnięcia wyrazu.

Następnie analizujemy każdy wyraz jaki znajduje się w słowniku. Po pierwsze sprawdzamy za pomocą tablicy D, czy litery występujące na kolejnych indeksach wyrazu są na nich dozwolone. Po drugie za pomocą tablicy M sprawdzamy czy wyraz zawiera wszystkie litery, o których wiemy, że występują w szukanym wyrazie. Jeżeli wyraz pomyślnie przeszedł obydwa sprawdzenia to może być on naszym szukanym wyrazem.

Jeżeli po przejściu wszystkich wyrazów w słowniku mamy dokładnie 1 wyraz, który może być naszym szukanym wyrazem to odpowiedzią będzie TAK. W przeciwnym wypadku odpowiedzią jest NIE.

Złożoność czasowa: O(q + n)

Wróć do listy zadań

World of Bajtcraft

Dane w zadaniu:

K - liczb surowców na minutę zbieranych przez jednego robotnika
S - koszt produkcji jednego robotnika
M - czas produkcji nowego robotnika
G - liczba surowców do zebrania

W zadaniu musimy policzyć, ile czasu zajmie zebranie określonej ilości surowców G.

W rozwiązaniu przeprowadzimy symulację zbierania surowców. Optymalne rozwiązanie osiągniemy na jeden z poniższych sposobów:

Jeden robotnik pracujący sam od początku do końca (bez produkcji nowych pracowników)
Produkowanie nowych robotników jak tylko mamy na to dostępne surowce.

W rozwiązaniu podajemy to, które trwa krócej.

Symulacja:

Symulację możemy podzielić na dwie fazy:

zbieranie surowców na kolejnego robotnika
czekanie, aż kolejny robotnik zostanie wyprodukowany

Im więcej robotników mamy do dyspozycji, tym krócej trwa pierwsza faza.
W pewnym momencie będziemy mogli ją całkowicie pominąć, bo czekając na kolejnego robotnika uzbieramy wystarczająco dużo surowców,
żeby zacząć produkować kolejnego, jak tylko dostaniemy poprzedniego.

Zdefiniujmy sobie metodę F, która policzy, ile minut będziemy zbierać określoną ilość surowców J, mając X robotników:
F (J, X) = J / (XK) + (J / (XK) mod (XK) != 1 ? 1 : 0)

Liczymy, ile czasu zajmie zebranie wszystkich surowców mając 1 robotnika:

R = F (G, 1)

Jest to górne ograniczenie na wynik.

Sprawdźmy, czy można osiągnąć lepszy wynik.

W tym celu policzymy, ile czasu będziemy zbierać na nowego robotnika (faza pierwsza):
L1 = F (S, 1)

W tym czasie uzbieramy
N1 = L1*K
surowców.

Musimy jeszcze odczekać M minut, aż nowy robotnik zostanie wyprodukowany (faza druga).

Nowego robotnika będziemy mieć po:
T2 = L1 + M

W tym momencie będziemy mieć
S2 = N1 - S + M*K
surowców.

Od tego momentu mamy 2 robotników i S2 surowców w banku.

Sprawdzamy, kiedy uzbierają wymagane do zwycięstwa surowce.
R2 = T2 + F (G - S2, 2)

Porównujemy R2 z poprzednio wyliczonym R. Jeśli nowy wynik jest większy, możemy przerwać obliczenia.

Jeśli R2 jest mniejsze, to możemy wrócić do fazy pierwszej, przy czym we wszystkich kolejnych obliczeniach musimy uwzględnić
aktualną liczbę robotników, początkową ilość surowców, które już posiadamy oraz czas, który już upłynął.

Powyższe rozwiązanie iteracyjne można zapisać rekurencyjnie. Zakładamy, że parametry wejściowe są dostępne globalnie.

Pseudokod:

int solution(początkowe surowce B, liczba robotników X) // ile czasu X robotników będzie zbierać docelową ilość surowców R0 = F (G - B, X) // czas, po którym dostaniemy nowego robotnika T1 = M // ile czasu potrzeba, żeby uzbierać na kolejnego robotnika If (B < S) T1 += F (S - B, X) // Warunek zakończenia rekurencji. Produkcja nowego robotnika zajmie więcej niż, zebranie surowców if (R0 <= T1) return R0 R1 = T1 + solution(B + T1*X*K - S, X + 1) return min(R0, R1)

Żeby rozwiązać zadanie, wywołujemy:

solution(0, 1)

Złożoność czasowa: O(n)

Wróć do listy zadań