---
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
```