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

Question

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

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

Как посчитать количество вагонов?

Answer 1

Сначала все сделать выключенными, потом включить первый и считать сколько прошли

Answer 2

Если уж не нравится критерий достаточно долго, можно тогда попробовать следующим образом: вагон в котором мы находимся 0й и в нем мы включаем свет, двигаемся в одном выбранном направлении, считая вагоны, пока не встретим вагон со включенным светом, выключаем его и возвращаемся назад в 0й вагон(мы знаем где он, тк считаем вагоны при перемещении). Продолжаем до тех пор пока в 0м вагоне не погаснет свет, это будет значить что мы обошли весь поезд. Но я чет туплю и не могу оценить сложность алгоритма, O(n^2)?

Answer 3

Мы их считаем КАЖДЫЙ раз, и в 0м горит свет пока круг не замкнется

Answer 4

Можно включить свет в 0м вагоне, а затем ходить влево и вправо на одинаковое расстояние при этом выключая свет и ведя подсчет вагонов. На каком-то этапе мы выключим свет в 0 вагоне.

Answer 5

Если будет четное, то на последнем этапе, находясь в 0 вагоне, зажечь свет и сделать 1 проход в ту же сторону но уже на n-1 шагов

Answer 6

Да👍. Намного быстрее в 1 сторону с возвращением и проверкой в 0 вагоне.

Answer 7

Смотрите, другая идея посетила, а что есть нам весь поезд "отформатировать" чередованием вкл-выкл-вкл-выкл....? Тогда в определенный момент при четном количестве вагонов при прохождении поезда нам больше не придется переключать свет, тогда потребуется поставить маркет отсчета (думаем как). При нечетном количестве вагонов начало отсчета само себя укажет, там 2 соседних вагона всегда будут с одним и тем же состоянием света... Как минимум нужно будет несколько раз пройти по всему поезду.

Answer 8

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

Answer 9

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

Answer 10

Итераций будет много, да, но этот способ надёжный. Количество проходов будет всего n*2, где n - количество вагонов

Answer 11

С прохождением в 1 сторону есть тоже возможность что ты наткнешься на точно такую же маркировку, вероятность возрастает при увеличении числа вагонов

Answer 12

Поправьте, если я считаю не правильно, но количество пройденных вагонов в худшем случае(если все включены) получается сумма по k = 0 до n - 1, от произведения (2k+1)(n-k), что даем весьма не утешительные результаты, так для 10 вагонов мы пройдём 385 вагонов, что даже не n^2

Answer 13

А нет, я дважды учла переход(зря влезла в общий вид, отвлеклась и не то написала), все ок там примерно 2n+n^2 должно быть

Answer 14

Надо было расписывать снизу вверх, так для 10 вагонов получается 21(последний круг) 19 (туда - обратно для 10 вагонов), 17 для 9... 3 для 2х, и 120 всего

Answer 15

Хорошо, а если рассмотреть на примере 5 вагонов. Находясь в 0м вагоне делаем 1 шаг в любой соседний вагон (допустим вагон -1), делаем 3 шага в другую сторону (мы в вагоне +2), теперь в другую 5 шагов и мы в вагоне -3 он же 0, возвращаясь мы обнаружим что в 0 свет погас . Всего 12 шагов

Answer 16

А не надо после каждого увеличения отрезка на единицу проверять? То есть первый раз с попаданием - 1, +1, - 2, +2, - 3, 0

Answer 17

Так вы же идете в 2 стороны по порядку и всегда проходите через 0 вагон

Answer 18

Но это выдаст правильное значение если вагонов нечётное количество

Answer 19

Ну так я про возвращение каждый раз для общего случая

Answer 20

Это у Вас для 10 вагонов с проверкой хождения -1 1 -2 2 получилось 72 прохода?