Delta mi!

W tej edycji kącika znowu cofniemy się w czasie do 2005 roku, do pierwszej edycji konkursu Potyczki Algorytmiczne, i omówimy zadanie z finału próbnego tego konkursu pt. Drogi (bardzo podobne zadanie pojawiło się zresztą w jeszcze bardziej zamierzchłej przeszłości, na Międzynarodowej Olimpiadzie Informatycznej w 1996 roku).

W tym miesiącu omówimy zadanie, które pojawiło się w pierwszej edycji konkursu Potyczki Algorytmiczne, w roku 2005.

Wyobraź sobie, Drogi Czytelniku, że jesteś kapitanem okrętu wojennego i w trakcie jednej z misji znalazłeś się na środku morza leżącego na terytorium wroga. Wiesz, że wróg rozmieścił w tej strefie pewną (skończoną) liczbę radarów. Każdy radar ma określony zasięg, być może różny w przypadku różnych radarów, i jest w stanie wykryć każdy podejrzany obiekt, który znajdzie się w jego zasięgu. Naszym siłom wywiadowczym udało się wykraść plan rozmieszczenia radarów. Na jego podstawie chcesz stwierdzić, czy możesz wydostać się z wrogich wód niezauważony przez radary.

Wyobraźmy sobie biedną sierotkę, której macocha nakazała oddzielić groch od fasoli. Chcąc nie chcąc, dziewczę siada w kącie izby przed pokaźnym kopcem grochu pomieszanego z fasolą i zaczyna pracę. Praca jest niezwykle monotonna: sierotka bierze nasiono z górki i jeśli to fasola, odrzuca je na lewą stronę, a jeśli groch – na prawą; i tak w kółko...

W dniach 14–18 maja br. w Warszawie odbyły się finały najstarszego i najbardziej prestiżowego konkursu informatycznego na świecie, ACM International Collegiate Programming Contest (ACM ICPC), nazywanego też Akademickimi Mistrzostwami Świata w Programowaniu Zespołowym.

Czy zastanawiałeś się kiedykolwiek, drogi Czytelniku, na czym zarabiają największe firmy informatyczne w Dolinie Krzemowej? Google nie pobiera opłat za wyszukiwanie informacji, konto na Facebooku jest darmowe, Yahoo nie żąda pieniędzy za e-mail... Z punktu widzenia użytkownika praktycznie wszystko wydaje się bezpłatne. Dlaczego zatem powyższe firmy wyceniane są na miliardy dolarów? Kto pokrywa koszty utrzymania serwerów, zużycia prądu czy pensji pracowników?

Nie jest aż tak trudno założyć firmę informatyczną. Potrzebny jest do tego dobry pomysł na produkt, którego ludzie będą chcieli używać (na przykład urządzenie elektroniczne, program komputerowy lub portal internetowy), oraz kilku programistów-zapaleńców, którzy będą skłonni poświęcić kilka miesięcy życia na stworzenie wstępnej, działającej wersji produktu. W ten właśnie sposób powstała większość znanych obecnie firm z branży technologii informacyjnych, takich jak Microsoft (początkowo związany z interpreterem języka BASIC), Apple (pierwszym produktem był komputer do samodzielnego złożenia), Google (wyszukiwarka) czy Facebook (portal społecznościowy)...

 dniach od 27 do 30 marca 2012 r. w Trójmieście odbyły się zawody III stopnia XIX Olimpiady Informatycznej. Do finału zostało zakwalifikowanych rekordowo wielu, bo aż 100 zawodników. W ciągu dwóch dni zawodów finałowych zawodnicy mieli do rozwiązania w sumie sześć zadań programistycznych ocenianych od 0 do 100 punktów.

Chyba wszyscy lubimy liczby pierwsze. Szczególne wrażenie robią te naprawdę duże, wydają się skrywać w sobie jakąś nadzwyczajną tajemnicę: dlaczego akurat one stały się swego rodzaju wybrańcami spośród innych liczb i mają tak niezwykłe właściwości?

Tym razem omówimy zadanie Robot sortujący (ang. Robotic Sort) z Mistrzostw Europy Środkowej w Programowaniu Zespołowym 2007 (CERC 2007).

Tym razem zajmiemy się zadaniem Nurkowanie z Obozu Naukowo-Treningowego im. Antoniego Kreczmara w 2007 roku.

Jednym z pierwszych zadań, z jakimi musi zmierzyć się każdy uczący się algorytmów lub programowania, jest znajdowanie minimum w tablicy (ciągu liczb). Oznaczmy taką tablicę przez

W fizyce szkolnej nieustannie przewijającym się motywem są dwa znane miasta: miasto A oraz miasto B. W kryptografii takimi gwiazdami są Alicja i Bob, którzy ciągle się komunikują, uwierzytelniają, a zwykle przeszkadza im w tym złowroga Ewa.

W tym kąciku omówimy zadanie Jaskinia, które pojawiło się w zeszłym roku na Akademickich Mistrzostwach Polski w Programowaniu Zespołowym.

Jedną z najlepiej znanych metod wyznaczania liczb pierwszych jest sito Eratostenesa. Opiera się ona na spostrzeżeniu, w zasadzie oczywistym, że jak wyrzucimy wszystkie liczby złożone, to zostaną same liczby pierwsze...

W tym artykule omówimy zadanie Prostokąt arytmetyczny z Akademickich Mistrzostw Polski w Programowaniu Zespołowym 2011.

W tym miesiącu opiszemy zadanie Monety, które pojawiło się na Potyczkach Algorytmicznych w roku 2010.

Poszukiwanie pierwiastków wielomianu jest jednym z podstawowych zagadnień rozważanych we wszystkich naukach ścisłych. W tym artykule zajmiemy się czymś znacznie prostszym: sprawdzaniem, czy dana liczba jest pierwiastkiem zadanego wielomianu.

W tym kąciku rozwiążemy zadanie Prostokąty (Rectangles), które pojawiło się w 2007 roku na konkursie organizowanym przez MIT w serwisie spoj.pl.

W tym miesiącu omówimy zadanie, które rozwiązywali uczestnicy Obozu Naukowo-Treningowego im. A. Kreczmara w 2009 r.

Któż z nas nie bawił się jako dziecko w chowanego? Zabawa ta sprawia dzieciom wiele radości, mimo że z algorytmicznego punktu widzenia jest bardzo prosta. Jeżeli bowiem wszyscy ukrywający się czekają uczciwie w swoich kryjówkach, to zawsze uda się ich znaleźć – wystarczy, jeżeli szukający przejrzy wszystkie miejsca.

W grafie nieskierowanym możemy obliczyć stopień każdego wierzchołka, czyli liczbę krawędzi incydentnych z tym wierzchołkiem. Przykładowo, dla grafu-koperty otrzymujemy w ten sposób ciąg stopni 4, 4, 3, 3, 2. Wykonanie takiego przekształcenia dla danego grafu jest naprawdę proste. Możemy jednak postawić pytanie odwrotne: czy mając dany ciąg liczb, możemy stwierdzić, czy odpowiada on stopniom wierzchołków jakiegoś grafu nieskierowanego, a jeśli tak, zrekonstruować ten graf?

Zadanie omawiane w tym kąciku pochodzi z obozu treningowego drużyn rosyjskich z 2008 roku (autor zadania: Andrew Stankevich).

Aby opisać falę akustyczną, wytwarzaną przez głośnik, musimy podać, jak ciśnienie powietrza zmienia się w czasie – do tego wystarczy znać przebieg jednej wielkości – wychylenia membrany głośnika. Jeśli nasz głośnik jest podłączony do komputera, to stosowny opis fali jest produkowany przez kartę dźwiękową, która z kolei pobiera dane zapisane na jakimś nośniku danych. Na początku lat 80. XX wieku pojawił się nowy nośnik danych audio: płyta CD.

Kilkanaście lat temu zgubiłem się w lesie. Nie na tyle, żeby sytuacja była beznadziejna...