Algorytm żółwia i zająca
Dana jest tablica A[0..n] zawierająca liczby {1..n}. Napisz algorytm, który znajdzie dowolną liczbę występującą w tablicy więcej niż raz. Algorytm powinien działać w czasie liniowym i zużywać jedynie stałą ilość dodatkowej pamięci. Kandydat: Czy można modyfikować tablicę wejściową?Rekruter: Nie. Zadanie to pojawia się czasem na rozmowach kwalifikacyjnych w pewnej firmie (kod trzydzieści trzy – dziesięć), […]
Fioletowe żabki
Pewna czarownica omyłkowo odstawiła fiolkę z bardzo silną trucizną na półkę z innymi fiolkami i teraz nie pamięta, która z nich zawiera niebezpieczną substancję. Postanowiła ona przetestować fiolki za pomocą żabek, które są na truciznę odporne, ale u których po wypiciu trucizny następuje efekt uboczny w postaci zmiany koloru na fioletowy. Zmiana koloru następuje w […]
Jak zmniejszyć złożoność swojego algorytmu?
W zadaniu Wyspa z IX Olimpiady Informatycznej danych było n miast ułożonych na okręgu oraz odległości między dwoma sąsiednimi miastami. Należało znaleźć największą odległość między dwoma miastami, przy czym odległość między dwoma miastami definiujemy jako mniejszy z dystansów: zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara. Na rysunku powyżej widzimy przykładową wyspę. […]
Pionek na planszy
Podczas rekrutacji, moglibyśmy trafić na następujące zadanie: W linii prostej znajduje się n pól. Na każdym polu znajduje się pewna liczba całkowita. Na polu z numerem pierwszym znajduje się pionek. Pionek może poruszać się po planszy w prawą stronę, ale w każdym kroku nie może poruszyć się o więcej niż k pól. Jaka jest możliwie […]
Notka dziesiąta, w której poznajemy zmienne znakowe.
Zadanie 8: oRtOgRaFiA – Tomuś! – krzyknęła pani przedszkolanka – Słowa zaczynamy wielkimi literami, a potem używamy małych liter! Ile razy mam ci to powtarzać? Za karę przepiszesz cały tekst na nowo. bIedNy toMeK. pomÓż Mu wYkonAć to zAdAnie. Wejście W pierwszej i jedynej linii wejścia znajduje się słowo złożone z małych i wielkich liter […]
Czym jest atak DDoS?
Atak DoS (Denial of Service) polega na wyłączeniu pewnej konkretnej usługi w internecie. Istnieje wiele metod, aby interesującą nas usługę wyłączyć. Niektóre z nich polegają na wykorzystaniu błędu w oprogramowaniu. Dla przykładu stare systemy operacyjne bez odpowiedniego patcha wieszały się, gdy otrzymywały pakiet ping o zbyt dużym rozmiarze (ping of death). Innym przykładem jest atak […]
Notka dziewiąta, w której poznajemy tablice i zamieniamy zmienne miejscami
Zadanie na dzisiaj. Zadanie 7: Kserokopiarka 2 Przedszkolanka kazała dzieciom na zadanie domowe przynieść listę ich ulubionych liczb.– Tomku, zapomniałam o zadaniu domowym! – powiedziała Kasia – czy mogłabym spisać liczby od ciebie?– Dobrze – powiedział Tomek – tylko pozmieniaj trochę, żeby się nie skapnęła. Wejscie W pierwszej linijce standardowego wejścia, znajduje się liczba naturalna […]
Notka ósma, w której poznajemy linuksowe narzędzia przydatne w programowaniu konkursowym
Zacznijmy od następującego zadania: Zadanie 6: Kserokopiarka Tomek ma listę jego ulubionych liczb całkowitych. Chciałby podzielić się tą listą z Kasią. Tomek bardzo lubi Kasię. Poprosił Ciebie o pomoc. Treść tego zadania nie jest ambitna. Można powiedzieć, że dorównuje poziomowi tego zadania. Wejście Na standardowym wejściu znajduje się pewna liczba liczb całkowitych ai spełniających -109 […]
Notka siódma, w której odkrywamy smutną prawdę i wysyłamy nasze pierwsze zgłoszenia
Zacznijmy od smutnej prawdy. Nie zostaniesz mistrzem w programowaniu konkursowym, czytając jedynie tego bloga. Należy jeszcze rozwiązywać zadania. Zacznijmy od miejsc w których moglibyśmy rozwiązywać zadania. A jest ich sporo. Nie wszystkie z nich znam i z nie wszystkich korzystałem. Strony, które mogę polecić to: Codeforces – strona na której obecnie trenuje. Zawiera ona blisko […]
Notka szósta, w której dowiadujemy się w jaki sposób komputery zapamiętują liczby całkowite
Pewnie zastanawiacie się jakie zadanie dzisiaj rozwiążemy. A takie rozwiążemy: Zadanie 5: Wieża z klocków Tomek ułożył wieżę z klocków. Na każdym klocku znajduje się pewna cyfra. Tomek sprawdza jaką liczbę ułożył czytając cyfry od góry do dołu. Ale co to? Czyżby Tomek się pomylił? Tomkowi bardzo zależało na tym, aby liczba która powstanie, była […]