{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003e在这个问题中,你将需要处理 VK 社交网络中使用的真实算法。\u003c/span\u003e\u003c/p\u003e\u003cp\u003e和其他创建高负载网站的公司一样,VK 的开发人员需要定期处理请求统计。反映网站负载的重要指标是在 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e 秒内的请求平均次数(例如,\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e \u003d 60\u0026nbsp;\u003ci\u003eseconds\u003c/i\u003e \u003d 1\u0026nbsp;\u003ci\u003emin\u003c/i\u003e\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e \u003d 86400\u0026nbsp;\u003ci\u003eseconds\u003c/i\u003e \u003d 1\u0026nbsp;\u003ci\u003eday\u003c/i\u003e\u003c/span\u003e)。例如,如果这个值急剧下降,那说明网站存在访问问题。如果这个值增长,可能需要分析增长的原因,并在确实需要时向网站添加更多服务器。\u003c/p\u003e\u003cp\u003e然而,即使是计算某段时间内查询平均次数这样一个自然的问题,在处理庞大社交网络的数据量时也可能是一个挑战。这就是为什么开发人员不得不使用原始技术来近似解决问题,但同时更有效地解决问题。\u003c/p\u003e\u003cp\u003e让我们考虑以下形式化模型。我们有一个在 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e 秒内运行的服务。我们知道在每个时间点 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003et\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e)的这个资源的查询次数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e。让我们制定以下算法 \u003cspan class\u003d\"tex-font-style-it\"\u003e计算具有指数衰减的平均值\u003c/span\u003e。让 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e 是某个大于1的实数。\u003c/p\u003e\u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003e// setting this constant value correctly can adjust \u003cbr\u003e// the time range for which statistics will be calculated\u003cbr\u003edouble c \u003d \u003cspan class\u003d\"tex-font-style-it\"\u003esome constant value\u003c/span\u003e; \u003cbr\u003e\u003cbr\u003e// as the result of the algorithm\u0027s performance this variable will contain \u003cbr\u003e// the mean number of queries for the last \u003cbr\u003e// T seconds by the current moment of time\u003cbr\u003edouble mean \u003d 0.0; \u003cbr\u003e\u003cbr\u003efor t \u003d 1..n: // at each second, we do the following:\u003cbr\u003e // \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is the number of queries that came at the last second;\u003cbr\u003e mean \u003d (mean + \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e / T) / c;\u003cbr\u003e\u003c/pre\u003e\u003cp\u003e因此,平均变量每秒都会使用在该秒到达的查询次数进行重新计算。我们可以进行一些数学计算并证明正确选择常数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e 的值将使得 \u003cspan class\u003d\"tex-font-style-tt\"\u003emean\u003c/span\u003e 的值在 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e - \u003ci\u003eT\u003c/i\u003e + 1 ≤ \u003ci\u003ex\u003c/i\u003e ≤ \u003ci\u003et\u003c/i\u003e\u003c/span\u003e 时与真实平均值 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e 的值不会相差太大。\u003c/p\u003e\u003cp\u003e这种方法的优势在于它只使用当前时间点的请求次数,并不需要存储大时间范围内的请求历史。此外,它考虑到最近的值的权重大于旧值的权重,这有助于更快地对值的急剧变化做出反应。\u003c/p\u003e\u003cp\u003e然而,在工业编程中使用新的理论方法之前,有一个必须的步骤,那就是在给定的测试数据集上实际测试其可信度。你的任务是比较近似算法的工作结果和真实数据。\u003c/p\u003e\u003cp\u003e给定 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e 个值 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e,整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e 和实数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e。此外,还给定了 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e 个时间点 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ej\u003c/i\u003e ≤ \u003ci\u003em\u003c/i\u003e\u003c/span\u003e),我们对过去 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e 秒内的查询平均次数感兴趣。实现两个算法。第一个算法应该根据定义计算所需值,即使用公式 \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/51ae4f3dab75c191cae300b3e2f91b7c?v\u003d1711353901\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e。第二个算法应该按照上述描述计算平均值。打印出两个值,并通过公式 \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/236aba13e8759ea060f927dd0a621119?v\u003d1711353901\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 计算第二个算法的相对误差,其中 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eapprox\u003c/i\u003e\u003c/span\u003e 是第二个算法得到的近似值,\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ereal\u003c/i\u003e\u003c/span\u003e 是第一个算法得到的精确值。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e)、整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eT\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e)和实数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 \u0026lt; \u003ci\u003ec\u003c/i\u003e ≤ 100\u003c/span\u003e) — 资源应该工作的时间范围,我们需要计算平均请求次数的时间范围的长度,以及近似算法工作的系数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e。数字 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e 保留小数点后六位。\u003c/p\u003e\u003cp\u003e下一行包含 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e 个整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e\u003c/span\u003e) — 每个时间点服务的查询次数。\u003c/p\u003e\u003cp\u003e下一行包含整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003em\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) — 我们对过去 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e 秒内的查询平均次数感兴趣的时间点数量。\u003c/p\u003e\u003cp\u003e下一行包含 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e 个整数 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e(\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e ≤ \u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e),表示我们需要统计的另一个时间点。时间点 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e 严格递增。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e打印 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e 行。第 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e 行必须包含三个数字 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ereal\u003c/i\u003e\u003c/span\u003e、\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eapprox\u003c/i\u003e\u003c/span\u003e 和 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eerror\u003c/i\u003e\u003c/span\u003e,其中:\u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/450a0da4fb46944279373ae82e1709de?v\u003d1711353901\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 是过去 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e 秒内的真实平均查询次数; \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eapprox\u003c/i\u003e\u003c/span\u003e 是通过给定算法计算的,等于 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003emean\u003c/i\u003e\u003c/span\u003e 在时间点 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e \u003d \u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e(即在循环的 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e 次迭代后); \u003c/li\u003e\u003cli\u003e \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/7b572dc053cbfbbe6fe2105c28363814?v\u003d1711353901\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 是近似算法的相对误差。\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e你打印的数字将与相对或绝对误差 \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e - 4\u003c/sup\u003e\u003c/span\u003e 进行比较。建议打印数字时保留小数点后至少五位。\u003c/p\u003e"}},{"title":"示例 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 1 2.000000\n1\n1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1.000000 0.500000 0.500000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e11 4 1.250000\n9 11 7 5 15 6 6 6 6 6 6\n8\n4 5 6 7 8 9 10 11\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8.000000 4.449600 0.443800\n9.500000 6.559680 0.309507\n8.250000 6.447744 0.218455\n8.000000 6.358195 0.205226\n8.250000 6.286556 0.237993\n6.000000 6.229245 0.038207\n6.000000 6.183396 0.030566\n6.000000 6.146717 0.024453\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e13 4 1.250000\n3 3 3 3 3 20 3 3 3 3 3 3 3\n10\n4 5 6 7 8 9 10 11 12 13\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3.000000 1.771200 0.409600\n3.000000 2.016960 0.327680\n7.250000 5.613568 0.225715\n7.250000 5.090854 0.297813\n7.250000 4.672684 0.355492\n7.250000 4.338147 0.401635\n3.000000 4.070517 0.356839\n3.000000 3.856414 0.285471\n3.000000 3.685131 0.228377\n3.000000 3.548105 0.182702\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}