+ 2

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

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

5th Feb 2020, 8:10 PM
Kosarevsky Dmitry
Kosarevsky Dmitry - avatar
74 Antworten
+ 5
Сначала все сделать выключенными, потом включить первый и считать сколько прошли
6th Feb 2020, 10:56 AM
sankot
sankot - avatar
+ 4
Если уж не нравится критерий достаточно долго, можно тогда попробовать следующим образом: вагон в котором мы находимся 0й и в нем мы включаем свет, двигаемся в одном выбранном направлении, считая вагоны, пока не встретим вагон со включенным светом, выключаем его и возвращаемся назад в 0й вагон(мы знаем где он, тк считаем вагоны при перемещении). Продолжаем до тех пор пока в 0м вагоне не погаснет свет, это будет значить что мы обошли весь поезд. Но я чет туплю и не могу оценить сложность алгоритма, O(n^2)?
7th Feb 2020, 6:00 AM
sankot
sankot - avatar
+ 4
Мы их считаем КАЖДЫЙ раз, и в 0м горит свет пока круг не замкнется
7th Feb 2020, 6:04 AM
sankot
sankot - avatar
+ 3
Можно включить свет в 0м вагоне, а затем ходить влево и вправо на одинаковое расстояние при этом выключая свет и ведя подсчет вагонов. На каком-то этапе мы выключим свет в 0 вагоне.
7th Feb 2020, 6:26 AM
Сергей Котко
Сергей Котко - avatar
+ 3
Если будет четное, то на последнем этапе, находясь в 0 вагоне, зажечь свет и сделать 1 проход в ту же сторону но уже на n-1 шагов
7th Feb 2020, 8:28 AM
Сергей Котко
Сергей Котко - avatar
+ 3
Да👍. Намного быстрее в 1 сторону с возвращением и проверкой в 0 вагоне.
7th Feb 2020, 10:04 AM
Сергей Котко
Сергей Котко - avatar
+ 2
Смотрите, другая идея посетила, а что есть нам весь поезд "отформатировать" чередованием вкл-выкл-вкл-выкл....? Тогда в определенный момент при четном количестве вагонов при прохождении поезда нам больше не придется переключать свет, тогда потребуется поставить маркет отсчета (думаем как). При нечетном количестве вагонов начало отсчета само себя укажет, там 2 соседних вагона всегда будут с одним и тем же состоянием света... Как минимум нужно будет несколько раз пройти по всему поезду.
6th Feb 2020, 10:39 AM
Алексей Ермаков
Алексей Ермаков - avatar
+ 2
Просили посчитать количество вагонов, можно конечно карту составлять, и когда шифр полностью повторится мы узнаем количество, но это не гарантированно, потому что мы точно не знаем были ли здесь или нет. Мне кажется рациональней переключить все состряния в одно(любое) ну и условие что мы не встречали вагоны в другом состоянии достаточно долго, и тогда начать отсчет, для верности можно переключить не один вагон, а допустим 11, вероятность встретить переключенными 11 вагонов уже довольно мала
6th Feb 2020, 11:09 AM
sankot
sankot - avatar
+ 2
Хоть это решение и полное с точки зрения алгоритма, мне оно не нравится, мне кажется можно сделать проще и быстрее(как бы идея не поменялась, хочу все сделать выключенными, только буду не просто все гасить, а гасить и считать сразу, мне кажется количество операций возрасло просто непомерно, для относительно небольших н(до 1000) это слишком медленно)
7th Feb 2020, 6:19 AM
sankot
sankot - avatar
+ 2
Итераций будет много, да, но этот способ надёжный. Количество проходов будет всего n*2, где n - количество вагонов
7th Feb 2020, 6:25 AM
Алексей Ермаков
Алексей Ермаков - avatar
+ 2
С прохождением в 1 сторону есть тоже возможность что ты наткнешься на точно такую же маркировку, вероятность возрастает при увеличении числа вагонов
7th Feb 2020, 6:50 AM
Сергей Котко
Сергей Котко - avatar
+ 2
Поправьте, если я считаю не правильно, но количество пройденных вагонов в худшем случае(если все включены) получается сумма по k = 0 до n - 1, от произведения (2k+1)(n-k), что даем весьма не утешительные результаты, так для 10 вагонов мы пройдём 385 вагонов, что даже не n^2
7th Feb 2020, 7:30 AM
sankot
sankot - avatar
+ 2
А нет, я дважды учла переход(зря влезла в общий вид, отвлеклась и не то написала), все ок там примерно 2n+n^2 должно быть
7th Feb 2020, 8:02 AM
sankot
sankot - avatar
+ 2
Надо было расписывать снизу вверх, так для 10 вагонов получается 21(последний круг) 19 (туда - обратно для 10 вагонов), 17 для 9... 3 для 2х, и 120 всего
7th Feb 2020, 8:07 AM
sankot
sankot - avatar
+ 2
Хорошо, а если рассмотреть на примере 5 вагонов. Находясь в 0м вагоне делаем 1 шаг в любой соседний вагон (допустим вагон -1), делаем 3 шага в другую сторону (мы в вагоне +2), теперь в другую 5 шагов и мы в вагоне -3 он же 0, возвращаясь мы обнаружим что в 0 свет погас . Всего 12 шагов
7th Feb 2020, 8:20 AM
Сергей Котко
Сергей Котко - avatar
+ 2
А не надо после каждого увеличения отрезка на единицу проверять? То есть первый раз с попаданием - 1, +1, - 2, +2, - 3, 0
7th Feb 2020, 8:22 AM
sankot
sankot - avatar
+ 2
Так вы же идете в 2 стороны по порядку и всегда проходите через 0 вагон
7th Feb 2020, 8:24 AM
Сергей Котко
Сергей Котко - avatar
+ 2
Но это выдаст правильное значение если вагонов нечётное количество
7th Feb 2020, 8:25 AM
Сергей Котко
Сергей Котко - avatar
+ 2
Ну так я про возвращение каждый раз для общего случая
7th Feb 2020, 8:27 AM
sankot
sankot - avatar
+ 2
Это у Вас для 10 вагонов с проверкой хождения -1 1 -2 2 получилось 72 прохода?
7th Feb 2020, 8:44 AM
Сергей Котко
Сергей Котко - avatar