Przeskocz do treści

Delta mi!

Loading
  1. Algorytmy Informatyczny kącik olimpijski

    Przeciąganie liny

    W tym miesiącu proponujemy zadanie Przeciąganie liny, które pojawiło się w podwarszawskim Józefowie, podczas zeszłorocznej Bałtyckiej Olimpiady Informatycznej. Zadanie opisuje problem optymalizacji znanej wakacyjno-urlopowej zabawy. Co ciekawe, warstwa fabularna proponowanego rozwiązania - choć pozostaje w podobnych klimatach - to jednak odchodzi od liny na rzecz plecaka.

  2. Algorytmy Informatyczny kącik olimpijski

    Coś się popsuło

    W noworocznym kąciku omówimy zadanie Wykrywanie wrednej usterki pochodzące z zeszłorocznej Międzynarodowej Olimpiady Informatycznej, która odbyła się w Kazaniu (Rosja). Autorzy zadania oczekują od nas, że pomożemy zdiagnozować usterkę, która wkradła się do bazy danych zaimplementowaną przez niefrasobliwego inżyniera Ilszata.

  3. Algorytmy Informatyczny kącik olimpijski

    Kolorowanie cyklu

    Zagadnienie kolorowania cyklu niejednokrotnie pojawiało się na konkursach programistycznych, m.in. na Mistrzostwach Europy Środkowej w Programowaniu Zespołowym (zadanie Beijing Guards z roku 2004), czy też Mistrzostwach Polski w Programowaniu Zespołowym (zadanie Słoneczna wyspa z roku 2010).

  4. Algorytmy Informatyczny kącik olimpijski

    Wykładzina

    W zeszłym miesiącu zajmowaliśmy się uogólnieniem następującego zadania: dla danego kwadratu rozmiaru |n n podzielonego na  2 n pól, z których niektóre były zabronione, należało znaleźć prostokąt o największym polu, który nie zawierał żadnego zabronionego pola. W tym numerze rozważymy jeszcze inną wariację tego zadania, a mianowicie będziemy szukać największych prostokątów, które zawierają co najwyżej |K zabronionych pól (nazwiemy je prostokątami prawie pustymi).

  5. Algorytmy Informatyczny kącik olimpijski

    Zliczamy puste prostokąty

    W tym miesiącu zajmiemy się dość klasycznym zadaniem. Dany jest kwadrat rozmiaru |n n podzielony na  2 |n pól, przy czym niektóre pola są zabronione. Dowolny zawarty w tym kwadracie prostokąt, który nie zawiera żadnego pola zabronionego, nazwiemy prostokątem pustym. Należy znaleźć pusty prostokąt o jak największym polu.

  6. Informatyka Informatyczny kącik olimpijski

    Jeszcze dwa zadania do plecaka

    W kąciku kontynuujemy przygodę z zadaniami, do których rozwiązania przydaje się znajomość problemu plecakowego. Tym razem w nieco trudniejszej jego wersji, w której każdy przedmiot ma swój rozmiar m oraz wartość w Standardowe pytanie, które możemy wtedy zadać, to np. jaka jest największa sumaryczna wartość przedmiotów, które możemy zapakować do plecaka, nie przekraczając jego udźwigu M

  7. Algorytmy Informatyczny kącik olimpijski

    Filary

    W tym kąciku omówimy zadanie Filary, które pojawiło się na Akademickich Mistrzostwach Polski w Programowaniu Zespołowym 2014. Zadanie, pomimo prostej treści i (jak się za chwilę przekonamy) całkiem prostego rozwiązania, sprawiło sporo kłopotów drużynom startującym w zawodach i ostatecznie zostało rozwiązane tylko przez jedną z nich.

  8. Algorytmy Informatyczny kącik olimpijski

    Multizbiory

    W tym kąciku proponuję zadanie polecane przez mojego korespondenta w Jekaterynburgu, mieście znanym również z turnieju Ural Sport Programming Championship, którego zeszłoroczną atrakcją był bezwzględny pojedynek pięciu najlepszych drużyn z Rosji z pięcioma najlepszymi drużynami z Chin. Popatrzmy na zadanie, którego nie udało się rozwiązać żadnej z nich!

  9. Algorytmy Informatyczny kącik olimpijski

    Karty

    W tym kąciku zmierzymy się z zadaniem Karty z Potyczek Algorytmicznych 2013. Oryginalne sformułowanie zadania dotyczyło kart perforowanych, my jednak przedstawimy je nieco inaczej, przy okazji wprowadzając niejawnie kilka nieznaczących uproszczeń.

  10. Algorytmy Informatyczny kącik olimpijski

    Infiltracja

    Tym razem zajmiemy się zadaniem z finałów Akademickich Mistrzostw Świata w Programowaniu Zespołowym 2012, które odbyły się w Warszawie. Zadanie zatytułowane Infiltration zostało rozwiązane przez 31 spośród 112 drużyn i było średnim pod względem trudności zadaniem na tych zawodach.

  11. Algorytmy Informatyczny kącik olimpijski

    Czworokąty wypukłe

    W tym kąciku zajmiemy się zadaniem Quadrilaterals z obozu w Petrozawodsku w 2006 roku. Na płaszczyźnie dane jest math punktów w położeniu ogólnym (tzn. żadna trójka punktów nie leży na jednej prostej). Należy wyznaczyć liczbę czworokątów wypukłych, których wierzchołki znajdują się wśród podanych punktów.

  12. Algorytmy Informatyczny kącik olimpijski

    Odśnieżanie

    Zadanie Odśnieżanie z zeszłorocznego Obozu Naukowo-Treningowego im. A. Kreczmara można sformułować w języku teorii grafów następująco. W nieskierowanym, ważonym, spójnym grafie math  wyróżniono cztery wierzchołki. Należy usunąć część krawędzi z grafu tak, żeby nadal istniały ścieżki pomiędzy każ parą wyróżnionych wierzchołków i żeby suma wag krawędzi, które pozostały w grafie, była jak najmniejsza.

  13. Algorytmy Informatyczny kącik olimpijski

    Dwa przyjęcia

    W niedawno wydanej książce W poszukiwaniu wyzwań – zbiorze zadań z konkursów programistycznych – Filip Wolski opisał rozwiązanie zadania Dwa przyjęcia z finału XII Olimpiady Informatycznej. W zadaniu tym występuje math osób, z których niektóre się znają (wiemy które). Chcemy podzielić ten zbiór na dwa rozłączne podzbiory (przyjęcia) w taki sposób, aby zmaksymalizować liczbę osób, które mają parzystą liczbę znajomych na przyjęciu, na którym przebywają...