Polish version    English version  
  O olimpiadzie -> Zadania -> IX OI 2001/2002


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
IX Olimpiada Informatyczna 2001/2002

Zadanie: szy
Autor: Wojciech Guzicki
Szyfr

Zawody III stopnia, dzień drugi  

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=t1a1+t2a2+...+tnan

Zadanie

Masz dane zaszyfrowane wiadomości oraz ciągi liczb (ai), których użyto do ich zaszyfrowania. Twoje zadanie polega na odkodowaniu zaszyfrowanych wiadomości i zapamiętaniu ich w określonych plikach. Nie musisz dostarczać żadnego programu. Wystarczy, że zapiszesz odszyfrowane wiadomości.

Wejście

Dysponujesz kilkoma zestawami danych. Każdy zestaw jest zapisany w osobnym pliku: szyk.in, gdzie k jest numerem zestawu. W pierwszym wierszu każdego z tych plików 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 000 000 000. W n+2-im wierszu zapisana jest jedna liczba całkowita S - zaszyfrowana wiadomość, 0<=S<=a1+a2+...+an.

Wyjście

Dla każdego zestawu danych szy*.in, powinieneś utworzyć plik szy*.out zawierający odszyfrowaną wiadomość. W pierwszym wierszu tego pliku 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.

Przykład

Dla pliku wejściowego szy.in:

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 plik wyjściowy szy.out:

110001000101101100010101



Wersja do druku