Kolorowy wąż
Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Kolorowy wąż”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. W dużym skrócie: w zadaniu graliśmy w węża i zjadaliśmy kolorowe jedzenie z planszy. Gdy wąż zjadł jedzenie, zwiększał się o jeden segment z przodu i segment ten stawał się koloru tego jedzenia. Podczas gry […]
Największa suma mniejsza niż K
Dzisiaj zajmiemy się następującym problemem rekrutacyjnym: Mamy daną tablicę A[1..N] oraz wartość K. Chcemy znaleźć spójną podtablicę A[i..j] o jak największej sumie, ale mniejszej od K. Zacznijmy od pytania do rekrutera: Kandydat: Czy tablica może zawierać elementy ujemne?Rekruter: Tak. To pytanie wynika z tego, że istnieje algorytm rozwiązujący problem w czasie liniowym dla tablic z […]
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 […]