| Автор: | И. Лудов | Ограничение времени: | 2 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
| Выходной файл: | output.txt |
Для еще большего удешевления производства своих телефонов небезызвестная фирма приняла интересное инженерное решение. Теперь их начинка не будет содержать средств для непосредственного воспроизведения оцифрованной звуковой волны. Вместо этого все звуки будут генерироваться устройством наподобие аддитивного синтезатора. Все что оно умеет — это выдавать комбинацию нескольких квадратных волн с разными амплитудами, которые оно получает на вход. Оказывается, закодированные таким образом данные еще и могут занимать меньший объем! Для успешного воплощения этой передовой технологии теперь только требуется написать программу, которая будет любой звук приводить к такому виду. К сожалению, при этом неизбежны потери информации, но нужно постараться их минимизировать.
Будем считать, что звук нарезан на фреймы, каждый из которых содержит количество отсчетов, равное P-й степени двойки. Гармоника с номером i представляет собой квадратную волну и строго задается следующей формулой: Hi(j) = − 1⌊ j / 2i⌋ + 1. Нужно для одного заданного фрейма сгенерировать его представление в виде b0 * H0(j) + … + bP * HP(j), причем так, чтобы его среднеквадратичное отклонение (рассчитанное как сумма квадратов разностей исходного и приближенного отсчета по всем j) от исходного звука было минимально.
Поскольку синтезатор понимает только целые числа, ему на вход должны подаваться целые амплитуды. Однако есть возможность передать еще один дополнительный параметр — масштабный коэффециент S, на который все амплитуды будут автоматически разделены. Поэтому нужно представить их как рациональные числа, в качестве S передать их общий знаменатель, а в качестве последовательности bi — соответствующие числители.
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|