Posts

Część 1 W dzisiejszym zadaniu mamy na wejściu zbiór kluczy i zamków, naszym zadaniem jest obliczyć ile w sumie kluczy pasuje do ilu zamków. Input wygląda w ten sposób: ##### ##.## .#.## ...## ...#. ...#. ..... ..... #.... #.... #...# #.#.# #.### ##### ..... ..... #.#.. ###.. ###.# ###.# ##### Zamki to te macierze które w górnym rzędzie mają same #, a klucze mają w dolnym rzędzie same #, klucz mieści się w zamku jeśli ilość # w każdej kolumnie, nie przekracza wysokości kolumny. Właściwie w treści zadania mamy podane całe jego rozwiązanie, widać że autor nie chciał jak najbardziej ułatwić nam dzisiejsze zadanie. ...

W dzień wigilijny miałem nadzieję że zadanie będzie prosteze gdyż chciałem spędzić go z rodziną, dostaliśmy zadanie którego część 2 była lekkim wyzwaniem ale całkiem szybko zrozumiałem co trzeba w niej zrobić. Zadanie Na wejściu otrzymujemy listę bramek logicznych które mają po dwa wejścia i jedno wyjście, dostajemy też wartości na wejściach to pewnej części bramek. Naszym zadaniem jest zasymulować działanie tych bramek i zwrócić wartości na wyjściach zaczynających się na literę z ...

Zadanie Dzisiejsze zadanie jest klasycznym zadaniem z teorii grafów. W naszym zadaniu komputery to wierzchołki, oznaczone są one jako stringi składające się z dwóch znaków, w danych wejściowych dostajemy listę krawędzi grafu w postaci: kh-tc # komputer kh jest połączony z komputerem tc qp-kh de-cg ta-ka ... Mamy znaleźć takie zbiory trzech komputerów że każdy jest połączony z każdym. Jest to problem znalezienia kliki w grafie. Problem ten jest NP-trudny, jednak dla klik o rozmiarach 3 nawet rozwiązanie typu brute force nie powinno sprawić większego problemu. ...

Poprzez problemy z zadaniem 21 ten post wrzucam z opóźnieniem, ale zadanie z dnia 22 na szczęście było dużo prostsze niż poprzednie. Najtrudniejszym aspektem było zrozumienie treści zadania poprzez czytanie ze zrozumieniem. Część 1 W pierwszej części zadania mamy wygenerować ciąg liczb pseudolosowych zgodnie z podanym w treści algorytmem. Każda linijka zawiera sekretną liczbę początkową od jednego sprzedawcy, dla każdej z tych liczb mamy zasymulować transformacje 2000 razy i zwrócić sumę otrzymanych liczb. ...

Zadanie z dnia 21 mocno przycisnęło mnie do muru, wrzucam rozwiązanie z opóźnieniem, gdyż zajęło mi ono więcej czasu niż chciałbym przyznać. Zadanie Treść zadania jest dosyć skomplikowana, mamy keypad zawierający cyrfy od 0 do 9 oraz przycisk A do akceptowania danej cyfry. Wygląda to tak: +---+---+---+ | 7 | 8 | 9 | +---+---+---+ | 4 | 5 | 6 | +---+---+---+ | 1 | 2 | 3 | +---+---+---+ | 0 | A | +---+---+ Nie możemy jednak bezpośrednio wpisywać nic na tym keypadzie, musi to wykonać robot, którym sterujemy za pomocą takiego keypada: ...

Zadanie Dzisiaj przyszedł czas na kolejne zadanie ze znajdywaniem ścieżki w dwuwymiarowej macierzy. Format wejścia jest podobny jak w zadaniu 16. Czyli mamy grida ze ścieżkami oznaczonymi jako . a ścianami oznaczonymi jako #. Start i koniec oznaczone są kolejno jako S i E. Naszym celem jest znalezienie najkrótszej ścieżki od początku do końca, z tym że mamy możliwość oszukiwania, gracz raz podczas wyścigu może aktywować oszustwo trwające dwa ruchy. Podczas oszustwa może przechodzić przez ściany, ale na końcu trwania oszustwa powinien skończyć na pustym polu. (Czyli efektywnie jesteśmy w stanie przeskoczyć jedną ścianę). ...

Zadanie Dzisiaj na wejściu otrzymujemy listę stringów które możemy wykorzystać do tworzenia innych większch stringów za pomocą konkatenacji. Dostajemy też listę długich stringów które będziemy próbować zbudować. r, wr, b, g, bwu, rb, gb, br brwrr bggr gbbr rrbgbr ubwu bwurrg brgr bbrgwb Naszym zadaniem jest policzyć ile długich ciągów znaków jesteśmy w stanie stworzyć za pomocą fragmentów z pierwszej linijki. Przykłady: brwrr - br + wr + r bggr - b + g + g + r ubwu - nie da się! Rozwiązanie W faktycznym inpucie naszego zadania stringi budulcowe są sporo dłuższe i jest ich więcej, jedną z fajnych struktur do przechowywania takiego typu danych jest trie, pozwala ono bowiem na weryfikowanie w wydajny sposób czy dany prefix występuje w jakim kolwiek ze słow z dużego słownika. ...

Problem Dzisiaj znajdujemy się na planszy 2d o wielkości 71 na 71, zaczynamy w narożniku o koordynatach (0,0) musimy dojść do pola (70, 70). Na wejściu dostajemy listę koordynatów w takiej formie: 5,4 4,2 4,5 3,0 2,1 6,3 ... Koordynaty te wskazują na których polach znajduje się przeszkoda. Naszym zadaniem jest znaleźć najkrótszą ścieżkę (omijając przeszkody) z punktu startowego do końcowego, ale mamy brać pod uwagę tylko 1024 pierwszych linijek z koordynatami przeszkód. Zakładam że pozostałe przeszkody będą potrzebne do części 2. ...

Zadanie Zadanie z dnia 17 polega na tym żeby uruchomić program na fikcyjnym procesorze opisanym dokładnie w treści zadania. Omówię jedynie najważniejsze aspekty. Nasz procesor operuje na liczbach 3 bitowych, każda operacja składa się z kodu operacji zaraz za nią operandu (para zajmuje razem 6 bitów). Procesor posiada też 3 rejestry: A, B i C, rejestry te mogą trzymać dowolne wartości nie ograniczone przez 3 bity. Program składa się z ciągu 3 bitowych wartości, operator operand, IP jest rejestrem który na początku ma wartość 0, wskazuje on na instrukcję która powinna zostać wykonana następna. Moment w którym próbujemy wykonać instrukcją znajdującą się poza pamięcią jest momentem kiedy nasz program się kończy. ...

Problem Dzisiejsze zadanie polega na znalezieniu ścieżki w labiryncie która będzie miała najniższy score, gdzie score liczony jest w taki sposób że każdy ruch zwiększa go o jeden a każdy skręt o 90 stopni zwiększa go o 1000. Zaczynamy w punkcie S a kończymy w punkcie E. Oto przykładowy labirynt: ############### #.......#....E# #.#.###.#.###.# #.....#.#...#.# #.###.#####.#.# #.#.#.......#.# #.#.#####.###.# #...........#.# ###.#.#####.#.# #...#.....#.#.# #.#.#.###.#.#.# #.....#...#.#.# #.###.#.#.#.#.# #S..#.....#...# ############### Rozwiązanie Jak tylko widzę zadanie ze znajdywaniem najkrótszej ścieżki to od razu myślę o algorytmie Dijkstry. Nasz labirynt możemy rozważać jako graf. Ważne jest to że każdym wierzchołkiem nie mogą być same koordynaty a także kierunek w którym jesteśmy zwróceni, lub bardziej powinienem powiedzieć orientacja, gdyż z punktu widzenia liczenia score nie ma znaczenia w którą stronę skręcamy a jedynie że zmieniamy orientację z pionowej na poziomą lub na odwrót. ...