printЗадачи командного чемпионата

printF. Аппроксимация

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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
loading