B. Average Sleep Time

Codeforces

IDCF808B

Time1000ms

Memory256MB

Difficulty—

data structuresimplementationmath

English · Original

Chinese · Translation

Formal · Original

It's been almost a week since Polycarp couldn't get rid of insomnia. And as you may already know, one week in Berland lasts _k_ days! When Polycarp went to a doctor with his problem, the doctor asked him about his sleeping schedule (more specifically, the average amount of hours of sleep per week). Luckily, Polycarp kept records of sleep times for the last _n_ days. So now he has a sequence _a_1, _a_2, ..., _a__n_, where _a__i_ is the sleep time on the _i_\-th day. The number of records is so large that Polycarp is unable to calculate the average value by himself. Thus he is asking you to help him with the calculations. To get the average Polycarp is going to consider _k_ consecutive days as a week. So there will be _n_ - _k_ + 1 weeks to take into consideration. For example, if _k_ = 2, _n_ = 3 and _a_ = \[3, 4, 7\], then the result is . You should write a program which will calculate average sleep times of Polycarp over all weeks. ## Input The first line contains two integer numbers _n_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 2·105). The second line contains _n_ integer numbers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 105). ## Output Output average sleeping time over all weeks. The answer is considered to be correct if its absolute or relative error does not exceed 10 - 6. In particular, it is enough to output real number with at least 6 digits after the decimal point. [samples] ## Note In the third example there are _n_ - _k_ + 1 = 7 weeks, so the answer is sums of all weeks divided by 7.

自从波利卡普患上失眠症已经快一周了。正如你可能已经知道的，贝兰的一周由 #cf_span[k] 天组成！当波利卡普带着这个问题去看医生时，医生问他关于他的睡眠计划（更具体地说，是每周的平均睡眠小时数）。幸运的是，波利卡普记录了过去 #cf_span[n] 天的睡眠时间。因此，他现在有一个序列 #cf_span[a1, a2, ..., an]，其中 #cf_span[ai] 表示第 #cf_span[i] 天的睡眠时间。记录的数量如此庞大，波利卡普无法自己计算平均值。因此他请求你帮助他进行计算。为了计算平均值，波利卡普将考虑 #cf_span[k] 个连续天作为一周。因此共有 #cf_span[n - k + 1] 个星期需要考虑。例如，如果 #cf_span[k = 2]，#cf_span[n = 3] 且 #cf_span[a = [3, 4, 7]]，则结果为。你需要编写一个程序，计算波利卡普在所有星期中的平均睡眠时间。第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 2·105]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 105]）。请输出所有星期中的平均睡眠时间。如果答案的绝对误差或相对误差不超过 #cf_span[10 - 6]，则认为答案正确。特别地，只需输出至少保留小数点后6位的实数即可。在第三个示例中，有 #cf_span[n - k + 1 = 7] 个星期，因此答案是所有星期的总和除以 7。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 2·105]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 105]）。 ## Output 请输出所有星期中的平均睡眠时间。如果答案的绝对误差或相对误差不超过 #cf_span[10 - 6]，则认为答案正确。特别地，只需输出至少保留小数点后6位的实数即可。 [samples] ## Note 在第三个示例中，有 #cf_span[n - k + 1 = 7] 个星期，因此答案是所有星期的总和除以 7。

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 1 \leq k \leq n \leq 2 \cdot 10^5 $. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers with $ 1 \leq a_i \leq 10^5 $. **Constraints** 1. $ 1 \leq k \leq n \leq 2 \cdot 10^5 $ 2. $ 1 \leq a_i \leq 10^5 $ for all $ i \in \{1, \dots, n\} $ **Objective** Compute the average sleep time over all contiguous $ k $-day weeks: $$ \text{Average} = \frac{1}{n - k + 1} \sum_{i=1}^{n - k + 1} \left( \sum_{j=i}^{i+k-1} a_j \right) $$

Samples

Input #1

3 2
3 4 7

Output #1

9.0000000000

Input #2

1 1
10

Output #2

10.0000000000

Input #3

8 2
1 2 4 100000 123 456 789 1

Output #3

28964.2857142857

API Response (JSON)

{
  "problem": {
    "name": "B. Average Sleep Time",
    "description": {
      "content": "It's been almost a week since Polycarp couldn't get rid of insomnia. And as you may already know, one week in Berland lasts _k_ days! When Polycarp went to a doctor with his problem, the doctor asked",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF808B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "It's been almost a week since Polycarp couldn't get rid of insomnia. And as you may already know, one week in Berland lasts _k_ days!\n\nWhen Polycarp went to a doctor with his problem, the doctor asked...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "自从波利卡普患上失眠症已经快一周了。正如你可能已经知道的，贝兰的一周由 #cf_span[k] 天组成！\n\n当波利卡普带着这个问题去看医生时，医生问他关于他的睡眠计划（更具体地说，是每周的平均睡眠小时数）。幸运的是，波利卡普记录了过去 #cf_span[n] 天的睡眠时间。因此，他现在有一个序列 #cf_span[a1, a2, ..., an]，其中 #cf_span[ai] 表示第 #cf_s...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq n \\leq 2 \\cdot 10^5 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ 1 \\leq a_i \\leq 10^5 $.\n\n**Constraints**...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments