← 返回题目列表

Codeforces · 523/B

B. 平均请求

中文机器翻译题面 查看原题

在这个问题中,您将必须处理 VK 社交网络中使用的真实算法。

与任何其他创建高负载网站的公司一样,VK 开发人员必须定期处理请求统计数据。反映网站负载的一个重要指标是一定时间段T秒内的平均请求数(例如,T=60秒=1分钟,T=86400秒=1天)。例如,如果该值急剧下降,则表明该站点存在访问问题。如果该值增长,则可能需要分析增长的原因,并在确实需要时向网站添加更多服务器。

然而,当您处理庞大的社交网络的数据量时,即使是计算一段时间内的平均查询数这样的自然问题也可能是一个挑战。这就是为什么开发人员必须使用原始技术来近似解决问题,但同时更有效。

让我们考虑以下正式模型。我们有一个工作时间为 n 秒的服务。我们知道在每个时刻 t (1 ≤ t ≤ n) 对此资源的查询数量。让我们制定以下计算指数衰减均值的算法。令 c 为某个实数,严格大于 1。

因此,每秒都会使用该秒出现的查询数重新计算平均变量。我们可以通过一些数学计算证明,正确选择常数c的值将使在t - T + 1 ≤ x ≤ t时mean的值与真实平均值ax相差不大。

这种方法的优点是它只使用当前时刻的请求数量,不需要存储大时间范围内的请求历史记录。此外,它考虑最近值的权重大于旧值的权重,这有助于更快地对值的急剧变化做出反应。

然而,在工业编程中使用新的理论方法之前,有一个强制性的步骤要做,即在给定的测试数据集上实际测试其可信度。您的任务是将近似算法工作所获得的数据与真实数据进行比较。

给定 n 个值 at、整数 T 和实数 c。此外,还给出了 m 个时刻 pj (1 ≤ j ≤ m),其中我们感兴趣的是最后 T 秒内查询数量的平均值。实现两个算法。第一个应该根据定义计算所需的值,即通过公式 $$\frac{a_{p_j-T+1} + a_{p_j-T+2} + \ldots + a_{p_j}}{T}$$。第二个算法应如上所述计算平均值。打印这两个值并通过公式 $$\frac{|approx-real|}{real}$$ 计算第二个算法的相对误差,其中 approx 是第二个算法获得的近似值,real 是第一个算法获得的精确值。

输入

第一行包含整数n (1 ≤ n ≤ 2·105)、整数T (1 ≤ T ≤ n) 和实数c (1 < c ≤ 100) — 资源应该工作的时间范围、我们需要平均请求数的时间范围的长度以及近似算法的工作系数c。数字 c 精确到小数点后六位数字。

下一行包含 n 个整数 at (1 ≤ at ≤ 106) — 每个时刻对服务的查询数。

下一行包含整数 m (1 ≤ m ≤ n) — 我们对最后 T 秒的平均查询数感兴趣的时刻数。

下一行包含 m 个整数 pj (T ≤ pj ≤ n),代表我们需要统计的另一个时刻。 pj 时刻严格增加。

输出

打印 m 行。第 j 行必须包含三个数字实数、近似值和误差,其中:

- $$real = \frac{a_{p_j-T+1} + a_{p_j-T+2} +... + a_{p_j}}{T}$$ 是最后 T 秒的真实平均查询数;
- approx 由给定算法计算得出,等于时间 t = pj 时刻的平均值(即在执行循环的第 pj 次迭代之后);
- $$error = \frac{|approx - real|}{real}$$ 是近似算法的相对误差。

您打印的数字将与正确数字进行比较,相对或绝对误差为 10 - 4。建议打印小数点后至少 5 位数字。

示例

输入 #1

1 1 2.000000
1
1
1

输出 #1

1.000000 0.500000 0.500000

输入 #2

11 4 1.250000
9 11 7 5 15 6 6 6 6 6 6
8
4 5 6 7 8 9 10 11

输出 #2

8.000000 4.449600 0.443800
9.500000 6.559680 0.309507
8.250000 6.447744 0.218455
8.000000 6.358195 0.205226
8.250000 6.286556 0.237993
6.000000 6.229245 0.038207
6.000000 6.183396 0.030566
6.000000 6.146717 0.024453

输入 #3

13 4 1.250000
3 3 3 3 3 20 3 3 3 3 3 3 3
10
4 5 6 7 8 9 10 11 12 13

输出 #3

3.000000 1.771200 0.409600
3.000000 2.016960 0.327680
7.250000 5.613568 0.225715
7.250000 5.090854 0.297813
7.250000 4.672684 0.355492
7.250000 4.338147 0.401635
3.000000 4.070517 0.356839
3.000000 3.856414 0.285471
3.000000 3.685131 0.228377
3.000000 3.548105 0.182702