Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
?

AL_20_10 - Rejestr

Do budowy pseudolosowych generatorów strumieniowych często wykorzystuje się rejestry. Generatory takie mają szerokie zastosowanie w kryptografii. Im bardziej wyrafinowany system generujący bity, tym trudniej jest go złamać. Nasz generator jest oparty na rejestrze przesuwnym ze sprzężeniem zwrotnym. Działanie jego jest bardzo proste. Ustalamy według pewnego schematu (o tym w dalszej części zadania) komórki rejestru, z których sumowane są bity modulo 2. Wynik jest wygenerowanym bitem, który także jest wstawiany na koniec rejestru, natomiast pozostałe są przesuwane o jeden bit w prawo.

Aby uzyskać maksymalny cykl takiego generatora należy oprzeć go o wielomian pierwotny modulo 2 (autor zadania zadbał o to, żeby tylko takie pojawiły się na wejściu). Wielomian, który został przedstawiony w zadaniu ma postać:

x8+x4+x3+x2+1

Rejestr ma zawsze długość stopnia wielomianu. W tym przypadku jest to 8 bitów. Zaczepy bitów, które będziemy dodawać modulo 2 ustawiamy odpowiednio na 8, 4, 3 oraz 2 miejscu (wyraz wolny nie bierze udziału).

Rysunek przedstawia generator dla wielomianu podanego w przykładzie:

generator

Zadanie polega na odszyfrowaniu wiadomości zaszyfrowanej tym generatorem.

Szyfrowanie

Najpierw ustawiamy ziarno - wartości początkowe bitów zawartych w poszczególnych komórkach rejestru. Następnie uruchamiamy generator pewną ilość razy. Następnie generujemy partie po osiem bitów i xorujemy je z kodem ASCII danej litery. W ten sposób powstaje szyfrogram w postaci sekwencji bitów - jedna litera = 8 bitów. Twoje zadanie polega na odszyfrowaniu wiadomości i przedstawieniu jej w postaci znakowej.

Wejście

W pierwszym wierszu jedna liczba n określająca stopień wielomianu pierwotnego (n < 10000).

W drugim wierszu n+1 współczynników tego wielomianu począwszy od tego, który stoi przy najwyższej potędze (współczynniki należą do zbioru {0, 1}.

Następnie ustawienie ziarna - n bitów rejestru.

W czwartym wierszu jedna liczba u określająca po ilu uruchomieniach generatora, bity będą brane pod uwagę.

W ostatnim wierszu szyfrogram o długości 8⋅s (1 ≤ s ≤ 500000). 

Dodatkowo n⋅s < 108 oraz n⋅u < 108

Wyjście

Oryginalna wiadomość.

Przykład

Wejście:
8
1 0 0 0 1 1 1 0 1
1 1 1 0 0 1 0 1 
2
0101001000010101100000101011011011010101

Wyjście:
haker

Dodane przez:Marcin Kasprowicz
Data dodania:2014-12-17
Limit czasu wykonania programu:1s-3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.