Olimpijskie kółko informatyczne
OFEK

Czas i miejsce

STRONA PRZESTAJE BYC AKTUALNA

Nowa strona kolka: kolko.ofek.waw.pl

UWAGA! ZMIANA TERMINU!!! KÓŁKO JEST TERAZ O GODZINIE 17

Kółko odbywa się w czwartki o godzinie 17 w Liceum Słowackiego, w auli na pierwszym piętrze. Liceum to znajduje się przy Trasie Łazienkowskiej na wysokości przystanku Aleja Wielkopolski.

Prowadzący:

Zadania

Co tydzień jest możliwość rozwiązania i przysłania pewnego zadania. Aktualnie rozwiązania należy wysyłać na adres parys@mimuw.edu.pl (planujemy wkrótce wprowadzić wysyłanie przez stronę). Rozwiązaniem powinien być program w Pascalu lub C / C++, który robi to co jest podane w zadaniu. W szczególności powinien wczytywać dane ze standardowego wejścia, wynik wypisywać na standardowe wyjście, nie wypisując przy tym żadnych śmieci. Uwaga!!! Przy rozwiązywaniu różnych zadań w Pascalu warto używać typu longint, a nie integer. W integer mieszczą się tylko małe liczby (do 32767).

Aktualne zadania:

Na rozwiązanie zadań są dwa tygodnie. W drugim tygodniu maksimum punktów do zdobycia jest o 1 punkt mniejsze niż w pierszym.
Permutacje (do 2. grudnia)
Szachownica (do 9. grudnia)

Poprzednie zadania:

Ciąg (do 25. listopada) Przykładowe rozwiązanie
Reszty (do 18. listopada) Przykładowe rozwiązanie
Mrówki (do 4. listopada) Przykładowe rozwiązanie

Ranking

Kliknij tutaj

O czym będzie

Kółko przeznaczone jest dla uczniów szkół średnich, którzy pragną poszerzyć swoją wiedzę w zakresie algorytmiki, programowania, itp. Przedstawimy różne podejścia do rozwiązywania problemów informatycznych oraz pokażemy trochę często przydatnych standardowych algorytmów. Będzie pewnie sporo ciekawych zadań. Zobacz też listę tematów, które prawdopodobnie pojawią się na kółku.

21.X.2004

Powiedzieliśmy coś o podstawach złożoności obliczeniowej, czyli jak odróżnić program szybki od wolnego. A więc należy patrzeć na to, czy czas działania jest proporcjonalny do N, do N2, do N3, gdzie N jest rozmiarem danych, na których się operuje w zadaniu. Jeśli N jest na przykład rzędu 1000000, to przejście z N do N2 zmienia czas działania około 1000000. Zatem najważniejsze jest wymyślić dobry algorytm, mający małą złożoność. A to czy dzięki jakimś sztuczkom nasz program będzie działał kilka razy szybciej to już niewiele zmieni. Należy również (prawie zawsze) unikać programów, których czas działania jest wykładniczy (tzn. proporcjonalny na przykład do 2N).

Ponadto przedstawiliśmy podstawy Pascala. Zobacz też krótki opis i parę przykładowych programików. Aby pisać programy w Pascalu należy używać kompilatora. Podstawowym jest Free Pascal. Wydaje mi się, że nieco przyjaźniejszy w użyciu jest Turbo Pascal, niestety jest to program jeszcze pod DOS i dlatego ma różne ograniczenia związane z ilością używanej pamięci.

28.X.2004

W tym tygodniu będzie o algorytmach zachłannych. Algorytm zachłanny charakteryzuje się tym, że w kolejnych krokach rozszerza budowane rozwiązanie o optymalny w danej chwili element. Zobacz parę przykładowych problemów, przy rozwiązywaniu których wykorzystuje się to podejście.

4.XI.2004

Programowanie dynamiczne. Liczymy rozwiązanie dla kolejnych, coraz to większych podproblemów i zapamiętujemy. Rozwiązanie dla większego problemu wynika jakoś w prosty sposób z mniejszych. Patrz tutaj.

18.XI.2004

Było o kopcach i drzewach licznikowych. O kopcach coś się wkrótce pojawi. Czytaj tutaj o drzewach licznikowych (napisane przez Andrzeja Gąsiennicę-Samka).

25.XI.2004

Głównie omówiliśmy zadania z pierwszego etapu Olimpiady Informatycznej.