Для хранения длинных последовательных целых чисел разрабатывается новый формат хранения целых чисел IIII-4. Число записывается как 4 бит префикса, за которым следуют от 0 до 4 дополнительных 4-битовых групп. Декодирование выполняется следующим образом. В начале нужно прочитать префикс. За тем нужно взять из фиксированной таблицы количество дополнительных групп после него и какое смещение нужно добавить к числу полученному после декодирования этих дополнительных групп. Вам поручено разработать таблицу для кодирования целых чисел в заданном диапазоне, которая позволяет наиболее компактно закодировать некоторую последовательность.
В первой строке заданы целые границы диапазона $$$X$$$ и $$$Y$$$, $$$-10^9\le X \le Y \le 10^9$$$, $$$Y-X+1\le 10^6$$$. Обе границы включаются в диапазон. Во второй строке задано число $$$N$$$, $$$1\le N \le 10^5$$$ элементов последовательности. В третье строке заданы $$$N$$$ целых чисел последовательности, которые лежат в указанном диапазоне.
Выведите 16 строк, в которых записаны элементы таблицы. В каждое строке должны находится два числа $$$L_i$$$, $$$O_i$$$, где $$$0\le L_i \le 4$$$ — количество дополнительных 4-битных групп, а $$$-2\cdot 10^9 \le O_i \le 2 \cdot 10^9$$$ — смещение, которое нужно добавить после декодирования дополнительных групп. Для всех чисел от $$$X$$$ до $$$Y$$$ включительно должна быть возможность их закодировать ровно одним способом. Разрешается кодировать числа вне диапазона любым числом способов. Заданная последовательность целых чисел должна быть закодированна в минимальное число битов. Если таких оптимальных таблиц несколько, разрешается вывести любую из них.
0 15 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15
-128 127 4 1 0 -1 0
2 -261 0 -5 0 -4 0 -3 0 -2 0 -1 0 0 0 1 1 2 1 18 1 34 1 50 1 66 1 82 1 98 1 114
| 2020-2021 ICPC, Moscow Subregional |
|---|
| Закончено |
