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_06_09 - Termin drugi

termin drugi

Studenci, którzy nie podeszli do zerówki i nie zdali egzaminu ze "Wstępu do algorytmów" w pierwszym terminie muszą zmierzyć się z zadaniem przygotowanym przez profesora Algobita. Wykładowca ma dziś zły humor, ale czy oznacza to, że zadanie będzie trudne? Brzmi ono tak:

Nauczyciel przygotował dla każdej osoby szyfrogram składający się z n liczb naturalnych nie większych niż 109 oraz rosnący ciąg ak składający się z k wyrazów o takiej własności, że każdy następny wyraz jest większy od sumy poprzednich, oraz pewne dwie względnie pierwsze liczby m i n. Następnie wytłumaczył w jaki sposób otrzymał liczby stanowiące szyfrogram:

Dla przykładu posłużymy się ciągiem o długości k = 4: {2, 3, 7, 14}. Następnie dobieramy dwie liczby n i m takie, że n jest względnie pierwsze ze wszystkimi elementami ciągu oraz m jest liczbą większą od sumy wszystkich liczb w ciągu i tworzymy nowy ciąg bk zgodnie z zasadą:

bi = ai * n mod m, gdzie 1 ≤ ik

Np. dla n = 11 oraz m  = 30 wyrazy nowego ciągu będą miały następujące wartości:

{22, 3, 17, 4}.

Aby zaszyfrować wiadomość przedstawiamy ją w sposób binarny i dzielimy na segmenty o długości k. W naszym przykładzie są 4 segmenty o długości 4 bitów każdy:

1001 1101 1110 0101

Teraz, każdy bit mnożymy przez odpowiadający wyraz ciągu i otrzymane elementy segmentu sumujemy:

dla 1001 mamy 22 + 4 = 26

dla 1101 mamy 22 + 3 + 4 = 29

dla 1110 mamy 22 + 3 + 17 = 42

dla 0101 mamy 3 + 4 = 7

Szyfrogramem jest ciąg: {26, 29, 42, 7}.

Zadaniem studentów i twoim jest odszyfrowanie tajnej wiadomości.

Wejście

W pierwszym wierszu jedna liczba określająca ilość zestawów danych.

Dla każdego zestawu mamy:

W pierwszym wierszu trzy liczby całkowite n, m k, gdzie n ≤ 1000, m jest nie większe niż podwojona suma wszystkich elementów ciągu oraz takie, że 0 < k ≤ 20, w następnym wierszu k wyrazów ciągu ak (maksymalny element ciągu jest nie większy niż 109). Następnie jedna liczba d określająca ilość elementów szyfrogramu 0 < d < 105. W ostatnim wierszu d liczb będących szyfrogramem. 

Wyjście

Dla każdego zestawu oryginalna wiadomość przedstawiona w postaci binarnej. Długość wiadomości jest nie większa niż 4*105.

Przykład

Wejście:
1
11 30 4
2 3 7 14
4
26 29 42 7

Wyjście:
1001110111100101

Dodane przez:Marcin Kasprowicz
Data dodania:2013-05-01
Limit czasu wykonania programu:1s-2s
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.