| History of OI -> IX OI 2001/2002 |  |
|
IX Olimpiada Informatyczna 2001/2002
|
|
Task: szy
|
Author: Szyfr
|
Cipher
| III stage contest |
We are given a sequence of positive integers ai (for i=1,2,...,n). This sequence is used to encrypt n-bit messages. If we have a message consisting of consecutive bits (t1,...,tn) (ti is either 0 or 1), then its encryption it the number:
S=t1a1+t2a2+...+tnan
Task
You are given encrypted messages and sequences of numbers (ai), that have been used to encrypt the messages. Your task is to decrypt the encrypted messages and to save them in particular files. You are not expected to present any program. It is sufficient that you write the decrypted messages.Input
You are given several sets of data at your disposal. Each set is written in a separate file: szyk.in, where k is the number of the set. In the first line of each file there is one integer n, 5<=n<=40. In the successive n lines there is a sequence of numbers (ai) written: in the line of number i+1 there is one positive integer ai. The sum of the numbers ai does not exceed 2 000 000 000. In the line of number n+2 there is one integer S - the encrypted message, 0<=S<=a1+a2+...+an.Output
For each set of data szy*.in you should create a file szy*.out containing the decrypted message. In the first line of this file you should write the successive numbers ti, without any spaces between them. The test data were chosen so that the encrypted messages are unambiguously determined.Example
For the following input file 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 667509506the correct answer is in the following output file szy.out:
110001000101101100010101
Print friendly version