Мы пытаемся найти неизвестное число, выбранное из множества целых чисел {1, 2, ..., n}, задавая вопросы. С каждым числом (вопросом), которое мы спрашиваем, мы получаем один из трех возможных ответов:

• "Названное вами число меньше загаданного" (и с вас взимается плата a), или
• "Названное вами число больше загаданного" (и с вас взимается плата 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=5).
Если нам сообщают, что 4 меньше загаданного числа (за плату a=2), тогда мы уверены, что "5" - это загаданное число (всего потратив 2+2=4).
Итак, при этой стратегии затраты в худшем возможном случае составят 5. Можно также показать, что это - самая маленькая затрата в худшем возможном случае, которую можно достичь. Таким образом, мы только что описали оптимальную стратегию для данных значений n, a и b.

Пусть C(n, a, b) будет затратами в худшем возможном случае при оптимальной стратегии для данных значений n, a и b.

Вот несколько примеров:
C(5, 2, 3) = 5
C(500, √2, √3) = 13.22073197...
C(20000, 5, 7) = 82
C(2000000, √5, √7) = 49.63755955...

Пусть F_k будет числами Фибоначчи: F_k = F_k-1 + F_k-2 с начальными значениями F₁ = F₂ = 1.
Найдите ∑_1≤k≤30 C(10¹², √k, √F_k), и приведите полученный ответ округленным до 8 знака после десятичной точки.