eolymp
bolt
Try our new interface for solving problems
Məsələlər

Кубичность

Кубичность

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Исследовательский космический спутник в ходе изучения некоторой функциональной зависимости произвел n измерений. Чтобы передать результаты эксперимента на Землю в наиболее сжатом виде, требуется разбить всю область значений аргумента на минимальное количество отрезков с соблюдением следующего условия: на каждом из этих отрезков должен существовать полином не более чем третьей степени, совпадающий с результатами измерений во всех точках, принадлежащих этому отрезку.

Также необходимо, чтобы границы получившихся отрезков являлись точками исходных измерений.

Giriş verilənləri

В первой строке находится количество измерений n (2n100). В следующей строке заданы n пар целых чисел, каждое из которых по модулю не превышает 1000, – результаты проведенных измерений. В каждой такой паре первое число – значение аргумента, а второе – соответствующее значение функции в этой точке. Пары перечислены в порядке возрастания координаты, расстояние между точками измерений не превышает 100. Числа в строке разделены не менее чем одним пробелом.

Çıxış verilənləri

Вывести минимально возможное число отрезков.

Nümunə

Giriş verilənləri #1
10
0 0  1 1  2 2   3 3  4 4   5 4  6 4  7 4  8 4  9 4
Çıxış verilənləri #1
2
Mənbə Новосибирск 2013