eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Дискретное преобразование Фурье

Дискретное преобразование Фурье

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

В этой задаче вам требуется провести дискретное преобразование Фурье для многочлена . Напомним, дискретное преобразование Фурье - это вектор y = (y_0, y_1, ..., y_{n-1}), коэффициенты которого вычисляются по формуле:

.

Входные данные

В первой строке записано единственное целое число n (1 n 1000). Во второй строке записано ровно n целых чисел - коэффициенты a_k (-1000 a_k ≤ 1000) в порядке от a_0 до a_{n-1}.

Выходные данные

Ввести ровно n строк. k-ая строка должна содержать ровно два числа real(y_k) и imag(y_k), разделенные пробелом и выведенные с абсолютной или относительной погрешностью, не превышающей 10^{-6}, где real() обозначает действительную часть, а imag() - мнимую.

Пример

Входные данные #1
2
1 2
Выходные данные #1
3.0000000000 0.0000000000
-1.0000000000 0.0000000000
Входные данные #2
4
1 2 3 4
Выходные данные #2
10.0000000000 0.0000000000
-2.0000000000 -2.0000000000
-2.0000000000 0.0000000000
-2.0000000000 2.0000000000
Автор Евгений Соболев
Источник Летняя школа Севастополь 2013, Волна 1, День 5