3.8 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f5021000cf542c510015 | Задача 406: Гра «Вгадування» | 5 | 302074 | problem-406-guessing-game |
--description--
Ми намагаємось знайти приховане число, вибране з набору цілих чисел {1, 2, ..., $n$}, задаючи питання. На кожне поставлене нами число (питання) ми отримуємо одну з трьох можливих відповідей:
- "Ваше припущення нижче за приховане число" (і ви підпадаєте під вартість а), або
- "Ваше припущення вище, ніж приховане число" (і ви підпадаєте під вартість b) або
- "Так, це воно!" (і гра закінчується).
Враховуючи значення n, a, і b, оптимальна стратегія мінімізує загальні витрати на найгірший з можливих випадків.
Наприклад, якщо n = 5, a = 2, та b = 3, тоді ми можемо задати "2" як наше перше питання.
Якщо нам кажуть, що 2 більше, ніж приховане число (для вартості b = 3), тоді ми впевнені, що "1" - це приховане число (для загальної вартості 3).
Якщо нам кажуть, що 2 менше, ніж приховане число (для вартості a = 2), тоді наше наступне запитання буде "4".
Якщо нам кажуть, що 4 більше, ніж приховане число (для вартості b = 3), тоді ми впевнені, що "3" - це приховане число (для загальної вартості 2 + 3 = \color{blue}{\mathbf{5}}).
Якщо нам кажуть, що 4 менше, ніж приховане число (для вартості a = 2), тоді ми впевнені, що "5" - це приховане число (для загальної вартості 2 + 2 = \color{blue}{\mathbf{4}}).
Таким чином, найгірша вартість досягнута цією стратегією, - 5. Також можна показати, що це найнижча найгірша вартість, яку можна досягти. Так, насправді, ми щойно описали оптимальну стратегію для заданих значень 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.
assert.strictEqual(guessingGame(), 36813.12757207);
--seed--
--seed-contents--
function guessingGame() {
return true;
}
guessingGame();
--solutions--
// solution required