Упаковка чисел
(Время: 1 сек. Память: 16 Мб Сложность: 65%)
При передаче данных по сети важно их эффективно кодировать, чтобы лучше использовать пропускную способность канала. Мы опишем процедуру декодирования чисел при одном эффективном способе их кодирования. Этот способ использует переменную длину кодов, для обеспечения единственности декодирования ни один код числа не является префиксом кода другого числа. Вы же должны реализовать процедуру оптимального кодирования.
Метод применим для кодирования целых чисел от −263 до 263−1 (тип long в Java, int64 в Дельфи, __int64 в C++). Упакованное число занимает от 1 до 9 байт, в зависимости от своего значения.
Декодирование происходит следующим образом. Сначала рассматривается первый байт числа. Просматривая его биты от старшего к младшему, найдем первый ноль. Пусть q – количество просмотренных при этом единиц (если первый бит равен 0xff, то q=8). Число q означает, сколько следующих байтов относятся к декодируемому числу. Если q=8, то эти байты – стандартная восьмибайтная запись числа, причем старшие байты идут сначала.
В противном случае выполним следующее. Если q+2-й бит первого байта равен нулю (биты нумеруются с единицы, сначала идет старший бит, если q=7, то рассматривается старший бит второго байта) то старшие единицы первого байта заменяются на нули, и число дополняется нулевыми байтами до размера 8 байтов. Иначе (если соответствующий бит равен единице) q+1-й бит (который всегда равен нулю) заменяется на единицу, число же дополняется слева байтами 0xff до восьми байтов. В обоих случаях получается стандартная восьмибайтная запись числа, причем старшие байты идут сначала.
Вам заданы несколько целых чисел, закодируйте каждое из них таким образом, чтобы длина закодированного числа была минимальной возможной, и оно декодировалось в исходное число.
Входные данные
Первая строка входного файла INPUT.TXT содержит n – количество тестовых примеров (1 ≤ n ≤ 104). Следующие n строк содержат по одному числу в интервале между -263 и 263-1 включительно.
Выходные данные
В выходной файл OUTPUT.TXT выведите n строк, каждая строка должна содержать закодированную версию соответствующего числа, записанную как последовательность шестнадцатеричных цифр, старшие байты должны идти сначала. Используйте строчные буквы английского алфавита.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 9
0
1
2
3
100
500
1000000
-1
-100 | 00
01
02
03
8064
81f4
cf4240
7f
bf9c |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
