ACM 2008 - Автокорреляция

Задача D. Автокорреляция ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Входной файл:	input.txt		Ограничение времени:	1 сек
Выходной файл:	output.txt		Ограничение памяти:	512 Мб

Условие

Пусть задан временной ряд Yn1 = {y_t}nt = 1. Требуется написать программу, вычисляющую значения коэффициентов автокорреляции Пирсона r_l = corr(Yn − l1, Ynl), l = 1,m.

Формат входного файла

Первая строка входных данных содержит целые числа n и m — длину ряда и максимальное значение задержки. Вторая строка входного файла содержит n вещественных чисел — временной ряд.

Формат выходного файла

Выходной файл должен содержать m вещественных чисел — значения коэффициента автокорреляции с точностью не менее трёх знаков после запятой.

Ограничения

2 ⩽ m < n ⩽ 10³

Примеры тестов

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`10 2 1 1 2 2 1 1 2 2 1 1`	`0.1 -1`