Игры вслепую

Будем действовать по следующему алгоритму, попутно объясняя, почему он сработает. Рассмотрим висячую вершину дерева и подвесим граф за нее. Сначала назовем только вершину

) Если нам ответили не 0. Тогда нам могли ответить только Обозначим смежную с вершину через и спросим про и Если нам отвечают не то это означает, что фишка стоит не в этот случай будет подходить под рассматриваемые далее. Если нам все-таки отвечают то спросим про и все вершины, смежные с Причем спросим про это множество дважды. Заметим, что если хоть раз мы услышим ответ или больше, то сможем определить положение фишки. Если же нам не ответят, то это означает, что сейчас, после нашего вопроса, фишка находится ни в ни в Этот случай будет подходить под рассматриваемые далее, потому что это то же самое, что спросить только про и услышать ответ

) Итак, можно считать, что мы услышали ответ Это означает, что ни в ни рядом с фишка на предыдущем ходу не стояла. Мы будем увеличивать множество вершин, про которые задается вопрос на очередном шаге, добавляя следующую вершину, смежную с последней из добавленных. При этом есть две возможности, при которых мы начинаем действовать по-другому.

Назовем разветвлением вершину, степень которой больше 3.

a) Последняя добавленная к множеству вершина не является разветвлением, но при этом мы услышали в ответ не Заметим, что так как до этого множество, про которое мы спрашиваем, с фишкой не соседствовало, то мы можем услышать только или причем если мы услышали то фишка находилась в соседней с вершине и мы ее определяем, а если то в самой вершине что мы также определим. Этот подслучай разобран.

б) Последняя добавленная к множеству вершина является разветвлением. Если при этом нам ответили (а больше ответить нам и не могли), то фишка находилась в вершине Если нам ответили то спросим про то же самое множество вершин (обозначим его через ) еще раз. Если нам отвечают не то мы можем однозначно определить положение фишки. Итак, мы добились, чтобы нам ответили Получается, что фишка находится на одной из ветвей, выходящих из вершины

Будем проверять эти ветви по очереди. Сначала спросим про всю первую ветку (без ). Пусть мы услышали ответ Тогда повторим вопрос про множество пока не услышим (как мы выяснили ранее, либо за вопроса мы этого добьемся, либо выясним местоположение фишки). Затем проверим следующую ветку, и так далее, пока не найдем ветку, в которой находится фишка. Вновь проверим множество пока не услышим в ответ. За все наши вопросы фишка не может переходить с ветки на ветку, значит, мы точно знаем, на какой ветке сейчас фишка. Все остальные ветви отбрасываем и добавляем к множеству фишек, про которые мы сейчас будем спрашивать, первую фишку нужно ветви. Далее действуем по тому же алгоритму. Заметим, что рано или поздно он закончится, так как на отбрасываемых ветках фишка оказаться не может. Значит, в итоге мы найдем фишку.