Сколько комнат в коридоре?

[TimTowdy]

Такое чувство что условие не полное. Иначе задача легко решается за два прохода по всем комнатам.

[mihaild]

Задача действительно не очень сложная. Но ошибки в условиях я пока не вижу. Что значит «за два прохода»?

[FlashXL]

Нет, нельзя за два прохода.

[steck]

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

[steck]

упс, можно не выключать лампочку которая оказалась не в начальной комнате.
В целом это даже более правильно, поскольку приятнее ходить по комнатам с работающим освещением. Но на решение это не повлияет. =)

В итоге у нас будет включен свет везде кроме начальной комнаты. Сосчитать количество комнат не составит проблему. (все включённые плюс один).

[FlashXL]

Ух, у меня алгоритм чуть сложнее, но суть та же в принципе :)

[YasonBy]

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

P.S. Применимо, разумеется, только для небольших значений N :)

[FlashXL]

А еще, если двигаться около скорости света, можно застать тускнеющую нить накаливания :)

[FlashXL]

Как всегда ответ беленьким:
Пусть мы находимся в какой-то комнате и все которые впереди нумеруются +1, +2 и т.д., все сзади -1, -2 и т.д. Идем в комнату +1, инвертируем состояние света. Идем в комнату -1, делаем то же самое. Идем опять в +1 и смотрим, не изменилось ли состояние света. Если изменилось, то количесво комнат — 2. Если не изменилось — идем в комнату +2, инвертируем свет и так далее, пока не заметим, что в комнате с номером m состояние света изменилось с момента нашего последнего визита. И значит комнат N = 2m.

[steck]

У вас небольшой косяк.
Пусть комнаты всего 2.
идём в +1, инвертируем.
идём в -1 (та же комната), инвертируем.
идём в +1, состояние не изменилось, идём в +2…
=)

[mihaild]

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

[FlashXL]

Тут тоже просто — мы же знаем свет в комнате 0 и если мы его изменили в +1, то проходя мимо той же 0 это заметим :)

[FlashXL]

Пусть в +1 свет горит. Идем туда, выключаем. Идем в -1, соответственно включаем, идем обратно в +1 — свет включен, тогда как мы его там явно выключали.

[mihaild]

Ваш способ не работает в случае нечетного числа комнат (что видно по ответу: N=2m). Нужно лишь добавить, что пока идем смотрим не изменилось ли где состояние (точнее, нужно посмотреть на комнаты m-1 и m, а не только m)

[FlashXL]

Да, точно, спасибо!

[hTLK]

<спойлер>
1. включаем свет в текущей комнате
2. идём в одну (любую, но конкретную сторону) до тех пор пока не встретим комнату с включенным светом, при этом считаем сколько комнат прошли
3. выключаем свет в этой комнате
4. возвращаемся в комнату с которой начали (по дороге мы считали сколько комнат прошли)
5. если в комнате в которую вернулись свет горит, то действуем по алгоритму с пункта 2. иначе получается что мы выключили свет в исходной комнате, значит число комнат которое мы прошли и есть искомое N
</спойлер>