img img img img img img img img img img img img img img img img img img img img img img
Логотип Человек живет, пока думает.
Решайте задачи и живите долго!
Для участия в проекте необходимо
и достаточно зарегистрироваться!
Rss Регистрация || Вход
Вход
Diofant.ru
Картинка
Отражение Отражение Картинка Картинка
отражение
Лента событий: DOMASH решил задачу "Все стороны трапеции" (Математика):
+ 0

Задача 509. Игра "Угадай число!" с весами

постоянный адрес задачи: http://www.diofant.ru/problem/2425/
показать код для вставки на свой сайт >>
Задачу решили: 1
всего попыток: 4
поделиться задачей:

Задача опубликована: 20.05.13 08:00
Прислал: admin img
Источник: Проект "Эйлер" (http://projecteuler.net)
Вес: 2
сложность: 3 img
баллы: 100
Темы: алгоритмыimg

Широко известна игра, где один из участников задумывает целое число, а другой пытается его угадать, задавая вопросы. В этой задаче исследуется вариант такой игры, когда задумывают натуральное число из промежутка [1,n], а в качестве вопросов разрешается называть натуральные числа из этого же интервала. При этом стоимость каждого вопроса равна названному числу. Допускаются ответы трех видов:

  1. Ты назвал число меньше задуманного.
  2. Ты угадал!
  3. Ты назвал число больше задуманного.

Требуется определить  задуманное число и при этом минимизировать суммарную стоимость вопросов (в дальнейшем – цена игры). Для данного числа n назовем стратегию оптимальной, если она минимизирует цену игры для самого неудачного задуманного числа.

Например, при n=3 наилучшим первым ходом будет число "2". После этого при любом ответе можно будет точно определить задуманное число, поэтому больше вопросов не потребуется, и цена игры будет равна 2.

Если n=8, мы могли бы выбрать в качестве стратегии "бинарный поиск". Если первым ходом мы назовем число "4", а задуманное число будет больше, чем 4, нам потребуется еще два вопроса. Пусть вторым ходом мы называем число "6". Если задуманное число больше, чем 6, нам потребуется еще один ход, скажем, "7", и цена игры составит 4+6+7=17.

Мы можем существенно улучшить нашу стратегию для n=8, если первым ходом назовем число "5". Если задуманное число больше, чем 5, то вторым ходом мы можем назвать число "7", и этого будет достаточно для нахождения задуманного. Тогда цена игры составит 5+7=12. Если же задуманное число меньше, чем 5, то для его определения достаточно  вторым и третьим ходом назвать "3" и "1", а цена игры составит 5+3+1=9. Поскольку 12 > 9, в худшем случае цена игры при этой стратегии будет равна 12. Получается, что данная стратегия более выгодна, чем предыдущая, и оказывается, что она оптимальна, то есть никакая другая стратегия не может гарантировать для n=8 результат меньший, чем 12.

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

Тогда C(1) = 0, C(2) = 1, C(3) = 2 и C(8) = 12.

Можно подсчитать, что  C(100) = 400.

Найдите С(500000).

 
 
Пожалуйста, не пишите нам, что Вы не можете решить задачу.
Если Вы не можете ее решить, значит Вы не можете ее решить :-)

Обсуждение Правила >>

Внимание! В обсуждении задачи запрещено публиковать ответы и давать подсказки.
 
Внимание! Если Вы увидите ошибку на нашем сайте, выделите её и нажмите Ctrl+Enter.