|
Это не подсказка, уточнение условия. Ибо если математики должны отвечать одновременно решения нет. А вот если кто-то один, то другое дело. Предположим, что охранники настолько глупы, что дали одному математику число 1. Тогда он понимает, что у второго число 2. И когда охранники приходят первый раз, отвечает 2. Теперь предположим, что математикам дали числа 2,3.
Пришли охранники первый раз, математик с 2 молчит, освобождения не последовало. Значит у его товарища не 1, а 3. На второй приход охранников, математик с числом 2 называет большее число товарища.
Аналогично числа 3,4
На третий приход охранников математик с числом 3 исключает числа 1,2 называет 4.
На четвертый приход охранников математик с числом 4 называет 5.
...
На n-й приход математик с числом n называет n+1
А вот, то что им не разрешено предварительно договориться это печально. Охранники могут оказаться злобными и дать большое число. Впрочем, если число слишком большое я бы рискнул начать отсчет не с 1, а с какого-нибудь числа поближе. Например с ближайшего снизу простого числа. Допустим пусть дали числа 4671, 4672. Отсчет начинаем с ближайшего простого 4663. (Если одному из математиков досталось простое число или на единицу большее, то отсчет начинаем всё равно с предыдущего простого числа.)
Имеем 4671-4663=8. На 8 приход охранников математик с числом 4671 должен сказать 4672. Если бы у его товарища было 4670, то остается надеяться, что он назвал бы его на 7й приход охранников. При таком алгоритме время пребывания в тюрьме примерно было бы равно ln(n) дней.
|
Вход
FAQ
Поиск
