[SMWP_114] Sinusoidalne Szyfratory

0 Flares Twitter 0 Facebook 0 0 Flares ×

Link do zadania:
http://www.spoj.com/SMWP/problems/SMWP_114/

Opis problemu:
Problem przedstawiony w zadaniu nie jest skomplikowany. Naszym zadaniem jest jedynie zaszyfrować tekst składający się z wielkich liter metodą szyfru płotkowego.

Rozwiązanie:
Rozwiązanie tego zadania nie wymaga znajomości żadnych algorytmów. Jedyną trudnością jest optymalne przechodzenie po tablicy słowa. Mianowicie musimy zauważyć, że przeskok dla n-tego poziomu zagłębienia tj. n liczone od wierzchołka płotka rozpoczyna się od n-tej pozycji litery słowa (liczone od 1). Ponadto dla każdego pierwszego poziomu n, przesunięcie, nazwijmy początkowe po tablicy słowa wyraża się wzorem k*2-2, gdzie k jest liczbą poziomów (inaczej wysokością płotka). Następnie wraz ze zniżaniem się do głębszych poziomów tj większych n, nasze przesunięcie początkowe maleje o 2 pozycje oraz tworzy się przesunięcie końcowe zwiększające się o 2 na każdy wzrastający poziom n. Ponadto musimy również pamiętać o krotności parzystości przesunięcia. Dla przesunięcia nieparzystego na danym stopniu korzystamy z przesunięcia początkowego, natomiast dla przesunięcia parzystego musimy skorzystać z przesunięcia rosnącego tj końcowego, które otrzymuje podczas obiegu słowa na n=k poziomie wartość przesunięcia początkowego. W celach optymalizacyjnych zaleca się także osobne rozpatrzenie przypadku kiedy wysokość płotka jest równa 1, wówczas wypisujemy wyraz z wejścia w niezmienionej postaci.

Print Friendly

Dodaj komentarz

Wymagane pola są oznaczone *.