Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
Mogę podzielić się tym jak ja zaklepałem checker, podejrzewam że orgowie robili coś podobnego.
Dla wygody zakładamy, że ruchy mapują się na takie wektory:
\ |
.\|
--x--
..|\
..| \
i przeskalowuję je tak, aby środek każdego takiego wektora był w punkcie kratowym.
Narysowane odcinki możemy reprezentować teraz jako (multi)zbiór tych środków, a te możemy sobie wygodnie hashować w następujący sposób:
- hash punktu (x, y) to A^x * B^y mod P (dla zafiksowanych A, B, P),
- hash zbioru to suma hashy jego elementów.
Taki sposób hashowania pozwala wygodnie przesuwać cały zbiór punktów o dowolny wektor.
Teraz chcemy policzyć hashe następujących rzeczy - a) piramidy o boku n; b) tego co narysuje żółwik
a) to po prostu jakaś wzorkologia, ja to liczyłem czymś w stylu szybkiego potęgowania
b) to jest ta ciekawsza część. Główna obserwacja jest taka, że dowolna sekwencja ruchów wygeneruje nam jakiś zbiór punktów + przesunie żółwika o jakiś offset (zależny tylko od tej sekwencji). Dzięki temu możemy sobie szybko radzić z sekwencjami postaci N[...]. Wystarczy policzyć hash i offset tego co jest w środku, a wówczas hash N[...] możemy policzyć korzystając z tego że potrafimy szybko przesuwać zbiory o ten offset.
Dokładniej wychodzi coś w stylu hash(N[S]) = hash(S) * (1 + A^x B^x + A^(2x) B^(2x) + ... + A^((N-1)x) B^((N-1)y)), gdzie (x, y) to offset po wykonaniu S.
Dla wygody zakładamy, że ruchy mapują się na takie wektory:
\ |
.\|
--x--
..|\
..| \
i przeskalowuję je tak, aby środek każdego takiego wektora był w punkcie kratowym.
Narysowane odcinki możemy reprezentować teraz jako (multi)zbiór tych środków, a te możemy sobie wygodnie hashować w następujący sposób:
- hash punktu (x, y) to A^x * B^y mod P (dla zafiksowanych A, B, P),
- hash zbioru to suma hashy jego elementów.
Taki sposób hashowania pozwala wygodnie przesuwać cały zbiór punktów o dowolny wektor.
Teraz chcemy policzyć hashe następujących rzeczy - a) piramidy o boku n; b) tego co narysuje żółwik
a) to po prostu jakaś wzorkologia, ja to liczyłem czymś w stylu szybkiego potęgowania
b) to jest ta ciekawsza część. Główna obserwacja jest taka, że dowolna sekwencja ruchów wygeneruje nam jakiś zbiór punktów + przesunie żółwika o jakiś offset (zależny tylko od tej sekwencji). Dzięki temu możemy sobie szybko radzić z sekwencjami postaci N[...]. Wystarczy policzyć hash i offset tego co jest w środku, a wówczas hash N[...] możemy policzyć korzystając z tego że potrafimy szybko przesuwać zbiory o ten offset.
Dokładniej wychodzi coś w stylu hash(N[S]) = hash(S) * (1 + A^x B^x + A^(2x) B^(2x) + ... + A^((N-1)x) B^((N-1)y)), gdzie (x, y) to offset po wykonaniu S.
Potwierdzam
Potwierdzam
A dlaczego nie ma języka Pascal?
Składam wniosek formalny o usunięcie humanistów.
Potwierdzam
Potwierdzam test
Potwierdzam
Moje ładne rysunki: https://ibb.co/FDzvmXq
(rozwiązanie to co wszyscy)
(rozwiązanie to co wszyscy)
Potwierdzam
Test niezgodny z treścią zadania.
potwierdzam
https://pastebin.com/FJjuw7Ms
Rekurencja próbuje narysować trójkąt z "pełnym" prawym bokiem i ząbkowanymi pozostałymi. Zaczynam na gorze, konczę po prawej.
Trójkąt rozmiaru 2k+1 lub 2k+2 rysuję tak:
-2x (dopisując 2[ przed wejściem w podfunkcję i ] po wyjściu) rekutencyjnie trojkąt rozmiaru k, trojkąty stykaja się (wierzchołkami prawy do gornego), jestem w prawym wierzchołku dolnego trójkąta.
-dorysowuje zygzaczek (linia w lewo, w gorę-prawo i znow w lewo, dodaliśmy dwie krawędzie dolnemu trojkątowi, i dolną gornemu ) - lądują w lewym rogu gornego trojkąta.
-rysuję romb. Kończę w lewym rogu wielkiego, tworzonego wlaśnie trojkąta.
Ale ten trójkąt ma "pełną" dolną krawędź, co się nie splata z warunkiem na rekurnecję. Dorysowuję więc zygzaczek (albo falbankę szerokości 2), co naprawia trojkąt i przesuwa zółwia na właściwa pozycję (prawy rog trojkąta).
Jeśli to trojkąt, który chcaiłem narysować (korzeń rekurencji), rysuję kreskę w lewo i prawo-gorę, by dorysować brakujace boki.
Liczby koduję jak w rozwiązaniu z OIJ, w systemie o podstawie 9.
Edit: obraz wart więcej i te sprawy https://youtu.be/PUEMoPTok70
Moje rozwiązanie jest bardzo podobne do rozwiązania Michała, tylko orientacja inna.
Rekurencja próbuje narysować trójkąt z "pełnym" prawym bokiem i ząbkowanymi pozostałymi. Zaczynam na gorze, konczę po prawej.
Trójkąt rozmiaru 2k+1 lub 2k+2 rysuję tak:
-2x (dopisując 2[ przed wejściem w podfunkcję i ] po wyjściu) rekutencyjnie trojkąt rozmiaru k, trojkąty stykaja się (wierzchołkami prawy do gornego), jestem w prawym wierzchołku dolnego trójkąta.
-dorysowuje zygzaczek (linia w lewo, w gorę-prawo i znow w lewo, dodaliśmy dwie krawędzie dolnemu trojkątowi, i dolną gornemu ) - lądują w lewym rogu gornego trojkąta.
-rysuję romb. Kończę w lewym rogu wielkiego, tworzonego wlaśnie trojkąta.
Ale ten trójkąt ma "pełną" dolną krawędź, co się nie splata z warunkiem na rekurnecję. Dorysowuję więc zygzaczek (albo falbankę szerokości 2), co naprawia trojkąt i przesuwa zółwia na właściwa pozycję (prawy rog trojkąta).
Jeśli to trojkąt, który chcaiłem narysować (korzeń rekurencji), rysuję kreskę w lewo i prawo-gorę, by dorysować brakujace boki.
Liczby koduję jak w rozwiązaniu z OIJ, w systemie o podstawie 9.
Edit: obraz wart więcej i te sprawy https://youtu.be/PUEMoPTok70
Moje rozwiązanie jest bardzo podobne do rozwiązania Michała, tylko orientacja inna.
Potwierdzam.
To celowe, chciałem poszukać na jakich testach mój program najdłużej się wykonuje i tak było mi wygodnie.