Turniej szachowy
Dzisiaj rozwiążemy następujące zadanie rekrutacyjne: W turnieju szachowym gra n graczy. Turniej będzie trwał n-1 dni i w każdym dniu, każdy szachista będzie rozgrywał jedną partię. Każdy z zawodników powinien zagrać z każdym innym dokładnie raz. Napisz program, który stworzy rozpiskę rozgrywek. Zaczniemy jak zawsze od pytań do rekrutera. Kandydat: Czy możemy założyć, że n […]
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 […]