Dany jest ciąg dodatnich liczb całkowitych ai (dla i=1, 2, ..., n). Ciąg ten jest używany do szyfrowania n-bitowych wiadomości. Jeśli mamy wiadomość, której kolejne bity tworzą ciąg (t1, ..., tn) (ti ze zbioru {0, 1}), to po zaszyfrowaniu ma ona postać liczby:
S=t1*a1+t2*a2+...+tn*an
Masz dane zaszyfrowane wiadomości oraz ciągi liczb (ai), których użyto do ich zaszyfrowania. Twój program ma odkodować zaszyfrowane wiadomości.
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n, 5 <= n <= 40. W kolejnych n wierszach zapisany jest ciąg liczb (ai): w i+1-ym wierszu zapisana jest jedna dodatnia liczba całkowita ai. Suma liczb ai nie przekracza 2*109. W n+2-im wierszu zapisana jest jedna liczba całkowita S - zaszyfrowana wiadomość, 0 <= S <= a1+a2+...+an.
W pierwszym i jedynym wierszu wyjścia należy zapisać kolejne liczby ti, bez żadnych odstępów między nimi. Dane testowe zostały dobrane tak, że zaszyfrowane wiadomości są określone jednoznacznie.
Dla danych wejściowych:
24 19226985 123697 67356296 19721773 1113273 69335448 23680077 9029881 85168664 93676782 5253843 77616588 78572630 13375812 17199980 101508862 59248276 3505733 35790095 62028546 85726819 56462819 103373994 91757169 667509506
poprawną odpowiedzią jest:
110001000101101100010101
[Zgłoś rozwiązanie] [Moje zgłoszenia]