Сегодня, придя на пару по дискретной математике, профессор Р. решил рассказать студентам первого курса о генерации QR-кодов.

QR-код – это монохромная картинка, на которой некоторые устройства (например смартфон со специальным приложением) распознают текст. Этим текстом может быть не только простая фраза, но и, хоть это и не входит в официальную спецификацию, ссылка, номер телефона или визитная карточка. Такие коды чаще всего используют, чтобы закодировать ссылку и распечатать её на плакате или визитке.

QR-код поддерживает несколько способов кодирования данных, в зависимости от того, какие символы используются: цифровое, буквенно-цифровое, кандзи (китайско-японские иероглифы) и побайтовое кодирование. Так как студенты учатся на первом курсе, профессор Р. решил затронуть только цифровое кодирование. Цифровое кодирование подразумевает использование только цифр от 0 до 9. Сначала требуется создать пустую последовательность бит, которая дальше будет заполняться.

Этот тип кодирования требует $$$10$$$ бит на $$$3$$$ символа. Вся последовательность символов разбивается на группы по $$$3$$$ цифры, и каждая группа (трёхзначное число) переводится в 10-битное двоичное число и добавляется к последовательности бит. Если общее количество символов не кратно 3, то если в конце остаётся 2 символа, полученное двузначное число кодируется 7 битами, а если 1 символ, то 4 битами.

Например, есть строка «12345678», которую надо закодировать. Мы разбиваем её на числа: $$$123, 456$$$ и $$$78$$$, затем переводим каждое из них в двоичный вид: $$$0001111011, 0111001000$$$ и $$$1001110$$$, и объединяем это в один поток: $$$000111101101110010001001110$$$.

Профессор Р. дал студентам следующую задачу: по заданной строке, состоящей из цифр, построить её двоичное представление по заданному алгоритму. Попробуйте и вы решить эту задачу.