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