freeCodeCamp/curriculum/challenges/ukrainian/10-coding-interview-prep/project-euler/problem-472-comfortable-distance-ii.md

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
5900f5451000cf542c510057	Проблема 472: Комфортна відстань II	5	302149	problem-472-comfortable-distance-ii

--description--

Є N місць поспіль. N людей приходять один за одним та займають місця згідно з даними правилами:

1. Жодна людина не сидить поруч з іншою.
2. Перша людина обирає будь-яке місце.
3. Кожна наступна людина вибирає місце, найбільш віддалене від того, хто вже сидить, до тих пір, поки воно не порушує правило 1. Якщо існує більше одного варіанту, що задовільняє цю умову, то людина обирає місце зліва.

Зверніть увагу, що через правило 1, деякі місця, безумовно, будуть вільними, і максимальна кількість осіб, які можуть бути розміщені, менша за N (для N > 1).

Ось можливі розстановки для N = 15:

Ми бачимо, що якщо перша людина обирає правильно, то на 15 місцях може бути до 7 осіб. Ми також можемо бачити, що перша людина має 9 варіантів, щоб максимізувати кількість осіб, яких можна розмістити.

Нехай f(N) буде кількістю варіантів, які перша людина має, аби максимізувати кількість людей для N місць поспіль. Таким чином, f(1) = 1, f(15) = 9, f(20) = 6, та f(500) = 16.

Також \sum f(N) = 83 за 1 ≤ N ≤ N ≤ 20 і \sum f(N) = 13\\,343 за 1 ≤ N ≤ 500.

Знайдіть \sum f(N) для 1 ≤ N ≤ {10}^{12}. Впишіть останні 8 цифр вашої відповіді.

--hints--

comfortableDistanceTwo() повинен повертатися як 73811586.

assert.strictEqual(comfortableDistanceTwo(), 73811586);

--seed--

--seed-contents--

function comfortableDistanceTwo() {

  return true;
}

comfortableDistanceTwo();

--solutions--

// solution required