|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||13||11||10||83.333%|
Binary encoding represents integer numbers from 0 to 2n − 1 inclusive with n bits, each bit is either 0 or 1. In binary encoding most significant digit is written first. Two binary codes are compared from left to right, from the most significant digit to the least significant one. Binary codes are uniquely assigned to numbers from 0 to 2n − 1 is a such a way, that corresponding binary codes for numbers in ascending order are themselves in ascending order. For example, binary encoding for numbers from 0 to 7 is:
Truncated binary encoding generalizes binary encoding to represent integer numbers from 0 to m − 1 inclusive, where m may or may not be equal to 2n for some integer number n. Unlike binary encoding, truncated binary encoding uses different number of bits to represent different numbers. If n is the smallest integer number such that m ≤ 2n, then truncated binary encoding represents each number from 0 to m −1 with n or with n−1 bits. Some numbers are encoded with n−1 bits only if m < 2n; when m = 2n truncated binary encoding is the same as binary encoding. Truncated binary codes are compared from left to right, just like binary codes.
Truncated binary encoding also satisfies the following rules:
For example, truncated binary encoding for numbers from 0 to 5 is:
Your task is to encode numbers from 0 to m − 1 with truncated binary encoding.
The input file contains integer number m (2 ≤ m ≤ 10000).
Write to the output file m lines. These m lines shall contain truncated binary encoding of numbers from 0 to m − 1 in ascending order.
00 01 100 101 110 111