Загадано число от 1 до 377. Разрешается выделить одно подмножество множества чисел от 1 до 377 и спросить, принадлежит ли ему загаданное число. За ответ «да» надо заплатить 2 рубля, за ответ «нет» - 1 рубль. Какая наименьшая сумма денег необходима для того, чтобы наверняка угадать число?
Обозначим через F(c) максимальное число вариантов, которое можно гарантированно различить, если мы готовы потратить суммарно не более c рублей в худшем случае. При каждом вопросе мы выбираем некоторое подмножество. Если ответ «да», то тратим 2 рубля и остаётся бюджет c–2, если «нет» – 1 рубль и бюджет c–1. Тогда можно рассуждать следующим образом: если мы зададим вопрос, то в зависимости от ответа мы сможем различить F(c–2) вариантов при ответе «да» и F(c–1) вариантов при ответе «нет». Чтобы полностью различить число, общее число вариантов должно быть не больше суммы этих возмож...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Не нашел нужную задачу?