Середнє останніх N

average-of-last-n-ukr.md

Середнє останніх N

Сервер отримує послідовність запитів. Кожен запит — це дійсне число, результат обчислення. Після кожного запиту потрібно повертати середнє значення останніх не більше ніж N чисел.

Вхідні дані

Перший рядок містить одне ціле число N (1 ≤ N ≤ 10⁵) — максимальна кількість останніх значень, які враховуються при обчисленні середнього.

Другий рядок містить одне ціле число Q (1 ≤ Q ≤ 10⁵) — кількість запитів.

Далі йдуть Q рядків, у кожному з яких — одне дійсне число xᵢ (-10⁶ ≤ xᵢ ≤ 10⁶) з точністю до 6 знаків після коми.

Вихідні дані

Виведіть Q рядків — середнє значення останніх не більше ніж N чисел після кожного запиту. Відповіді виводьте з точністю не менше ніж 6 знаків після коми.

Приклад

Вхідні дані:

3
5
1.0
2.0
3.0
4.0
5.0

Вихідні дані:

1.000000
1.500000
2.000000
3.000000
4.000000

Пояснення:

• Після першого: [1.0] → 1.0
• Після другого: [1.0, 2.0] → 1.5
• Після третього: [1.0, 2.0, 3.0] → 2.0
• Після четвертого: [2.0, 3.0, 4.0] → 3.0
• Після п’ятого: [3.0, 4.0, 5.0] → 4.0

everage-of-last-n-en.md

Average of the Last N

The server receives a sequence of requests. Each request is a floating-point number representing the result of a computation. After each request, you must return the average of no more than the last N numbers.

Input

The first line contains an integer N (1 ≤ N ≤ 10^5) — the maximum number of recent values to consider when computing the average.

The second line contains an integer Q (1 ≤ Q ≤ 10^5) — the number of requests.

The next Q lines each contain a floating-point number xᵢ (-10^6 ≤ xᵢ ≤ 10^6) with up to 6 digits after the decimal point.

Output

Print Q lines — the average of no more than the last N values after each request. Each answer must be printed with at least 6 digits after the decimal point.

Example

Input:

3
5
1.0
2.0
3.0
4.0
5.0

Output:

1.000000
1.500000
2.000000
3.000000
4.000000

Explanation:

• After first: [1.0] → 1.0
• After second: [1.0, 2.0] → 1.5
• After third: [1.0, 2.0, 3.0] → 2.0
• After fourth: [2.0, 3.0, 4.0] → 3.0
• After fifth: [3.0, 4.0, 5.0] → 4.0

'use strict';

class CircularList {
  #size = 0;
  #head = 0;
  #tail = 0;
  #list = null;
  #sum = 0;
  #overflow = false;
  #length = 0;

  constructor(size, initVal = -0.1) {
    this.#size = size;
    this.#list = new Array(size).fill(initVal);
  }

  push(val) {
    if (this.#overflow) this.shift();

    this.#list[this.#tail] = val;
    this.#sum += val;
    this.#length++;

    if (++this.#tail === this.#size) this.#tail = 0;
    this.#overflow = this.#head === this.#tail;
  }

  shift() {
    if (this.length === 0) return;

    this.#sum -= this.#list[this.#head];
    this.#length--;

    if (++this.#head === this.#size) this.#head = 0;
    this.#overflow = false;
  }

 values() {
    let res = [];
    if (this.length === 0) return res;

    const list = this.#list;
    const listLength = this.#size;
    const itemsCount = this.#length;
    const start = this.#head;
    const end = start + itemsCount;

    if (end <= listLength) {
      res = list.slice(start, end);
    } else {
      const sliceA = list.slice(start, listLength);
      const sliceB = list.slice(0, this.#tail);
      res = sliceA.concat(sliceB);
    }
    return res;
  }

  get sum() {
    return this.#sum;
  }

  get length() {
    return this.#length;
  }
  
  get state() {
    const list = this.values();
    const head = this.#head;
    const tail = this.#tail;
    const sum = this.sum;
    const len = this.length;
    return { list, head, tail, sum, len };
  }
}

const list = new CircularList(3);

for (let i = 0; i < 7; i++) {
  list.push(i);
  console.log(list.state);
}

console.log('--------');

for (let i = 0; i < 7; i++) {
  list.shift();
  console.log(list.state);
}

@artem-ye ,

дякую за рішення.
Виглядає робочим, але трохи надлишковим:

• shift() -- не треба, то ж спробуйте лишити, або тільки #head, або тільки #tail
• варто розділити логику буфера та логіку стану (я зробив два окреми класи)
• values() -- краще зробити ітератором, як це працює для Set та Map

@DScheglov, я навіть не думав, що хотсь буде дивитись, дякую.
В мене було трохи часу, ось що вийшло

'use strict';

class CircularList {
  #size = 0;
  #tail = 0;
  #list = null;
  #length = 0;

  constructor(size, initVal = -0.1) {
    this.#size = size;
    this.#list = new Array(size).fill(initVal);
  }

  push(val) {
    let popVal = 0;
    if (this.#length < this.#size) {
      this.#length++;
    } else {
      popVal = this.#list[this.#tail];
    }

    this.#list[this.#tail] = val;
    if (++this.#tail === this.#size) this.#tail = 0;

    return {
      length: this.#length,
      popVal,
    };
  }

  get #head() {
    const tail = this.#tail;
    const offset = this.#length;
    const size = this.#size;
    let head = tail - offset;
    if (head < 0) head += size;
    return head;
  }

  get length() {
    return this.#length;
  }

  *values() {
    if (this.#length === 0) return;

    const head = this.#head;
    const offset = this.#length - 1;
    const tail = head + offset;
    const top = this.#size - 1;
    const overflow = tail > top ? tail - top : 0;

    for (let i = head; i <= tail - overflow; i++) yield this.#list[i];

    if (overflow === 0) return;
    for (let i = 0; i <= overflow - 1; i++) yield this.#list[i];
  }

  *valuesHumanReadable() {
    const length = this.#length;
    const head = this.#head;
    for (let n = 0, i = head; n < length; n++) {
      yield this.#list[i];
      if (++i === length) i = 0;
    }
  }
}

class CircularAdder {
  #list = null;
  #sum = 0;
  #length = 0;

  constructor(size, initVal) {
    this.#list = new CircularList(size, initVal);
  }

  push(val) {
    const { length, popVal } = this.#list.push(val);
    this.#length = length;
    this.#sum += val - popVal;
  }

  count() {
    return this.#length;
  }

  sum() {
    return this.#sum;
  }

  avg() {
    return this.#length === 0 ? 0 : this.#sum / this.#length;
  }

  values() {
    return this.#list.values();
  }
}

const list = new CircularAdder(3);

for (let i = 0; i < 7; i++) {
  list.push(i);
  const sum = list.sum();
  const arr = [];
  for (const e of list.values()) arr.push(e);
  console.log({ sum, arr });
}

@artem-ye
В мене вийшло дуже схоже -- я зроблю mention під приватним gist-ом, щоб Ви змогли порівняти

@DScheglov Дякую, побачив, дійсно дуже схоже.
Спробуйте показати свій код Тімуру, може він щось порадить.