Написать пост

Задача про бесконечный поезд

Аватар Типичный программист

Обложка поста Задача про бесконечный поезд

Представьте себе замкнутую по окружности железную дорогу. По ней едет поезд, последний вагон которого скреплён с первым так, что внутри можно свободно перемещаться между вагонами. Вы оказались в одном случайном вагоне и ваша задача — подсчитать их общее количество. В каждом вагоне можно включать или выключать свет, но начальное положение переключателей случайное и заранее неизвестно.

Все вагоны внутри выглядят строго одинаково, окна закрыты так, что невозможно посмотреть наружу, движение поезда равномерное. Помечать вагоны как-либо, кроме включения или выключения света, нельзя. Количество вагонов конечно (не верьте заголовку).

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

С таким же успехом можно, например, ходить по сторонам от начального вагона на равные расстояния, постепенно их увеличивая, и инвертировать в них свет. То есть если считать, что сначала вы в вагоне с номером 0, то ходить надо в -1, 1, -2, 2, -3, 3 и так далее. Если при этом запоминать состояние самого дальнего вагона, то при повторном прохождении мимо него вы заметите изменившийся свет, если круг замкнётся. А зная длину пути в обе стороны, вы легко вычислите общее количество вагонов.

Следите за новыми постами
Следите за новыми постами по любимым темам
106К открытий106К показов