Programowanie i algorytmy

Omówienie zadań z II edycji

powrót

Wyznacz promień
W tym zadaniu należy wykorzystać dwukrotnie wzór na pole trójkąta. Pierwszy wzór wykorzystuje długości boków trójkąta zawartych między punktami - jest to wzór Herona, natomiast drugi to wzór, w którym zawarty jest promień okręgu opisanego na tym trójkącie: P = (abc)/($R)

Małe problemy Bajtka
W tym zadaniu nie należy patrzeć na liczby jak na liczby. Więcej nie podpowiem :)

Znak pierwiastka
W tym zadaniu należy najpierw rozłożyć liczbę na czynniki pierwsze, następnie zauważyć, w jaki sposób wyciągamy czynniki przed pierwiastek. Np jeśli liczba rozkłada się 2^10 * 3^5, a stopień pierwiastka jest równy 3, to możemy przed pierwiastek wyciągnąć (10 div 3 = 3, 5 div 3 = 1) 2^3 * 3^1, natomiast pod pierwiastkiem zostanie (10 mod 3 = 1, 5 mod 3 = 2) 2^1 * 3^2, gdzie div to dzielenie całkowite, a mod to reszta z dzielenia.

Liczby (nie)pierwsze
Do rozwiązania tego zadania można wykorzystać drzewo przedziałowe. W pierwszej kolejności przesiewamy sitem Eratostenesa zbiór liczb naturalnych nie większych niż 2 mln. Następnie liniowo przeszukujemy otrzymaną tablicę i w przypadku napotkania pierwszej niepierwszej liczby aktualizujemy drzewo wstawiając 1, następna po tej liczbie liczba niepierwsza będzie miała wartość 2, jeśli napotkamy liczbę pierwszą, wyliczanie resetujemy.
Przy zapytaniach będziemy szukać wartość maksymalną w przedziale. Należy tylko liniowo rozpatrzyć początkową lewą część przedziału (liczb niepierwszych w tym przedziale może być co najwyżej 147).

Śnieg
W tym zadaniu należy wyznaczyć NWW podanych trzech liczb, które określają długość kroków, następnie zamienioną na centymetry trasę, którą badamy, dzielimy całkowicie przez otrzymany wynik NWW(a, b, c).

Kolejne wartości
W tym zadaniu należy nieco zmodyfikować ten algorytm.

Skalowanie
W treści tego zadania jest wszystko napisane. Należy jedynie pamiętać o tym, żeby nie wstawiać zbędnych spacji na końcu każdego wiersza, a na końcu ostatniego nie wstawiać znak końca linii.

Żyjątka na pewnej planecie
Po rozrysowaniu sobie schematu drzewa genealogicznego zauważamy, że na wyjściu powinny pojawić się liczby Fibonacciego zmniejszone o 1.

Małe Szyfrowanko

Szyfrem opisanym w zadaniu jest szyfr Vigenère'a . Można było stworzyć tablicę opisaną w treści i odczytywać litery za pomocą współrzędnych lub zauważyć prosty wzór: numerujemy litery A=1,B=2,C=3,…,Z=26. Litery X i Y to współrzędne litery zaszyfrowanej. Numer litery zaszyfrowanej = (X+Y), dla X+Y<=26 lub (X+Y)-26 dla X+Y>26.
Przeglądając nadesłane rozwiązania widziałem duży problem z wczytywaniem danych. Większość błędnych rozwiązań używało funkcji cin.sync() oraz cin.clear(), które nie działają na linuksie. Jeśli nie chcemy czyścić bufora można wczytać wszystkie dane jako ciągi znaków a następnie zamienić te, które domyślnie są liczbami za pomocą funkcji opisanych tu.