Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
823. Аппроксимация
Олимпиадные задачи на русском языке| 15/03/2008 | Южно-Уральский открытый командный чемпионат по программированию (F) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В результате измерений была получена зависимость некоторого параметра от времени. Значение
параметра измерялось каждую единицу времени, при измерении выполнялось преобразование аналогового
значения в цифровую форму и дробная часть результата измерений отбрасывалась. Например, если
в момент времени `i` было получено цифровое значение `y_i` для параметра, это означает, что реальное
значение `f_i` измеряемого параметра было `y_i\ ≤\ f_i\ <\ y_i\ +\ 1`.
Необходимо описать зависимость параметра от времени с помощью кусочно-линейной аппроксимации,
разбив интервал времени измерений на наименьшее число участков. Границы участков должны быть целыми числами.
В пределах каждого участка для аппроксимирующей прямой `F(t)\ =\ a*t\ +\ b` должно выполняться условие `y_i\ ≤\ F(i)\ <\ y_i\ +\ 1`.
В первой строке ввода содержится одно целое число `N` (`2\ ≤\ N\ ≤\ 100`) – число измерений. Во второй строке содержится
`N` целых чисел, разделенных пробелами, в диапазоне от 0 до 255 – результаты измерений.
В первой строке вывести одно число `K` – минимальное число участков. Далее следует `K` строк,
в каждой строке должно быть по четыре числа – начало и конец участка `s_i`, `t_i`
(целые, `t_{i-1}\ =\ s_i\ <\ t_i`, `t_K\ =\ N`, `s_1\ =\ 1`), и коэффициенты `i`-й прямой `a_i`, `b_i` с точностью `10^{-6}`.
Пример ввода
5 1 3 5 2 3
Пример вывода
3 1 3 2.000000 -1.000000 3 4 -3.000000 14.000000 4 5 1.000000 -2.000000
