Strona poświęcona algorytmom

Autor: algoorithmspl

Obozy algorytmiczne / matematyczne

Obozy algorytmiczne / matematyczne

Obozy na których już byli uczestnicy kółka MOI/OI: Talent / Polska (12-19 lat) Tygodniowe obozy algorytmiczne przygotowujące do olimpiad (wakacje / rok szkolny). Szkoła podstawowa/średnia:          http://talent.edu.pl/obozy/ Obóz Naukowy Politechniki Warszawskiej / Polska Są różne warsztaty między innymi dotyczące informatyki i programowania […]

KÓŁKO MOI – 24 LISTOPADA 2018

KÓŁKO MOI – 24 LISTOPADA 2018

Witajcie, 24.11.2018 Dziękuję za dzisiejszy pracę. Każda kropla naszego umysłowego wysiłku przenosi nas na wyższy poziom. A dziś tych kropli było dużo. Naprawdę dostaliście dziś 2 mocne zadanie. Dziękuję ponownie Mikołajowi Bulge za super zadanie, omówienie i podzielenie się swoimi doświadczeniami. W najbliższy piątek Mikołaj […]

Testy do zadań I etap MOI 2018/2019

Testy do zadań I etap MOI 2018/2019

W komentarzach wrzucajcie linki do swoich testów z  I etapu MOI-a 2018/2019 + krótki opis:
* jakie zadanie
* charakter testów (jakie zakres wartości, …)

Testy do wszystkich zadań z I etapu MOI-a autorstwa Piotra Pływacza:
Każde zadanie ma około 1000 testów + plik readme z opisem testów

http://gurago.pl/m2018/IetapMOIa-PP.zip

Testy do zadań Jabłka i gruszki (I etap MOI 2018/2019):
Test 1
http://gurago.pl/m2018/testy_ig.zip

Test 2
http://gurago.pl/m2018/testy_pp.zip
1-300:  n, m < 50;   k < 200;   a[i] < 100
301-600: n, m, k, a[i] < 1000
601-900: n, m < 5000; k, a[i] <= 10^6
901-1000: n, m <= 10^6; k, a[i] <= 10^9

 

Testy do Piłeczek na Podłodze autorstwa Ignacego Gębusia:
Sprawdzone dwoma metodami.
kategorie:
a: n=5 x,y w przedziale 0-5
b: n=100 x,y w przedziale 0-100
c: n=500 x,y w przedziale 0-1000000000
d: n=1000 x,y w przedziale 0-1000000000

https://igebus.pl/nextcloud/index.php/s/dMLmH7d8TSrpB8F

 

Pakiet sprawdzarek Linuxowych Mikołaja Bulge:
http://gurago.pl/m2018/xd.zip

 

KÓŁKO MOI – 10 LISTOPADA 2018

KÓŁKO MOI – 10 LISTOPADA 2018

2018.11.10 Witajcie, Dziękuje Wam za dzisiejsza zabawę. ——————————– Jeśli zrobiliście dzisiejsze zadanie możecie być dumni. Macie super szanse na finał MOI-a, na wielkie święto informatyki w Gdyni. Potrzeba tylko woli walki, 4 zadań tygodniowo! Jeśli ktoś nie zrobił tego zadania – nie szkodzi. Prośba o […]

Kółko MOI – 17 listopada 2018

Kółko MOI – 17 listopada 2018

Kochani, 2018.11.10 Zapraszam na jutrzejsze/sobotnie kółko MOI. 8:00 – 10:30, sala 217, Staszic. —— 8:00 – quiz 8:10 – omówienie pracy domowej 8:30 – 10:30 * zadanko proste – nowy algorytm * zadanko trudniejsze (Mikołaj Bulge) * jak sprawdzać masowo zadania (Mikołaj Bulge) – rozwinięcie […]

Kółko MOI – 28 października 2018

Kółko MOI – 28 października 2018

Dziękuję serdecznie za przesłane rozwiązania zadań.
W pracy domowej dochodzi jedno zadanie z mojego ulubionego USACO.
Całość czasu poświęcamy na OI-a.

—-
W załączeniu zgoda na udział w kółku MOI.
Prośba o wydrukowanie, wypełnienie i przyniesienie w piątek/sobotę tych którzy do tej pory tego nie zrobili.

——-
Na poprzednim kółku, gdy rozwiązywaliśmy zadanie zając, Paweł Jastrzębski napisał Find And Union własną metodą.
Inaczej niż ja przedstawiałem, inaczej niż podchodzi się w podręcznikach.
Sam też na zajęciach wymyślił usprawnienie Find And Union.

Bardzo Was zachęcam do krytycznego podejścia do wiedzy, do sposobów rozwiązania, do algorytmów.

Tylko wtedy, gdy będziecie pytać
* dlaczego ten algorytm tak właśnie działa?
* czy na pewno to jest poprawne?
* zaraz, zaraz – przecież można lepiej!
tylko wtedy wymyślicie coś naprawdę nowego i tylko wtedy posuniecie świat do przodu.

Broń Boże, nie wolno Wam przyjmować żadnych twierdzeń, algorytmów jako prawdy objawionej, jako dogmatów z którymi się nie dyskutuje.
Wręcz odwrotnie, im więcej będziecie kwestionować to co Wam przekazuję, pytać dlaczego, szukać słabego punktu tym będę bardziej zadowolony.
Koniec końców, moim marzeniem jest byście pokazali mi, że nie mam racji, że można szybciej, że można lepiej.

Nasze kółko to grupa osób która ma wywrócić świat algorytmiki.
Pokazać, że coś co robi się w n^2 można w n.
A w ogóle można zupełnie inaczej na to spojrzeć i zamiast w w czasie n można zrobić w czasie logn.

Macie zaprzeczyć dotychczasowej wiedzy tak jak Einstein zaprzeczył Newtonowi.
Jeśli nie dziś, to za 5 czy 10 lat.

Musicie mieć swobodę, pewność siebie, naukową zuchwałość.
Bo czyż Einstein nie był zuchwały by gdy mówił, że Newton nie ma racji?

Ale tylko taka osoba wywróci ten świat do góry nogami.

Dlatego kombinujcie, pokazujcie że nie mam racji, wymyślajcie zupełnie inne podejścia.
Na to liczę, tego oczekuję, wiem, że każdego z Was stać na kluczowe odkrycie.

To jest dopiero zabawa!

—–
Praca domowa – całość
Wszystkie zadania – nagroda specjalna, bez jednego zadania – nagroda główna, pojedyncze zadania – nagrody zwykłe

Zadanie 1 – Klubowicze 2
https://sio2.mimuw.edu.pl/c/oi26-1/p/
Warunek zaliczenia:
Przechodzi testy na forum OI-a:
https://sio2.mimuw.edu.pl/c/oi26-1/forum/

Zadanie 2 – Chemical table
http://codeforces.com/contest/1012/problem/B
Warunek zaliczenia:
    * screen z wynikiem na 70%+
    * krótki opis algorytmu, przesłany kod

Zadanie 3 – Kulki
https://zadania.oig.edu.pl/OIG/contest_rounds/view/25515313
Warunek zaliczenia:
    * screen z wynikiem na 70%+
    * krótki opis algorytmu, przesłany kod

Zadanie 4 – Hurtownia
https://szkopul.edu.pl/p/default/problemset/oig/2
Warunek zaliczenia:
    * screen z wynikiem na 70%+
    * krótki opis algorytmu, przesłany kod

Zadanie 5 – TRAPPED IN THE HAYBALES (SILVER)
http://www.usaco.org/index.php?page=viewproblem2&cpid=550
Warunek zaliczenia:
    * screen z wynikiem na 70%+
    * krótki opis algorytmu, przesłany kod

Walczymy!
Daniel

Kółko MOI – 3-8 listopada 2018

Kółko MOI – 3-8 listopada 2018

8.11 Zapraszam na jutrzejsze, piątkowe kółko MOI. Jutro trudniejsze zadanie z II etapu, średnie z finału MOI-a. Zaczynamy 15:15 od quizu. Potem zadanko. Sale 217/101 / Staszic / Nowowiejska 37a / Warszawa. —— Do 12 listopada jest I etap OI-a. Szczęśliwie jest to dzień wolny. […]

Loteria

Loteria

Nietypowa Bydgoszcz W Bydgoszczy jest nietypowa loteria, która składa się z dwóch losowań: Najpierw losujemy liczbę k Następnie ze podanego nam zbioru z n liczb losujemy 2 dowolne liczby: p1 i p2 Gracz wygrywa nagrodę tylko wtedy, gdy p1 + p2 = k. Ala ma […]

FSO

FSO

Samochody

Fabryka Samochodów Osobowych (FSO) produkuje wiele rodzajów samochodów. Każdy samochód posiada następujące atrybuty:

  • cena
  • kolor
  • ciężar

 

Nowe raporty

Z uwagi na duży popyt na nowe samochody zarząd poprosił dział informatyki o nowe raporty. Pilnie potrzebne są następujące raporty:

  1. sumaryczny koszt wszystkich samochodów o tym samym ciężarze
  2. sumaryczny ciężar samochodów o tym samym kolorze

 

Szybkość, liczy się tylko szybkość

Fabryka produkuje kilkaset samochodów na godzinę. Dlatego raporty muszą być generowane bardzo szybko – maksymalnie w czasie N*logN gdzie N to ilość samochodów w zestawieniu.

 

Wejście

W pierwszej linii znajdują się 1 liczba oznaczająca ilość wyprodukowanych aut – ilość aut w zestawieniu

            1 <= liczba_aut <= 500 000 (liczba wyprodukowanych aut)

W kolejnych liczba_aut liniach znajdują się 3 liczby oznaczające następujące informacje o każdym wyprodukowanym samochodzie:

            cena kolor ciezar

gdzie:

            1 <= cena <= 106

            1 <= kolor <= 1015

            10 <= ciezar <= 1014

 

Wyjście

Twój program powinien wypisać następujący raport:

Koszt aut o tym samym ciezarze (tekst)

C – Liczbę oznaczającą ilość różnych ciężarów aut w zestawieniu

C linii uporządkowanych rosnąco względem ciężaru a w każdej linii 2 liczby

            ciezar sumaryczny_koszt_aut_o_tym_ciezarze

Ciezar aut o tym samym kolorze (tekst)

K – Liczbę oznaczającą ilość różnych kolorów aut w zestawieniu

K linii uporządkowanych rosnąco względem koloru a w każdej linii 2 liczby

            kolor sumaryczny_ciezar_aut_o_tym_kolorze

 

Przykład 1

Wejście

5                      (Jest 5 aut w zestawieniu)

2 3 10             (auto nr 1: cena 2, kolor 3, ciężar 10)

5 1 20             (auto nr 2: cena 6, kolor 1, ciężar 20)

6 4 10             (auto nr 3: cena 7, kolor 4, ciężar 10)

1 1 10             (auto nr 4: cena 1, kolor 1, ciężar 10)

9 4 20             (auto nr 5: cena 9, kolor 4, ciężar 20)

Wyjście

Koszt aut o tym samym ciężarze

10 9                (najmniejszy ciężar 10, koszt wszystkich auto o tym ciężarze: 8)

20 14              (ciężar nr 2 to 20, koszt wszystkich auto o tym ciężarze: 5)

Ciezar aut o tym samym kolorze

1 30                (najmniejszy kolor 1, suma ciężarów aut o tym kolorze to 30)

3 10                (kolejny kolor to 3, suma ciężarów aut o tym kolorze to 10)

4 30                (kolejny kolor to 4, suma ciężarów aut o tym kolorze to 30)

 

Rozwiązanie zadania “Sklep” z 3 etapu I OIG

Rozwiązanie zadania “Sklep” z 3 etapu I OIG

W tym artykule rozwiążemy zadanie Sklep z 3 etapu I Olimpiady Informatycznej Gimnazjalistów , które można znaleźć poniżej:          https://szkopul.edu.pl/p/default/problemset/oig/1   Zadanie Sklep – Co mamy zrobić? W zadaniu sklep musimy podsumować ilość towaru o takim samym numerze wypisać podsumowanie: numer produktu […]