1.7 KiB
1.7 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f4d91000cf542c50ffea | Задача 364: Комфортна відстань | 5 | 302025 | problem-364-comfortable-distance |
--description--
Є N місць поспіль. N людей приходять один за одним та займають місця відповідно до таких правил:
- Якщо є будь-яке місце, сусіднє місце (місця) якого не зайняте, займіть таке місце.
- Якщо такого місця немає і є місце, для якого зайнято лише одне сусіднє місце, займіть таке місце.
- В іншому випадку займіть одне з наявних місць.
Нехай T(N) буде кількістю можливостей, що N місць зайняті N людьми з даними правилами. Наступний малюнок показує T(4) = 8.
Можна перевірити, що 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.
assert.strictEqual(comfortableDistance(), 44855254);
--seed--
--seed-contents--
function comfortableDistance() {
return true;
}
comfortableDistance();
--solutions--
// solution required