51 lines
1.8 KiB
Markdown
51 lines
1.8 KiB
Markdown
|
---
|
|||
|
|
id: 5900f3df1000cf542c50fef1
|
|||
|
|
title: 'Завдання 115: Підрахунок комбінацій блоків ІІ'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 301741
|
|||
|
|
dashedName: problem-115-counting-block-combinations-ii
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Рядок довжиною `n` одиниць містить червоні блоки з мінімальною довжиною `m` одиниць, тому будь-які два червоні блоки (які можуть бути будь-якої довжини) розділені як мінімум одним чорним квадратом.
|
|||
|
|
|
|||
|
|
Нехай функція підрахунку $F(m, n)$ представляє кількість способів заповнення рядка.
|
|||
|
|
|
|||
|
|
Наприклад, $F(3, 29) = 673135$ та $F(3, 30) = 1089155$.
|
|||
|
|
|
|||
|
|
Тобто для m = 3 видно, що n = 30 — це найменше значення, для якого функція fill-count перевищує один мільйон.
|
|||
|
|
|
|||
|
|
Точно так само для m = 10 можна перевірити, що $F(10, 56) = 880711$ та $F(10, 57) = 1148904$, то ж n = 57 — це найменше значення, для якого функція fill-count перевищує один мільйон.
|
|||
|
|
|
|||
|
|
Для m = 50, знайдіть найменше значення `n`, для якого функція fill-count спочатку перевищує один мільйон.
|
|||
|
|
|
|||
|
|
**Примітка:** Це — складніша версія Завдання 114.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`countingBlockTwo()` повинен повертатися як `168`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(countingBlockTwo(), 168);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function countingBlockTwo() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
countingBlockTwo();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|