Wielki Zderzacz Termionów
Autorzy zadań do Potyczek Algorytmicznych trzymają naprawdę wysoki poziom. Jak oni wymyślają te zadania? Nie wiem. Krótkie streszczenie treści zadania W zadaniu Wielki Zderzacz Termionów mamy trzy rodzaje cząstek elementarnych: Czerwony (C), Zielony (Z) i Niebieski (N). Cząstki elementarne ustawia się w rzędzie i reagują ze sobą. Dwa sąsiednie termiony Czerwone mogą zamienić się w […]
Liczba potyczkowa
Rozpoczęła się runda próbna tegorocznych Potyczek Algorytmicznych. O tym co można sprawdzić w rundzie próbnej napisałem w poprzedniej notce. Zwykle zadania w dniu próbnym są bardzo łatwe. Klasycznym przykładem jest zadanie w którym należy dodać dwie liczby do siebie. Ja chciałbym wrócić pamięcią dwa lata wstecz, kiedy to na dniu próbnym pojawiło się zadanie, którego […]
Co zrobić w dniu próbnym
Żaden szanujący się konkurs algorytmiczny, nie odbywa się bez dnia próbnego (albo chociaż sesji próbnej). Dzień próbny jest potrzebny organizatorom, aby upewnić się, że wszystko zostało dopięte na ostatni guzik. Działa sprawdzaczka, zadania zostały odpowiednio załadowane, komputery zostały odpowiednio przygotowane i tak dalej. Dzień próbny jest również istotny dla zawodników, aby mogli się zapoznać ze […]
Płytkie nawiasowania
Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Płytkie nawiasowanie”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. Opiszę tu pokrótce o co w zadaniu chodziło, ale zanim to nastąpi to wytłumaczę czym jest poprawne nawiasowanie. Poprawne nawiasowanie to taki napis złożony z symboli ( oraz ) w którym każdy nawias otwierający ma […]
Zboże
Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Zboże”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. W dużym skrócie w zadaniu było dane ukorzenione drzewo z wagami na krawędziach oraz ciąg wierzchołków z tego drzewa. Dla każdego wierzchołka z ciągu należało policzyć jego sumaryczną odległość do wszystkich wierzchołków leżących w ciągu przed […]
Wyprzedzanie
Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Wyprzedzanie”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. W dużym skrócie: jednym pasem jedzie n ciężarówek. Pasem równoległym ciężarówki wyprzedza Bitazar (zły brat bliźniak Bajtazara). Policja Bajtocka chce teraz ukarać Bitazara mandatem. Wysokość mandatu zależy od tego ile razy Bitozar mógł podczas wyprzedzania zjechać […]
Pociąg towarowy
Na XXX Olimpiadzie Informatycznej zawodnicy mierzyli się z zadaniem “Pociąg towarowy”. Pełną treść zadania można znaleźć na oficjalnej stronie Olimpiady. W dużym skrócie w zadaniu mieliśmy dany ciąg oraz jego podciąg. Niestety – mając takie dane nie jesteśmy w stanie określić które dokładnie elementy zostały wybrane do podciągu. Dla przykładu: jeśli ciągiem jest 1 3 […]
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 […]