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

В результате измерений была получена зависимость некоторого параметра от времени. Значение
параметра измерялось каждую единицу времени, при измерении выполнялось преобразование аналогового
значения в цифровую форму и дробная часть результата измерений отбрасывалась. Например, если
в момент времени i было получено цифровое значение yi для параметра, это означает, что реальное
значение fi измеряемого параметра было yi ≤ fi < yi + 1.
Необходимо описать зависимость параметра от времени с помощью кусочно-линейной аппроксимации,
разбив интервал времени измерений на наименьшее число участков. Границы участков должны быть целыми числами.
В пределах каждого участка для аппроксимирующей прямой F(t) = a⋅t + 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.
Пример вывода
3
1 3 2.000000 -1.000000
3 4 -3.000000 14.000000
4 5 1.000000 -2.000000