Как оптимизировать блогеров?
Что-то давно здесь никаких моих любимых логически-математических задачек не было. Но недавно мне задали вот такую ->
Однажды блогеры собрались в поход. Но они попались какие-то не самые ходячие, далеко уходить не любят. Изначально все сидят в офисе. Выходя из офиса, каждый блогер может выйти и встать сразу за офисной дверью - или же на шаг впереди любого другого блогера. Но может и вообще не выходить. Любой блогер на улице, сразу за спиной которого находится другой блогер или офисная дверь, может вернуться в офис - все остальные блогеры отказываются двигаться с места. Как далеко смогут уйти от офиса десять блогеров? Все шаги у них одинаковые, они всегда смотрят в одну сторону -- от офиса и перпендикулярно офисной двери.
Например, в ситуации [офис, где блогер-1] [дверь] [пусто] [пусто] [блогер-2] [блогер-3] доступно три действия:
1: блогер-1 встаёт в первое пустое место за дверью офиса;
2: блогер-1 встаёт перед блогером-3;
3: блогер-3 возвращается в офис.
Блогер-2 ничего не может, поскольку за ним сзади пустое место.
Так вот, оказалось, что решение этой задачки заковыристое. Для десяти блогеров у меня получился 91 шаг. Но утверждается, что есть ещё более оптимальный алгоритм гуляния блогеров за дверью офиса. Но какой - голову сломал, ничего не придумал.
Не поможете? :)
Однажды блогеры собрались в поход. Но они попались какие-то не самые ходячие, далеко уходить не любят. Изначально все сидят в офисе. Выходя из офиса, каждый блогер может выйти и встать сразу за офисной дверью - или же на шаг впереди любого другого блогера. Но может и вообще не выходить. Любой блогер на улице, сразу за спиной которого находится другой блогер или офисная дверь, может вернуться в офис - все остальные блогеры отказываются двигаться с места. Как далеко смогут уйти от офиса десять блогеров? Все шаги у них одинаковые, они всегда смотрят в одну сторону -- от офиса и перпендикулярно офисной двери.
Например, в ситуации [офис, где блогер-1] [дверь] [пусто] [пусто] [блогер-2] [блогер-3] доступно три действия:
1: блогер-1 встаёт в первое пустое место за дверью офиса;
2: блогер-1 встаёт перед блогером-3;
3: блогер-3 возвращается в офис.
Блогер-2 ничего не может, поскольку за ним сзади пустое место.
Так вот, оказалось, что решение этой задачки заковыристое. Для десяти блогеров у меня получился 91 шаг. Но утверждается, что есть ещё более оптимальный алгоритм гуляния блогеров за дверью офиса. Но какой - голову сломал, ничего не придумал.
Не поможете? :)