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 […]
Notka piąta w której wpadamy w pętle
Zadanko na dziś brzmi: Zadanie 4: Sprawa małej wagi Tomek obserwuje mrówki w przedszkolnym terrarium. Znajdują się tam dwa gatunki mrówek: czerwone i czarne. Czarnych jest więcej niż czerwonych. Aczkolwiek Tomek zauważył, że co roku liczba czarnych mrówek się podwaja, a liczba czerwonych potraja. Teraz Tomek się zastanawia za ile lat liczba czerwonych mrówek przerośnie […]
Notka czwarta w której poznajemy zmienną boolowską i podejmujemy pierwszą decyzję
Dzisiaj zmierzymy się z następującym zadaniem. Problem 3: Niech się stanie prostokąt Tomek bawi się patyczkami w przedszkolu. Każdy patyczek ma długość wyrażoną w liczbie naturalnej. Każdy patyczek ma też nacięcia co 1 centymetr, które ułatwiają łamanie patyczka na części. Patyczki są niebieskie. Tomek ma trzy patyczki, a chciałby z nich utworzyć prostokąt. Ponieważ z […]
Notka trzecia, w której dowiadujemy się o operacjach na liczbach całkowitych i kompilujemy swój pierwszy program
Dzisiaj zajmiemy się następującym zadaniem: Problem 2: Pokrycie dywanowe Po wybudowaniu muru z pierwszego zadania, Tomek zaczął układać klocki na środku przedszkola. Znalazł na dywanie czerwony prostokąt i zastanawia się ile klocków będzie potrzebował, aby go całego przykryć za pomocą kwadratowych klocków. Prostokąt ma wymiary a x b. Natomiast klocki mają wymiar c x c. […]
Notka druga, w której dowiadujemy się dlaczego warto zajmować się programowaniem konkursowym
Jest wiele powodów dla których warto zainteresować się programowaniem konkursowym. Oto kilka z nich: Ułatwiona edukacja. Tytuł finalisty Olimpiady Informatycznej daje wolny wstęp na wiele polskich uczelni. Podobnie tytuł finalisty Olimpiady Informatycznej Juniorów daje wolny wstęp do szkół ponadpodstawowych. Do tego gwarantowana ocena celująca z informatyki i zwolnienie z matury z informatyki (nawet jeśli szkoła […]
Notka pierwsza, w której poznajemy nasze pierwsze zadanie i je rozwiązujemy
Zamiast przydługawego wstępu, przejdźmy od razu do rzeczy. Oto nasze dzisiejsze zadanie: Problem 1: Polski Chiński Mur Tomek próbuje wybudować mur z klocków. Mur przypomina konstrukcję złożoną z dwóch rzędów trójkątów. Każdy z nich składa się z 2n-1 trójkątów. Rzędy są zwrócone do siebie dłuższą podstawą. Dla n = 7 konstrukcja wygląda następująco Do konstrukcji […]
Replace the Numbers
Dzisiaj chciałem wam opowiedzieć o tym jak przekombinowałem rozwiązanie zadania Replace the Numbers z treningów codeforce. Zadanie należało do tych prostszych. Mieliśmy tablicę na której mogliśmy wykonywać dwa rodzaje operacji: Wstawienie elementu v na koniec tablicy Zamiana wszystkich wystąpień elementu a na element b (będę oznaczał jako a -> b) Mając daną listę instrukcji należało […]
Drzewa Czerwono-Czarne [Potyczki]
Dzisiaj będziemy rozwiązywać zadanie Drzewa Czerwono-Czarne z Potyczek Algorytmicznych 2021. Zadanie wprawdzie z dywizji C ale było ciekawe i przyniosło mi bardzo dużo radości. W zadaniu mieliśmy dane drzewo, którego wierzchołki zostały pomalowane na czarno i czerwono. Możemy wykonać ruch polegający na wzięciu krawędzi łączącej dwa wierzchołki różnego koloru i przemalowaniu jednego z tych wierzchołków […]
Mopadulo
Dzisiaj zajmiemy się rozwiązaniem zadania mopadulo z potyczek algorytmicznych 2021. W zadaniu tym pytają się nas na ile sposobów można podzielić ciąg na spójne fragmenty tak aby suma każdego fragmentu modulo p była parzysta. Dla przykładu dla ciągu [10, 1, 5, 8] i p = 11 są trzy takie podziały: Zacznijmy od przestawienia algorytmu dynamicznego […]
Poborcy podatkowi
Dzisiaj zajmiemy się zadaniem Poborcy podatkowi z Potyczek Algorytmicznych 2021. W zadaniu mamy do dyspozycji drzewo ważone na krawędziach. Chcemy wybrać zbiór rozłącznych krawędziowo ścieżek o długości 4, który maksymalizuje sumę wartości na krawędziach. Mamy drzewo. Chcemy coś maksymalizować. Więc prawdopodobnie trzeba użyć programowania dynamicznego na drzewach. Dla każdego wierzchołka v chcemy policzyć cztery wartości: […]