57 lines
4.2 KiB
Markdown
57 lines
4.2 KiB
Markdown
---
|
||
id: 5900f4b41000cf542c50ffc7
|
||
title: 'Завдання 328: Найменш затратний пошук'
|
||
challengeType: 5
|
||
forumTopicId: 301985
|
||
dashedName: problem-328-lowest-cost-search
|
||
---
|
||
|
||
# --description--
|
||
|
||
Ставлячи питання, ми намагаємося знайти прихований номер, вибраний із множини цілих чисел {1, 2, ..., $n$}. Кожне число (питання) яке ми запитуємо, має <u>вартість відповідну до поставленого питання</u> і ми отримуємо одну з трьох можливих відповідей:
|
||
|
||
- "Ваше припущення менше, ніж приховане число", або
|
||
- "Так, це воно!" або
|
||
- "Ваше припущення більше за приховане число".
|
||
|
||
Зважаючи на значення $n$, оптимальна стратегія мінімізує загальні витрати (наприклад, сума всіх поставлених запитань) <u>для найгіршого можливого випадку</u>. Наприклад:
|
||
|
||
Якщо $n = 3$, то, очевидно, найкраще, що ми можемо зробити, це запитати число "<strong>2</strong>". Відповідь одразу приведе нас до прихованого числа (загальні витрати = 2).
|
||
|
||
Якщо $n = 8$, ми можемо використати стратегію "двійкового пошуку": нашим першим питанням буде "<strong>4</strong>", і якщо приховане число перевищує 4, нам знадобиться одне або два додаткових запитання. Нехай наше друге питання буде "<strong>6</strong>". Якщо приховане число все ще вище, ніж 6, нам знадобиться третє питання, щоб вирішити між 7 і 8. Таким чином наше третє питання буде "<strong>7</strong>" і загальна вартість, у найгіршому випадку буде $4 + 6 + 7 = \mathbf{\color{red}{17}$.
|
||
|
||
Ми можемо значно поліпшити найгіршу ціну за $n = 8$, запитуючи спершу "<strong>5</strong>". Якщо нам кажуть, що приховане число вище, ніж 5, наше друге запитання буде "<strong>7</strong>", тоді ми дізнаємося, яким буде приховане число (для загальної вартості $5 + 7 = \mathbf{\color{blue}{12}}$). Якщо нам кажуть, що приховане число менше за 5, наше друге запитання буде "<strong>3</strong>", і якщо приховане число буде менше, то третє питання буде "<strong>1</strong>", в результаті ми отримуємо загальну вартість $5 + 3 = \mathbf{\color{blue}{9}}$. Оскільки $\mathbf{\color{blue}{12 > 9}}$, то найвища ціна у цій стратегії - <strong><span style="color: red;">12</span></strong>. Це краще, ніж те, чого ми раніше досягли зі стратегією "двійкового пошуку", це також краще або дорівнює будь-якій іншій стратегії. Таким чином ми щойно описали оптимальну стратегію для $n = 8$.
|
||
|
||
Нехай $C(n)$ буде найгіршою вартістю, досягнутою оптимальною стратегією для $n$, як описано вище. Таким чином $C(1) = 0$, $C(2) = 1$, $C(3) = 2$ та $C(8) = 12$.
|
||
|
||
Аналогічно, $C(100) = 400$ і $\displaystyle\sum_{n = 1}^{100} C(n) = 17575$.
|
||
|
||
Знайдіть $\displaystyle\sum_{n = 1}^{200\\,000} C(n)$.
|
||
|
||
# --hints--
|
||
|
||
`lowestCostSearch()` має повернути `260511850222`.
|
||
|
||
```js
|
||
assert.strictEqual(lowestCostSearch(), 260511850222);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function lowestCostSearch() {
|
||
|
||
return true;
|
||
}
|
||
|
||
lowestCostSearch();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|