Programowanie i algorytmy

Omówienie zadań I rundy

powrót

Fibonacci w przedziale

To zadanie można było rozwiązać na wiele sposobów. Liczby fibonacciego zapisujemy w tablicy, a następnie dla każdego zapytania przeszukujemy całą tablicy i zliczamy tylko te, które mieszczą się w przedziale. Dodatkowo można ustawić sobie wartownika na końcu tablicy np. 2000000000, żeby przez przypadek nie wyjść poza granicę tablicy.

Dodawanie ułamków

Zadanie proste, ale sporo osób złapało się na nim. Przede wszystkim trzeba było zauważyć, że dane wejściowe mogą być przy granicy górnej typu unsigned int. W pewnym momencie należy pomnożyć te liczby, a więc wyjdziemy poza granicę tego typu. Żeby program działał poprawnie dane należy przy mnożeniu zrzutować na unsigned long long lub od samego początku nadać im takie typy. Dodawanie ułamków omówione zostało w tym miejscu.

Trzy odcinki

Wyznaczamy maksimum początków tych odcinków oraz minimum ich końców. Jeśli min - max < 0 to oznacza, że taka część wspólna nie istnieje, w przeciwnym razie szukany przedział to [max..min].

Zapomniany klucz Cezara

Szyfr Cezara został omówiony w tym miejscu. Żeby odszukać klucz, należy sprawdzać kolejne klucze, do momentu otrzymania sensownej wiadomości.

Zamień na dziesiętny

Wzorcowe rozwiązanie tego zadania polegało na zastosowaniu schematu Hornera omówionego w tym miejscu, gdzie wsp[], to tablica cyfr, st to liczba cyfr zmniejszona o 1 oraz x to podstawa systemu w jakim została zapisana liczba. Pamiętajmy o tym, że przy każdym returnie w funkcji horner należy dodatkowo wykonać modulację otrzymanego wyniku. Cyfry wczytujemy oczywiście jako ciąg znaków pamiętając o tym, że znak 0 to 48 w ASCII, 1 to 49 itd. Dlatego też przy obliczeniach należy dany znak zmniejszyć o 48, żeby otrzymać faktyczną wartość cyfry.

Ruchy tektoniczne

To zadanie miało być najtrudniejsze i takie było. Do rozwiązania tego problemu należy użyć zmodyfikowane drzewo przedziałowe typu przedział - przedział, gdzie węzeł to np. zmienna typu strukturalnego przechowująca minimum, maksimum oraz obciążenie dla danego poddrzewa. Zapytania wykonywane są tu w czasie logarytmicznym, a więc dla tak dużych danych jesteśmy wstanie wyrobić się w ustalonym czasie. Rozwiązania siłowe, w których aktualizowano przedział element po elemencie, były zdecydowanie za wolne.

Fraktal Cantora

To zadanie było rozwiązywane wieloma sposobami. Ja mogę zaproponować kolejkę fifo, do której dodaję kolejne elementy danego piętra ustawiając odpowiednią flagę określającą, czy w danej chwili ma być rysowana spacja czy znak podłogi. W zadaniu można wykorzystać STL-ową kolejkę zaimplementowaną w bibliotece queue.
Inne rozwiązania do tego zadania: Blog Kokoska

Permutacje cyfr

Wzorcowe rozwiązanie ma złożoność liniową. Wystarczyło zauważyć, że aby jedna liczba była permutacją drugiej, należało zliczyć kolejne cyfry jednej i drugiej i sprawdzić, czy obie liczby mają po tyle samo odpowiednich cyfr. Cyfry zliczamy następująco: tworzymy tablicę int tab [59], następnie zliczamy cyfry tab[(int)cyfra]++; Dlaczego 59? Wystarczy popatrzeć na kody ASCII cyfr. Liczbę najlepiej wczytać jako ciąg znaków.

Drugie rozwiązanie polegało na posortowaniu cyfr tych liczb i porównaniu tych dwóch ciągów. Tu złożoność jest nieco gorsza: n log n + n.

Metoda trapezów

Liczbę trapezów na jakie należy podzielić pole wyszukujemy binarnie. Rozwiązanie znajduje się w przedziale [1..1000000], a więc środkiem tego przedziału jest oczywiście 500000 trapezów. W pierwszym kroku sprawdzamy, czy pole składające się z tej liczby trapezów jest równe szukanemu. Jeśli tak to mamy wynik, w przeciwnym razie musimy wiedzieć, czy wynik znajduje się w przedziale [1..499999] czy [500001..1000000]. Wszystko zależy od tego, czy badany przedział jest między miejscami zerowymi czy nie. Jeśli tak, to wystarczy zauważyć, że dla niewielkiej liczby trapezów przybliżone pole będzie z nadmiarem, w przeciwnym razie z niedomiarem. Od tego faktu zależy, w jaki sposób będzie działał algorytm przeszukujący binarnie. Dodatkowo należy pamiętać, że nie można porównywać liczb zmennoprzecinkowych. W tym celu wystarczy wyznaczyćepsilon = 0.000001 i równość dwóch liczb stwierdzamy w sytuacji gdy szukana liczba zawiera się w przedziale: [dokładne_pole - epsilon; dokładne_pole + epsilon].

Dodawanie czy odejmowanie

To zadanie rozwiązujemy wykorzystując technikę programowania dynamicznego. Dla uproszczenia pokażę rozwiązanie dla przykładu: 2 1 3 4. Na początku przyjmijmy, że indeksy tablicy mogą być ujemne (w praktyce zwykła tablica nie może takich mieć). Pierwszy wiersz tablicy dwuwymiarowej ustalamy na same zera, z wyjątkiem komórki o numerze 2, tu wstawiamy jeden. Oznacza to, że dla jednej liczby jedyny możliwy wynik to 2. Następnie między 2 i 1 możemy wstawić znak + lub -. Gdy wstawimy + otrzymamy 3, gdy znak "-", otrzymujemy 1. W drugim wierszu komórki o tych indeksach ustawiamy na 1, pozostałe powinny być 0. W każdym następnym kroku badamy poprzedni wiersz tablicy i w przypadku napotkania wartości 1 przesuwamy się w lewo i prawo o wartość następnej liczby w ciągu wstawiając w to miejsce 1. Indeksy ostatniego wiersza, pod którymi znajdują się 1, reprezentują możliwe do otrzymania wyniki. W naszym przykładzie to: -6, -4, 0, 2, 4, 8 oraz 10. Indeksy ujemne możemy usunąć przesuwając całość o odpowiednią wartość w prawo ( w zadaniu wystarczy 100000).
Poniższa tabela prezentuje zachowanie się danych dla powyższego ciągu:

Czworokąt na okręgu

Do prawidłowego rozwiązania zadania należało zapoznać się z warunkiem gwarantującym wpisanie okręgu w czworokąt: suma dwóch przeciwległych boków musi być równa sumie pozostałej parze. Dodatkowo należy pamiętać, że chociaż każda z liczb mieści się w unsigned int, to ich suma już niekoniecznie.

Gra w pierwsze

Do tego zadania należy zapoznać sie z kolejnym maturalnym algorytmem opisanym w tym miejscu. Nie wolno użyć sita Eratostenesa, ponieważ maksymalna potencjalna liczba pierwsza jest zbyt duża.

Notowania akcji 

Na początku bierzemy pierwszą trójkę liczb i sprawdzamy, czy spełniony jest jeden z warunków:
liczba_1 < liczba_2 i liczba_2 > liczba_3 lub liczba_1 > liczba_2 i liczba_2 < liczba_3. Jeśli tak, to mamy już 3 elementowy ciąg. Następnie przesuwamy się o jeden w prawo i znowu sprawdzamy poprawność jednego z warunków: liczba_2 < liczba_3 i liczba_3 > liczba_4 lub liczba_2 > liczba_3 i liczba_3 < liczba_4. Jeśli znowu jest prawda, to mamy już czteroelementowy ciąg spełniający kryteria zadania, jeśli nie to zaczynamy od początku, pamiętając o przechowywaniu dotychczasowej maksymalnej znalezionej długości. Gdy maksymalny ciąg będzie krótszy niż 3 powinniśmy wypisać 0.

Liczba k-cyfrowych liczb 
To zadanie jest bardziej matematyczne, a na zapytania można odpowiadać w czasie stałym: http://www.math.edu.pl/rozwiazanie.php?dzial=rozne&id=301
W języku C++ należy napisać własną funkcję pow(), bo funkcja z biblioteki math traci precyzję dla maksymalnych danych.

Podział odcinka
To zadanie nie jest trudne. Liczba podziału odcinka to NWD długości wektorów x,y, gdy x i y różne od zera. Przy obliczaniu długości należy pamiętać o odpowiednich typach danych.

Dzielniki silni 
Rozwiązanie: http://www.math.edu.pl/rozwiazanie.php?dzial=rozne&id=290
W algorytmie potrzebny jest preprocesing, aby na zapytania odpowiadać w czasie stałym. Implementacja w skrócie: sito, tablica liczb pierwszych, wczytanie danych do tablicy z wyłonieniem maksymalnej wartości (choć nie jest to wymagane), rozkład liczb od 2 do max na czynniki pierwsze pamiętając liczbę czynników pierwszych, gdzie po każdym rozkładzie na bieżąco korzystamy z reguły mnożenia dla niezerowej liczby wykładników, pamiętając o modulacji. Wynik dla n-tej liczby zapisujemy do tablicy, i tak dla wcześniej wczytanych danych możemy odpowiadać w czasie stałym.

Tulipany 
Kwadratowy algorytm oczywiście będzie za wolny. Wystarczy posortować dowolny ciąg liczb, i iterując drugi liniowo, szukamy binarnie najbliższej liczby w posortowanym ciągu.
Złożoność: O(n*log(m))

Trzyliterówka
Zadanie okazało się trudne, ale takie nie jest. Należy zliczać literki z początku i końca wspomagając się dwiema tablicami i zmiennymi boolowskimi dla pewnego rodzaju problematycznych przypadków.
Złożoność: O(d*m)

Wszystkie zgłoszenia w C++, których czas był większy niż 0.00, zatrzymywały się na kilku takich problematycznych przypadkach i wystarczyło dodać dla nich wyjątek.
Oto one:
2
aba oko
3
abd dca oko
4
abd dca prt tsp

Odpowiedzią dla każdego przypadku to NIE
*************************************************************************************

Oczywiście to nie jedyne poprawne rozwiązania problemów, w nadesłanych rozwiązaniach znalazły się algorytmy odmienne od tutaj przedstawionych, prowadzące także do zaliczenia zadania.