시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 9 | 3 | 1 | 16.667% |
Вадим --- большой фанат кусочно-линейных функций. Они имеют свои ограничения, и не любую функцию можно представить как кусочно-линейную. Вадим вам с радостью расскажет, что это такое.
Функция называется кусочно-линейной, если её график можно представить ломаной из $n$ вершин. А именно, она задаётся $n$ парами чисел $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$, которые являются координатами вершин ломаной. Обязательно должно выполняться условие $$x_1 < x_2 < x_3 < \ldots < x_n.$$
Этот набор точек задаёт функцию от одного аргумента, значение которой в $x_i$ равно $y_i$, а на промежутках между этими точками она линейная. Область определения такой функции --- это отрезок $[x_1, x_n]$.
Валя придумал свой класс функций с одной переменной, которые он назвал модульными. Модульная функция состоит из $n$ слагаемых, каждое из которых имеет один из двух видов: $|a_i \cdot x + b_i|$ или $-|a_i \cdot x + b_i|$. Здесь $x$ --- переменная, а $a_i$ и $b_i$ --- параметры функции, а $| \ldots |$ обозначает взятие по модулю. Таким образом, модульная функция с $n$ слагаемыми имеет вид $$\pm|a_1 x + b_1| \pm |a_2 x + b_2| \pm \ldots \pm |a_n x + b_n|.$$
Вадим захотел проверить, не хуже ли модульные функции его любимых кусочно-линейных. Он принёс кусочно-линейную функцию с $n$ вершинами. Постарайтесь теперь найти модульную функцию с ровно $n$ слагаемыми, которая будет тождественна равна данной кусочно-линейной на отрезке $[x_1, x_n]$.
В первой строке дано целое число $n$ --- количество вершин ломаной $(2 \le n \le 10^5)$.
Далее идёт $n$ строк, в каждой из которых через пробел даны два целых числа $x_i$, $y_i$ --- координаты очередной вершины ($-10^5 \le x_i, y_i \le 10^5$).
Гарантируется, что координаты $x_i$ идут строго по возрастанию, то есть $$x_1 < x_2 < x_3 < \ldots < x_n.$$
Выведите в единственной строке модульную функцию из ровно $n$ слагаемых, тождественно равную данной кусочно-линейно функции на отрезке $[x_1, x_n]$. Придерживайтесь формата, показанного в примерах.
Функция должна состоять из $n$ слагаемых $|a_i x + b_i|$, разделённых знаками +
и -
(коды 43 и 45). Разрешается перед первым слагаемым поставить ведущий минус. Каждое слагаемое должно быть взято по модулю двумя символами |
(код 124). Внутри слагаемого должен быть знак +
(или -
, если $b_i$ отрицательно). Левый операнд состоит из вещественного числа $a_i$ и переменной $x$ (код 120); знак умножения между ними не нужно писать, он подразумевается. Опускать $a_i$ или $b_i$ нельзя, даже если $a_i = 1$ или $b_i = 0$; нельзя также опускать левый операнд, если $a_i = 0$.
Таких слагаемых должно быть ровно $n$. Разрешено использовать слагаемые, тождественно равные нулю. Они могут быть записаны как |0x+0|
.
Размер выходного файла должен быть не больше $8$ МБ. Ответ считается правильным, если в любой точке отрезка $[x_1, x_n]$ значение вашей модульной функции отличается от значения данной кусочно-линейной не более, чем на $0.01$.
2 1 0 2 1
-|0x-1|+|1x+0|
2 0 1 1 2
|1x-0|+|0x+1|
3 -1 1 0 -1 1 0
|-0.5x+1|-|0x-2|+|-1.5x-0|
Иллюстрация к третьему примеру: