{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBinary code is a mapping of characters of some alphabet to the set of finite length bit sequences. For\nexample, standard ASCII code is a fixed length code, where each character is encoded using 8 bits.\u003c/p\u003e\n\u003cp\u003eVariable length codes are often used to compress texts taking into account the frequencies of occurence\nof different characters. Characters that occur more often get shorter codes, while characters occuring\nless often -- longer ones.\u003c/p\u003e\n\u003cp\u003eTo ensure unique decoding of variable length codes so called prefix codes are usually used. In a prefix\ncode no code sequence is a proper prefix of another sequence. Prefix code can be easily decoded scanning\nthe encoded sequence from left to right, since no code is the prefix of another, one always knows where\nthe code for the current character ends and the new character starts.\u003c/p\u003e\n\u003cp\u003eAmong prefix codes, the optimal code is known, so called Huffman code. It provides the shortest possible\nlength of the text among all prefix codes that separatly encode each character with an integer number of\nbits.\u003c/p\u003e\n\u003cp\u003eHowever, as many other codes, Huffman code does not preserve character order. That is, Huffman codes\nfor lexicographically ordered characters are not necessarily lexicographicaly ordered.\u003c/p\u003e\n\u003cp\u003eIn this problem you are asked to develop a prefix code that would be optimal for the given text among all\norder-preserving prefix codes. Code is called order-preserving if for any two characters the code sequence\nfor the character that goes earlier in the alphabet is lexicographically smaller.\u003c/p\u003e\n\u003cp\u003eSince text itself is not essential for finding the code, only the number of occurences of each character is\nimportant, only this data is given.\u003c/p\u003e\n\n\n\u003cp\u003e\u003cb\u003eInput:\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eThe input consists of several test cases\u003c/p\u003e\n\u003cp\u003eFor each test case, the first line contains n -- the number of characters in the alphabet (2 \u0026lt;\u003d n \u0026lt;\u003d 2000). The next line contains n integer numbers -- the number of occurences of the characters in the text for which\nthe code must be developed (numbers are positive and do not exceed 10\u003csup\u003e9\u003c/sup\u003e). Characters are described in\nthe alphabetical order.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eOutput:\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003eFor each test case, Output n bit sequences, one on a line -- the optimal order-preserving prefix code for the described text.\u003c/p\u003e\n\n\u003cb\u003eSample Input:\u003c/b\u003e\u003cpre\u003e5\n1 8 2 3 1\n\u003c/pre\u003e\n\n\u003cb\u003eSample Output:\u003c/b\u003e\u003cpre\u003e00\n01\n10\n110\n111\n\u003c/pre\u003e\n\n\n\n\n\u003cbr\u003e\n"}}]}