51 lines
1.7 KiB
Markdown
51 lines
1.7 KiB
Markdown
---
|
||
id: 5900f4d91000cf542c50ffea
|
||
title: 'Задача 364: Комфортна відстань'
|
||
challengeType: 5
|
||
forumTopicId: 302025
|
||
dashedName: problem-364-comfortable-distance
|
||
---
|
||
|
||
# --description--
|
||
|
||
Є $N$ місць поспіль. $N$ людей приходять один за одним та займають місця відповідно до таких правил:
|
||
|
||
1. Якщо є будь-яке місце, сусіднє місце (місця) якого не зайняте, займіть таке місце.
|
||
2. Якщо такого місця немає і є місце, для якого зайнято лише одне сусіднє місце, займіть таке місце.
|
||
3. В іншому випадку займіть одне з наявних місць.
|
||
|
||
Нехай $T(N)$ буде кількістю можливостей, що $N$ місць зайняті $N$ людьми з даними правилами. Наступний малюнок показує $T(4) = 8$.
|
||
|
||
<img class="img-responsive center-block" alt="вісім способів для N місць, зайняті N людьми" src="https://cdn.freecodecamp.org/curriculum/project-euler/comfortable-distance.gif" style="background-color: white; padding: 10px;" />
|
||
|
||
Можна перевірити, що $T(10) = 61\\,632$ та $T(1\\,000)\bmod 100\\,000\\,007 = 47\\,255\\,094$.
|
||
|
||
Знайдіть $T(100\\,000\\,000)\bmod 1\\,000\\,007$.
|
||
|
||
# --hints--
|
||
|
||
`comfortableDistance()` має повернути `44855254`.
|
||
|
||
```js
|
||
assert.strictEqual(comfortableDistance(), 44855254);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function comfortableDistance() {
|
||
|
||
return true;
|
||
}
|
||
|
||
comfortableDistance();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|