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

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

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В результате измерений была получена зависимость некоторого параметра от времени. Значение параметра измерялось каждую единицу времени, при измерении выполнялось преобразование аналогового значения в цифровую форму и дробная часть результата измерений отбрасывалась. Например, если в момент времени i было получено цифровое значение yi для параметра, это означает, что реальное значение fi измеряемого параметра было yi  fi < yi + 1.
Необходимо описать зависимость параметра от времени с помощью кусочно-линейной аппроксимации, разбив интервал времени измерений на наименьшее число участков. Границы участков должны быть целыми числами. В пределах каждого участка для аппроксимирующей прямой F(t) = at + b должно выполняться условие yi  F(i) < yi + 1.
В первой строке ввода содержится одно целое число N (2  N  100) – число измерений. Во второй строке содержится N целых чисел, разделенных пробелами, в диапазоне от 0 до 255 – результаты измерений.
В первой строке вывести одно число K – минимальное число участков. Далее следует K строк, в каждой строке должно быть по четыре числа – начало и конец участка si, ti (целые, ti-1 = si < ti, tK = N, s1 = 1), и коэффициенты i-й прямой ai, bi с точностью 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