Растолкуйте мне задачку про циклический поезд...

[Sun]

При N=12, нумерация вагонов начинается с 0.
2^4=(3+1)*2^2=12+2^2 - попадаем в 4й вагон
2^5=(3+1)*2^3=12*2+2^3 - 8й вагон
2^6=(3+1)*2^4=12*2^2+2^4=12*2^2+12+2^2=12(2^2+1)+2 ^2 - 4й вагон
2^7=(3+1)*2^5=12*2^3+2^5=12*2^3+12*2+2^3=12(2^3+2) +2^3 - 8й вагон
и т.д., согласно принципу индукции, шагая по степеням двойки, мы всегда будем попадать либо в 4й либо в 8й вагон. И чего нам это даст? Или я не так вас поняла?

[Jabo]

П2. Проходишь ещё раз и контролируешь естественно при бесконечном количестве вагонов задача не имеет решения.
ЗЫ: Можно конечно насрать в одном из вагонов, а потом найти - самый быстрый стопроцентный результат.

[HiLuxSurfer]

кстати! срать не запрещено по условиям задачи....

[GaXX]

по пути выключаем лампы в каждом вагоне, соответственно на шаге N все лампы будут выключены (и в 0 вагоне тоже) -> значит мы пошли по кругу -> возвращаемся назад в 0 вагон, включаем лампу -> идём на 2^(N-1) вагонов вперёд и дальше последовательно до горящей лампочки -> бинго!

[Lex]

при бесконечном количестве вагонов
насрать в одном из вагонов

не получится, приспичит еще не раз ))

[Sun]

По-вашему на каком шаге надо возвращаться в 0 вагон?

[GaXX]

на каждом

[Sun]

Ок. N=12. На четвертом шаге выключили все лампочки до 8 вагона, кроме нулевой. На пятом мы проходим нулевой вагон, но мы этого не знаем, т.к. не знаем, что N=12. Гасим лампочку в нулевом вагоне и, по вашему алгоритму, далее до 4го вагона (по нашему линейному счету 16-го) - и возвращаемся на 16 вагонов назад. Света нет - вывод - количество вагонов 16? Или 15? Или сколько от 8 до 16?

[GaXX]

На 5 шаге мы гасим лампу в 0 вагоне (не зная что он 0) -> возвращаемся назад на 16 шагов в 0 вагон -> видим что лампа погашена -> включаем её -> идем на 2^4=8 шагов и еще 4 шага до включённой лампы -> 0 вагон найден -> кол-во вагонов равно 8 + 4 == 12

[Sun]

поняла, спасибо

[Sun]

оптимизация 1: переходим от N^2 к (log N / m + N) - каждый следующий шаг длиннее предыдущего в m раз
оптимизация 2: как 1, но если лампа в вагоне не горит, то повторяем шаг. но здесь я чёт пока не соображу какая сложность получается

если точнее, то наверное так: если по пути не встретилось ни одной горящей лампы - повторяем шаг - да?
А сложность, если в исходном состоянии все лампы горят, будет такая же.
А если все выключены - 2*N - туда и обратно

[Jabo]

можно насрать и спрятать

[forvard]

Вася, проснись

[Jabo]

этож не баня а вагоны

[Jaguar-nn]

Тоже думал про точку отсчета типа включать везде свет и т.д. Но ведь действительно если не знаешь сколько вагонов ты по ним топаешь и вроде как ахулиард подряд включенных лампочек, ты типа останавливаешься и говоришь в поезде ахулиард вагонов, а оказалось в ахулиард+1 вагоне до которого недошел свет выключен.
Так вот задача намного проще чем кажется: надо дойти до локомотива и отсчитывать от него!

[axel]

все проще: в самом первом вагоне где респаунились пишем на стене "***" и идем до вагона ресторана.. лампочки можно не включать и не выключать, на это есть проводник.. если ресторана-вагона не находим, а метка х попадается снова, то вспоминаем сколько прошли вагонов.. и грустим.. пива то не попить.