Programowanie i algorytmy

Omówienie zadań z III rundy

powrót

Zbiór liczb niepodzielnych
Przykładowe rozwiązanie
Przeanalizujmy przykład z zadania:
Przedział, który będziemy rozpatrywać to w sumie [1..20]
W pierwszej kolejności wykonujemy coś podobnego do sita Eratostenesa dla liczb z multizbioru wykreślając je z powyższego przedziału:
1, 2, 34, 5, 6, 7, 8910, 11, 12, 13, 141516, 17, 18, 19, 20

Teraz w dodatkowej tablicy zliczamy ilość wystąpień liczb niepodzielnych, tak więc np. w tab[10] będziemy mieli 3 takie liczby, a w tab[20] jest ich siedem. Teraz aby wyznaczyć liczbę liczb niepodzielnych w przedziale [a..b], wystarczy zwrócić róznicę

tab\[b\] – tab[a-1].


Pięć kół i kwadrat
Przykładowe rozwiązanie
W tym zadaniu należy wykorzystać technikę Monte Carlo, czyli wylosować odpowiednią dużą liczbę punktów z kwadratu i sprawdzić czy należą one także do któregoś okręgu. Wszystkie punkty reprezentują pole kwadratu, te zaś, które mieszczą się w chociaż jednym okręgu reprezentują pole części wspólnej kwadratu i okręgu. W ten sposób możemy wyliczyć szukane procenty.

DOMINO II
Przykładowe rozwiązanie
Zadanie grafowe. Zadanie można rozwiązać zwykłym DFS-em z nawrotami(Backtracking). Warto zauważyć, że po zakończonej grze co najmniej jeden z końcowych kamieni domina będzie należał do profesora.

Modulo 10
Do rozwiązania wykorzystujemy schemat Hornera opisany tutaj, pamiętając, aby na bieżąco modulować wynik. Pamiętajmy, że żaden typ zmiennych w C++ nie pomieści liczby złożonej z 1000 bitów.

Ułamki dziesiętne
Przykładowe rozwiązanie
Potrzebna wiedza: arytmetyka na ułamkach, algorytm Euklidesa, szeregi geometryczne.
Jedyna trudność w tym zadaniu to zamiana ułamka okresowego na zwykły. Tu przyda się szereg geometryczny. Sumę takiego szeregu liczymy ze wzoru:

pierwszy_wyraz_ciagu/(1 - iloraz_ciagu)

Dla przykładu przeanalizujmy ułamek: 0,0(87)

0,0(87) = 0,0878787... = 0,087 + 0,00087 + 0,0000087 + ...

gdzie a1 = 0,087 natomiast iloraz = 1/100. Podstawiamy do wzoru i mamy 87/990

Bitcoin
Rozwiązanie dynamiczne. Załóżmy, że jedynym możliwym rozwiązaniem jest modernizacja pierwszego komputera. W tym przypadku jedynym sensownym rozwiązaniem jest zainwestowanie całej kwoty w ten komputer.
Załóżmy teraz, że mamy do dyspozycji dwa komputery. Wyznaczamy wszystkie możliwe kombinacje czyli:
0 tyś. w drugi komputer oraz n w pierwszy, 1 w drugi oraz n-1 w pierwszy itd. Przyrost bit monet dla powyższych kombinacji przechowujemy w tablicy i teraz wiemy gdzie najlepiej zainwestować.
W następnym kroku analizujemy co się dzieje, gdy zainwestujemy 0 tyś w trzeci komputer i najlepszą inwestycje n tysięcy w poprzednie dwa, dalej 1 tyś w trzeci komputer i n-1 tyś w poprzednie dwa itd. W ten sposób otrzymujemy najlepsze inwestycje dla danych trzech komputerów. Identycznie postępujemy dla 4 i 5 komputera. Ostatecznie otrzymujemy maksymalny szukany zysk.

Zadanie Maćka
kilka sposobów. Jednym z nich było zauważenie,że mając a we wzorze
a^2+b^2=c^2
Można było go przekształcić do
a^2=c^2-b^2
A to się równa a^2=(c-b)(c+b)
Teraz wystarczy znaleźć dzielniki liczby a^2 ,np: 3^2=(c-b)(c+b)
Dzielnikami 9 są 1 , 3 , 9
c+b=9 && c-b=1
2c=10 /:2
c=5
b=9-5=4
3,4,5

Lokata
www.spoj.com/FRAKTAL/problems/FR_03_02/

arytmetyka

kp - kapitał początkowy
kk - kapitał końcowy
p - stopa procentowa
rozwiązanie: (log(kk) - log(kp))/log(1 + p/100);
//



Desant
www.spoj.com/FRAKTAL/problems/FR_03_04/

wyszukiwanie binarne, haszowanie

Wczytujemy punkty, sortujemy je względem osi X lub Y i dla zapytania o punkt sprawdzamy jego przynależność za pomocą wyszukiwania binarnego.
Do realizacji zadania można było wykorzystać mapę STL lub wykorzystać haszowanie do boolowskiej tablicy jednowymiarowej.
//



Stronicowanie
www.spoj.com/FRAKTAL/problems/FR_03_06/

elementarne

Proste działania arytmetyczne pozwalające wyznaczyć liczbę stron, minima i maksima dla odnośników oraz wyświetlanie rekordów i odnośników zgodnie z podaną specyfikacją.
//



Fibonacci
www.spoj.com/FRAKTAL/problems/FR_03_08/

rekurencja, ciąg Fibonacciego, arytmetyka

Nie możemy generować szukanego ciągu i zliczać literek z oczywistych względów. Generujemy więc ciąg liczb Fibonaciego nie przekraczający 50 i zapisujemy wartości w tablicy. W zapytaniach zliczamy litery w pierwszym i drugim wyrazie, po czym wykorzystujemy wcześniej wygenerowane wartości ciągu Fibonacciego jako mnożnika dla tych liczb w zależności od wartości k. Rozwiązaniem jest suma iloczynów.
//



Ciąg EKG
www.spoj.com/FRAKTAL/problems/FR_03_10/

Liczby pierwsze, sito, podzielność

W rozwiązaniu potrzebny jest preprocesing, tzn. należy wygenerować szukany ciąg i przypisać pozycje wartościom w nowej tablicy, po czym na zapytania odpowiadać w czasie stałym, w przeciwnym razie otrzymamy TLE. Do wygenerowania ciągu możemy wykorzystać rozkład liczb na czynniki pierwsze, posiłkując się tablicą z liczbami pierwszymi wygenerowanymi wcześniej za pomocą sita Eratostenesa i pomocniczą tablicą sprawdzającą, czy liczba należy już do ciągu. Próba generowania takiego ciągu przy pomocy nwd i sprawdzania, czy kolejne wyrazy są względnie pierwsze nie powiedzie się ze względu na zbyt długi czas generowania taką metodą.
//



Podział kuli
www.spoj.com/FRAKTAL/problems/FR_03_12/

kombinatoryka

Rozwiązaniem jest ciąg: oeis.org/A000125
Po redukcji otrzymujemy ciąg o wzorze ogólnym a(n) = (n^3-n)/6+n+1
//



Metryka miasto
www.spoj.com/FRAKTAL/problems/FR_03_14/

sortowanie, odległość w metryce miasto.

Nie ma potrzeby szukania punktu optymalnego, (czasem takich punktów może być więcej). Wystarczyło zauważyć, korzystając z własności odległości w metryce miasto, że szukaną sumą będzie:

for(i=0; i<n; i++)
suma += (abs(X(i)-X(n/2)) + abs(Y(i)-Y(n/2)));

gdzie, X i Y to posortowane rosnąco ciągi współrzędnych X i Y wczytanych koordynatów z wejścia.
//



Ciąg cyfr
www.spoj.com/FRAKTAL/problems/FR_03_16/

rekurencja z powrotami

Zadanie problematyczne, bo potrzebujemy zminimalizować ostatnią wartość maksymalizując początkowe wyrazy, a w tym wszystkim przeszkadza nam zero wiodące. Rozwiązaniem jest rekurencja z powrotami. Rozpoczynamy od minimalizowania ostatniej wartości, po czym przesuwając się w ciągu od prawej strony do lewej wyszukujemy rozwiązania najlepszego za pomocą powrotów. Do realizacji zadania potrzebna będzie także funkcja porównująca sąsiednie wyrazy, nie potrzeba zamieniać ciągów na liczby, wystarczy porównywać ciągi znaków, ale tu także musimy zwrócić uwagę na cyfrę zero i odpowiednio taką funkcję zaimplementować, bo haczyków jest sporo.
//