В этой задаче вам потребуется иметь дело с реальным алгоритмом, который используется при работе социальной сети ВКонтакте.

Как и в любой другой компании, создающей высоконагруженные сервисы, разработчикам ВКонтакте приходится регулярно иметь дело со статистикой обращений. Важным показателем, отражающим нагруженность ресурса, является среднее число запросов за некоторый промежуток времени в T секунд (например, T = 60 сек = 1 мин или T = 86400 сек = 1 сутки). Например, если это число резко падает, то это признак того, что ресурс испытывает проблемы с доступностью, а если возрастает, то это повод исследовать причины роста количества запросов, и, возможно, увеличить количество ресурсов, поддерживающих работу сервиса.

Однако даже такая естественная задача как подсчёт среднего количества запросов за промежуток времени может оказаться непростой при работе с объёмами данных, характерными для огромной социальной сети. Поэтому в процессе разработки приходится использовать оригинальные технические приёмы, позволяющие решать те или иные задачи приближённо, но при этом более эффективно.

Рассмотрим следующую формальную модель. Имеется сервис, который работает на протяжении n секунд. Нам известно количество запросов к этому ресурсу a_t в каждый момент времени t (1 ≤ t ≤ n). Сформулируем следующий алгоритм подсчёта среднего с экспоненциальным затуханием. Пусть c — некоторое вещественное число, строго больше единицы.

// правильной установкой этой константы можно регулировать 
// промежуток времени, за который будет считаться статистика
double c = некоторая константа; 

// в результате работы алгоритма эта переменная будет 
// содержать среднее количество запросов за последние 
// T секунд к текущему моменту времени
double mean = 0.0; 

for t = 1..n: // каждую секунду делаем следующее:
    // at это количество запросов, поступивших за последнюю секунду;
    mean = (mean + at / T) / c;

Таким образом, переменная mean каждую секунду пересчитывается с использованием количества запросов, поступивших за эту секунду. Проведя некоторые математические выкладки можно доказать, что при правильном подборе константы c значение mean будет не сильно отличаться от реального среднего значения a_x при t - T + 1 ≤ x ≤ t.

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

Однако перед использованием нового теоретического подхода в промышленном программировании, обязательным шагом является практическая проверка его достоверности на имеющихся тестовых наборах данных. Ваша задача — сравнить результаты, полученные в результате работы приближённого алгоритма, с настоящими значениями.

Вам даны n значений a_t, целое число T и вещественное число c. Также вам даны m моментов p_j (1 ≤ j ≤ m), в которые нас интересует среднее значение количества запросов за последние T секунд. Реализуйте два алгоритма. Первый должен считать требуемое значение по определению, т. е. по формуле . Второй алгоритм должен считать среднее значение так, как описано выше. Выведите оба значения и посчитайте относительную ошибку второго алгоритма по формуле , где approx — приближённое значение, полученное вторым алгоритмом, а real — точное значение, полученное первым алгоритмом.