Kurs maturalny z języka angielskiego!
kurs-maturalny-jezyk-angielski

PROGRAMOWANIE I ALGORYTMY

Zajęcia maturalne z informatyki
Olimpiada Informatyczna Juniorów
    Prowadzący: Marcin Kasprowicz
  • właściciel serwisu algorytm.edu.pl
  • wrzesień 2024 — start zajęć
  • czytaj więcej

Omówienie zadań z VIII rundy


Drzewo binarne II
To zadanie można rozwiązać na wiele sposobów. Nasza propozycja jest taka. Tworzymy wyzerowaną tablicę na 64 elementy. Następnie każdą wczytaną liczbę skracamy przez dwa, aż otrzymamy 0. Każde takie skrócenie powoduje przejście o poziom wyżej na drzewie. Liczba skróceń tej liczby, to poziom na której ona pierwotnie się znajdowała. Do zliczenia ilości liczb na danym poziomie służy podana wcześniej tablica. Żadna liczba mieszcząca się w typie long long nie może znajdować się na poziomie wyższym niż 63.
 
Gra w bańki
To zadanie można w prosty sposób rozwiązać używając struktury stos. Wrzucamy kolejne wartości baniek, które poruszają się w prawą stronę. Napotykając bańkę przesuwającą się w lewym kierunku, do pary pobieramy bańkę ze stosu (jeśli nie jest oczywiście pusty) i dokonujemy konfrontacji.
 
Lider w macierzy
Wykonujemy preprocessing. Przechodzimy od lewej do prawej strony macierzy wyznaczając kolejnych liderów. Gdy znajdziemy się po prawej stronie, obniżamy się o jeden wiersz i poruszamy się w lewo itd. Przy każdym takim przejściu usuwamy tylko jedną kolumnę (wiersz) i dodajemy tylko jedną po prawej stronie. Wartości w macierzy nie przekraczają miliona, więc można stworzyć odpowiednią tablicę do zliczania wartości. Ilość elementów dla lidera jest z góry znana, więc bez problemu możemy na bieżąco określać, czy jest lider w podmacierzy. Na zapytania odpowiadamy w czasie stałym
 
Tysiące talii kart
Wzorcowe rozwiązanie ma złożoność liniową. Tworzymy wyzerowaną tablicę o długości ilości talii + 1. Następnie dla każdego początku przedziału zwiększamy wartość tablicy o 1, a na końcu przedziału zmniejszamy o 1. Następnie poruszamy się przez wszystkie elementy tablicy zwiększając każdą następną o wartość poprzedniej. W ten sposób wiemy, ile razy była położona na spód karta.
To zadanie można było rozwiązać także drzewem przedziałowym.
 
Piq
W tym zadaniu wystarczy odwołać się do twierdzenia o wymiernych pierwiastkach wielomianu.
Zjazd koordynatorów
Algorytm grafowy – przeszukiwanie wszerz.
Parkrun Działdowo II
Można rozwiązać to zadanie wykorzystując drzewo przedziałowe.