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.