задачо про вагоны метро

[santadambri]

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

Comments

[anonymous]

[santadambri]

ну крута.

[yakness]

это всё потому что я крутой.

[:]/\/\/\/\[:]

[gkuznets]

Грубо говоря, дан дек с обычными четырьмя операциями push_back, push_front, pop_back, pop_front. Нужно определить количество элементов в деке и оставить его в исходном состоянии.
Решение этой задачи можно найти, например, в книжке Шеня "Программирование. Теоремы и задачи."

[ghavr]

Фишка в том, что "ты" далеко не первый "ты" который там ходил. И надписей таких в каждом вагоне примерно сто тыщ миллионов. Ты написал и не можешь ответить - твоя ли надпись встретилась ещё раз или нет. Может быть (задолго) перед тобой прошёл чел, который идеально знает твои привычки и ход мыслей... он взял и баааальшой кусок состава изгафнякал так, как это сделал бы ты сам. Вот ходишь и думаешь...

[ghavr]

Не) Он когда-то жизнь остальным подпортил, а потом выпрыгнул из чудо-поезда)

[4ucha]

включить везде свет и в одном вагоне выключить и пошёл-пошёл гулять и считать :)

[naddinp]

непонятно, что значит "включить свет везде" - нужно определить, что значит везде.
пусть в первом вагоне свет включен
идем в положительную сторону. если в k-м вагоне свет также включен, выключаем, возвращаемся в 1й - смотрим, изменилось/нет. если изменилось - k-1. Если нет - ищем первый вагон с включенным светом > k

[santadambri]

:)