Август и Беатриса играют в игру. Август загадал натуральное число от 1 до n. Беатриса пытается угадать это число, для этого она называет некоторые множества натуральных чисел. Август отвечает Беатрисе YES, если среди названных ей чисел есть задуманное или NO в противном случае. После нескольких заданных вопросов Беатриса запуталась в том, какие вопросы она задавала и какие ответы получила и просит вас помочь ей определить, какие числа мог задумать Август.
Август и Беатриса играют в игру. Август загадал натуральное число от 1 до n. Беатриса пытается угадать это число, для этого она называет некоторые множества натуральных чисел. Август отвечает Беатрисе YES, если среди названных ей чисел есть задуманное или NO в противном случае. После нескольких заданных вопросов Беатриса запуталась в том, какие вопросы она задавала и какие ответы получила и просит вас помочь ей определить, какие числа мог задумать Август.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для начала надо определить минимальное количество вопросов, которые нужно задать, чтобы гарантированно угадать число, задуманное Августом. Если Август загадал число от 1 до n, то достаточно задать вопрос: Входит ли число n в задуманное множество? Если ответ YES, то число n - задуманное число, если NO - то задуманное число от 1 до n-1.
Теперь, если Беатриса задала k вопросов, то она может угадать число, которое задумал Август, только если все k чисел, названные ею, составляют подмножество множества из возможных чисел, которые мог задумать Август. Для этого надо, чтобы пересечение всех подмножеств, составленных из k чисел, которые могла назвать Беатриса, содержало задуманное число.
Таким образом, если пересечение всех подмножеств из k чисел, названных Беатрисой, не содержит задуманное число, то это число не может быть угадано Беатрисой при такой стратегии задания вопросов.
Например, если Август задумал число от 1 до 10, а Беатриса задала два вопроса: {2, 3, 5, 7, 9} и {1, 4, 6, 8, 10}, то пересечение этих подмножеств не содержит задуманное число, поэтому Беатриса не сможет угадать задуманное число.