---
id: 5900f5021000cf542c510015
title: 'Задача 406: Гра «Вгадування»'
challengeType: 5
forumTopicId: 302074
dashedName: problem-406-guessing-game
---

# --description--

Ми намагаємось знайти приховане число, вибране з набору цілих чисел {1, 2, ..., $n$}, задаючи питання. На кожне поставлене нами число (питання) ми отримуємо одну з трьох можливих відповідей:

- "Ваше припущення нижче за приховане число" (і ви підпадаєте під вартість а), або
- "Ваше припущення вище, ніж приховане число" (і ви підпадаєте під вартість b) або
- "Так, це воно!" (і гра закінчується).

Враховуючи значення $n$, $a$, і $b$, оптимальна стратегія мінімізує загальні витрати <u>на найгірший з можливих випадків</u>.

Наприклад, якщо $n = 5$, $a = 2$, та $b = 3$, тоді ми можемо задати "<strong>2</strong>" як наше перше питання.

Якщо нам кажуть, що 2 більше, ніж приховане число (для вартості $b = 3$), тоді ми впевнені, що "<strong>1</strong>" - це приховане число (для загальної вартості <strong><span style="color: blue;">3</span></strong>).

Якщо нам кажуть, що 2 менше, ніж приховане число (для вартості $a = 2$), тоді наше наступне запитання буде "<strong>4</strong>".

Якщо нам кажуть, що 4 більше, ніж приховане число (для вартості $b = 3$), тоді ми впевнені, що "<strong>3</strong>" - це приховане число (для загальної вартості $2 + 3 = \color{blue}{\mathbf{5}}$).

Якщо нам кажуть, що 4 менше, ніж приховане число (для вартості $a = 2$), тоді ми впевнені, що "<strong>5</strong>" - це приховане число (для загальної вартості $2 + 2 = \color{blue}{\mathbf{4}}$).

Таким чином, найгірша вартість досягнута цією стратегією, - <strong><span style="color: red">5</span></strong>. Також можна показати, що це найнижча найгірша вартість, яку можна досягти. Так, насправді, ми щойно описали оптимальну стратегію для заданих значень $n$, $a$і $b$.

Нехай $C(n, a, b)$ буде найгіршою вартістю, досягнутою оптимальною стратегією для заданих значень $n$, $a$та $b$.

Ось декілька прикладів:

$$\begin{align}   & C(5, 2, 3) = 5 \\\\
  & C(500, \sqrt{2}, \sqrt{3}) = 13.220\\,731\\,97\ldots \\\\   & C(20\\,000, 5, 7) = 82 \\\\
  & C(2\\,000\\,000, √5, √7) = 49.637\\,559\\,55\ldots \\\\ \end{align}$$

Нехай $F_k$ буде цифрами фібоначчі: $F_k = F_{k - 1} + F_{k - 2}$ з базовими кешами $F_1 = F_2 = 1$.

Знайдіть $\displaystyle\sum_{k = 1}^{30} C({10}^{12}, \sqrt{k}\sqrt{F_k})$, і дайте відповідь, округлену до 8 десяткових знаків після коми.

# --hints--

`guessingGame()` має повернути `36813.12757207`.

```js
assert.strictEqual(guessingGame(), 36813.12757207);
```

# --seed--

## --seed-contents--

```js
function guessingGame() {

  return true;
}

guessingGame();
```

# --solutions--

```js
// solution required
```