В одной из аудиторий университета стоит фортепиано, доступное для всех желающих. Митя, будучи выпускником музыкальной школы, каждую неделю играет на нём композиции из своего сборника. Образцы композиций хранятся у него на компьютере в специальном формате.
Аудиофайл формата Мити состоит из команд, которые так или иначе влияют на звучание композиции, в отличие от большинства других форматов, хранящих оцифрованный аналоговый звук. Для записи файла Митя использует две команды — «зажать клавишу» и «отпустить клавишу». Каждая из двух команд занимает {1}, разделённых на следующие фрагменты:
- {2} бит на хранение времени, которое нужно отсчитать с момента прошлой команды, прежде чем выполнится текущая;
- 4 бита на тип команды;
- 4 бита на номер инструмента, которому предназначается команда;
- 8 бит на номер ноты (от 0 до 127);
- 8 бит на силу нажатия (от 0 до 255; не несёт информации, если выполняется команда «отпустить клавишу»).
Такой формат позволяет проигрывать две и более ноты одновременно.
К Мите часто приходит Женя, увлекающийся сжатием данных. Он знает, как хранятся композиции Мити, и хочет предложить ему альтернативный вариант кодирования команд, в котором для кодирования каждого фрагмента команды будет использоваться минимально возможное одинаковое для каждого такого фрагмента целое количество бит, при этом не несущие для данной команды информации фрагменты исключаются из команды. В том числе Женя обратил внимание, что Митя умеет играть только на одном музыкальном инструменте, и подумал, где ещё он может уменьшить количество бит для хранения параметра, но точно известно, что он не стал изменять формат фрагмента для хранения времени между командами.
Также к Мите иногда приходит Настя, которая записывает игру Мити на диктофон. Она всегда включает запись в тот момент, когда Митя начинает играть композицию, и выключает запись ровно в тот момент, когда он заканчивает её играть. Диктофон записывает звук {3}.
На этой неделе ребята решили провести эксперимент. Митя подобрал композицию, в которой в каждый момент времени играется ровно одна нота и все ноты играются без пауз. Женя заранее конвертировал запись Мити в свой вариант формата, а Настя записала эту композицию на диктофон, после чего ребята сравнили размеры получившихся файлов.
Известно, что в композиции есть только ноты длительностью \(1/8\) секунды, \(1/4\) секунды и \(1/2\) секунды. Все ноты игрались непрерывно, и в файле Мити для этой композиции команда «зажать клавишу» для новой ноты выполняется сразу же после команды «отпустить клавишу» для текущей ноты.
{4}
Пример записи ответа:
171717