69 lines
3.8 KiB
Markdown
69 lines
3.8 KiB
Markdown
---
|
||
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
|
||
```
|