Сложненькая загадочка про вагоны

Вагоны соединены в колцо. Тебя запустили пересчитать вагоны. Выпустят только когда пересчитаешь. Вагоны в тунеле, так что картина из окна одна и таже. Вандализм не допустим, двери все самозахлапывающиеся, на тебе нет ничего (так как были варианты оставить одежду в первом вагоне). Вы можете только включать и выключать свет в вагоне. Свет включен в вагонах в произвольном порядке. Как пересчитать? Дерзайте
З.Ы. Считайте, что "произвольный порядок" против вас. Нужен сто процентный метод.

 

Блмн, ну эт точно не для тех, кто с конекта припёрся, и так голова не варит...

 

В том то и проблема. Локоматива нет, а вагоны сцепленны в кольцо.

 

Вагоны все одинаковые полностью.

 

Есть у меня один вариант. Задача встречалась раньше, но тогда не получилось решить, может сейчас удачней будет

Алгоритм хождения по вагонам такой:
1. Включается свет в вагоне, в котором человек очутился путем телепортации.
2. Идем направо, выключаем свет в правом вагоне (запоминаем 1).
3. Идем налево, отсчитываем два, включаем свет в вагоне (запоминаем 2).
4. Идем направо, выключаем свет в третьем по счету вагоне, если перед тем вагоном, в котором должен быть выключен свет, свет включен, то число вагонов равно числу, которое запомнили, иначе просто выключаем свет (запоминаем 3).
5. Идем налево, отсчитываем 4, включаем свет. Если свет в предыдущем вагоне был выключен, то число вагонов равно запомненному числу. (Запоминаем 4)
...
2n. Идем направо, выключаем свет в (2n - 1) по счету вагоне, если перед тем вагоном, в котором должен быть выключен свет, свет включен, то число вагонов равно числу, которое запомнили, иначе просто выключаем свет (запоминаем 2n - 1).
2n+1. Идем налево, отсчитываем 2n, включаем свет. Если свет в предыдущем вагоне был выключен, то число вагонов равно запомненному числу. (Запоминаем 2n)
...
*умираем от холода, голода и невозможности спать без одежды в бесконечном поезде*

 

хорошая попытка! Но ходим по кругу и думаем он бесконечен, так и не посчитав вагоны.

 

алгоритм куда проще, мы решили колективным разумом. Этот вариант тоже был.

 

Нет, не ходим. Круга не получится, так как все вагоны поделены на освещенные или нет, и при заходе на "чужую" половину этот заход будет виден и число вагонов посчитано. Если не так - приведите опровержение, пример бесконечного хождения с использованием этого алгоритма при конечном числе вагонов.

 

Вы заходите на не освещенные вагоны, а там выключеных вагонов столько, сколько вы выключили.

 

Еще понятнее вы включили и выключил по 4 вагона, а дальше включено 4 и выключено 4, как вы определите где финиш.

 

Здесь без разницы, какие вагоны исходные, включенные или выключенные. "Заход" на половину считается по своим уже стопроцентно собственноручно включенным/выключенным вагонам.

з.ы. еще один вариант (похож на предыдущий) - если коротко, то выключается первый вагон, и туда-сюда включается свет, с запоминанием "размаха" (n). Посередине (n/2) всегда должен быть изначальный вагон, если его нет, то число вагонов n/2.

 

А как вы узнаете, что зашли на половину? И как вы узнаете, что вы включили этот вагон.

 

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

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

 

А... Я вас видимо не понял. Правильно, только алгоритм легче: В первом вагоне гасим свет, а дальше идем по включеным, если натыкаемся на выключенный, включаем и проверяем первый.

 

Это хорошо, когда думаешь своей головой или с группой товарищей не нагружая гугл.

 

Хороший алгоритм Но его эффективность (количество шагов) зависит от начальных условий (при самых лучших - то есть все вагоны включены, равна 2*n, а при самых плохих - выключенных 2*(сумма по i от единицы до n) i), а мой стабильный (n + (сумма по i от единицы до n) i)). И если система вагонов такая интеллектуальная, что подбирает включение/выключение в зависимости от типа алгоритма, то вряд ли попадется самый простой вариант

з.ы. Вы, наверное, неправильно меня поняли как раз во второй раз. Имеется не одна серия включенных вагонов, или выключенных, а последовательность, где половина (или на вагон меньше) пройденных вагонов включена подряд, а половина пройденных выключена.

 

Ладно здаюсь. Я слишком пьян, чтоб считать. Решаем следующую? Она по легче.

 

Та задачка решена уже давно была, так что знаю ответ.

 

Могу задать задачку, которую сам не до конца понимаю её решение.