Проект основателей компании «Ваш репетитор»
ERUDITOR.RU

58. Круглый поезд

Несколько вагонов сцеплены между собой по кругу. Внутри ходит машинист, он должен посчитать количество вагонов. Он может только включать или выключать свет в вагонах. Как ему это сделать?
Вначале свет горит случайным образом. Количество вагонов может быть ну очень большим.
Прим. ред.
Отличная задача для собеседования программистов.
2007-07-27

Обсуждение


Задачи :: Круглый поезд
↓↓ 0 ↑↑   Zero (38 / 335)   26 июл 2007 23:19   »»


Хорошая задачка
Я такой вариант придумал:
Машинист выбирает "нулевой" вагон. Зажигает в нём свет (или оставляет зажжённым).
Далее он идёт в определённом направлении от этого вагона (скажем, по часовой стрелке) и считает количество пройденных вагонов до тех пор, пока не встретит первый "зажжённый" вагон. Тогда он гасит в нём свет и идёт обратно, отсчитывая запомненное число, чтобы остановиться точно в нулевом вагоне. Если в нём свет горит -- операция повторяется. Если нет -- то запомненное число и есть искомое количество вагонов.
↓↓ +9 ↑↑   eruditor (133 / 441)   27 июл 2007 05:16   «« #2 »»   Ответить


Так и есть.
↓↓ +4 ↑↑   Zero (38 / 335)   27 июл 2007 16:10   «« #3 »»   Ответить


Интересно, можно ли быстрее.
↓↓ 0 ↑↑   eruditor (133 / 441)   27 июл 2007 17:53   «« #4 »»   Ответить


Вродебы быстрее нельзя..
Ибо пришёл к такому же решению.
↓↓ 0 ↑↑   igar (10 / 119)   31 июл 2007 10:59   «« #5 »»   Ответить


Как?
да но ведь сказано:"Вначале свет горит случайным образом." Как он поймёт, где тот "нулевой" вагон?
↓↓ 0 ↑↑   Sweety (0 / 14)   08 авг 2007 23:57   «« #6 »»   Ответить


Sweety
Нулевой вагон - условное понятие. Его определяешь сам - любой вагон.
↓↓ 0 ↑↑   7777777 (3 / 130)   09 авг 2007 07:27   «« #7 »»   Ответить


да но Свет ведь включен не только в "нулевом"
↓↓ 0 ↑↑   Sweety (0 / 14)   09 авг 2007 19:44   «« #8 »»   Ответить


Sweety
И что? В решение вчитайтесь.
↓↓ 0 ↑↑   7777777 (3 / 130)   10 авг 2007 10:41   «« #9 »»   Ответить


Быстрее можно с парктической точки зрения, учитывая теорию вероятностей, особенно если вагонов действительно очень много. В "нулевом" вагоне включаем свет, в следующих двух выключаем, потом в трех включаем, в четырех выключаем и т.д, при этом считая вагоны. Наткнувшись в конечном итоге на такую последовательность и "проверив" для себя так определенное количество вагонов (совпадает ли), можно сделать вывод об их количестве на основании неполной индукции.
↓↓ 0 ↑↑   7777777 (3 / 130)   10 авг 2007 10:45   «« #10 »»   Ответить


Ууу, нет.
Раз уж учитываете теорию вероятностей, так учитывайте её грамотно.
Есть такая теорема, которая, в частности, говорит:
Если записать случайное число в виде десятичной (бесконечной) дроби, то ЛЮБАЯ сколь угодно длинная заранее заданная последовательность цифр встретится в этой записи БЕСКОНЕЧНОЕ число раз.
↓↓ 0 ↑↑   eruditor (133 / 441)   10 авг 2007 15:00   «« #11 »»   Ответить


eruditor
Акцент был на "практической" :) Иначе и ваше решение не имеет смысла, если число вагонов устремить к бесконечности.
↓↓ 0 ↑↑   7777777 (3 / 130)   10 авг 2007 15:53   «« #12 »»   Ответить


Моё решение имеет смысл при любом числе вагонов.

С практической точки зрения, вы никогда, принципиально, не ответите на вопрос чему равно это ваше "определённое" количество, которое нужно проверить.
↓↓ 0 ↑↑   eruditor (133 / 441)   11 авг 2007 14:34   «« #13 »»   Ответить


eruditor
Метод неполной индукции на практике имеет куда большее значение часто, чем та же теория вероятностей. :)
↓↓ 0 ↑↑   7777777 (3 / 130)   16 авг 2007 09:02   «« #14 »»   Ответить


Меня одного плющит? или как?
Похоже Sweety в такой же прострации ... "до тех пор, пока не встретит первый "зажжённый" вагон" - мне интерес принцип (свойство) по которому машинист определит что это "нулевой" вагон", если он его помнит по каким-то другим признакам, то вообще ему этот свет и не нужен !!! Поясните решение для особо непонятливых.
↓↓ 0 ↑↑   acogitas (0 / 10)   25 авг 2007 12:48   «« #15 »»   Ответить


Специально "для особо непонятливых"...
ВНИМАТЕЛЬНО прочитайте решение. Там все очень подробно расписано.

Если не поможет, нарисуйте для наглядности схему поезда и ЕЩЁ раз прочитайте...
↓↓ +4 ↑↑   Zero (38 / 335)   26 авг 2007 22:29   «« #16 »»   Ответить


Уточнение решения
Машинист не знает даже примерного количества вагонов, сколько их, 10, 100, 1000? Для того, чтобы создать "настоящую" точку отсчета, точнее вагон, необходимо сделать её уникальной. А правильнее - исключить теорию вероятностей и построить математическую последовательность. Например, выбираем условно "нулевой" вагон, оставляем в нем зажженным свет, в следующем втором вагоне свет выключаем (1), в третьем свет включаем, в четвером и пятом выключаем (2), в шестом включаем, в седьмом, восьмом и девятом (3) выключаем и т.д. При этом ведем счет вагонов. Как только добрались до построенной нами последовательности, отсчет заканчиваем.
↓↓ 0 ↑↑   LuciFerrum (0 / 3)   18 окт 2007 21:26   «« #17 »»   Ответить


"Как только добрались до построенной нами последовательности"?..
Опишите поточней, что это за момент.
↓↓ 0 ↑↑   eruditor (133 / 441)   19 окт 2007 14:39   «« #18 »»   Ответить


уточняю
добрались до вагона со светом, после которого свет не горит, потом горит и т.д. можно даже еще разик пройтись, сомневаюсь, что получится случайность, когда на определенном этапе мы встретим не нашу последовательность, но такую же. Тогда для верности можно построить поледовательность по другому принцыпу. Важно не выключить свет в вагоне с точкой отсчета, хотя понять это можно и вернуть все на место, сделав шаги назад.
↓↓ 0 ↑↑   LuciFerrum (0 / 3)   19 окт 2007 22:43   «« #19 »»   Ответить


а разрешима ли эта задача в принципе?
если да, то машинисту достаточно посмотреть в окно во внутрь "кольца", образованного поездом и посчитать видимое количество вагонов. А затем включить свет в одном вагоне и двинуться, например, по ходу часовой стрелки, выключая свет в нескольких вагонах по ходу (количество зависит от длины поезда, ее можно приблизительно определить выглянув внутрь "кольца"). После этого следует включить свет еще в одном вагоне, запомнив количество вагонов без света. С противоположной стороны, увидев соответствующее количество выключенных вагонов между двумя включенными, он поймет, что прошел приблизительно половину. Тогда нужно посмотреть, сколько включенных и выключенных вагонов находится перед "отмеченным" (слева от него), и, когда он наткнется на эту последовательность, дойти до нужного вагона не составит труда. Таким образом, если IQ машиниста не ниже среднего уровня и количество вагонов не является художественным вымыслом писателя-фантаста (т.е. задача разрешима в принципе), то ее решение не вызывает особых затруднений, напротив, разминка для серого вещества вызывает ощущения весьма приятные.
↓↓ 0 ↑↑   stahanov (0 / 2)   02 ноя 2007 14:50   «« #20 »»   Ответить


был бы поезд, за точку отсчета взял бы машинное отделение :о)
↓↓ 0 ↑↑   LuciFerrum (0 / 3)   04 ноя 2007 17:52   «« #21 »»   Ответить


у меня есть еще вариант, правда тоже долгий, но верный
Нужно выбрать условный нулевой вагон(предположим свет там горит). Далее двигаться от него сначала вправо на 1 вагон и включить там свет(или оставить включенным), вернуться в нулевой (просто отсчитав один вагон назад) - и пойти влево на 1 вагон, там свет оставить выключенным. Потом точно так же, только проходить уже по 2, по 3 и так далее вагонов туда и обратно, каждый раз начиная отсчет с нулевого. Предположим, там 10 вагонов, не считая нулевого. Тогда машинист включив свет в шестом вагоне справа, вернется в нулевой, пойдёт отсчитывать шесть вагонов налево, и окажется, что свет включен в пятом вагоне, то есть в том, где он его однажды его уже выключал. Значит, вагонов 10+нулевой. Если без нулевого число вагонов нечетное, всё будет так же, только машинист наоборот увидит выключенный свет там, где он его уже включал.
↓↓ 0 ↑↑   lynx (0 / 2)   11 дек 2007 19:01   «« #22 »»   Ответить


???
а нельзя сначала выключить везде свет, а потом по одному включать таким образом считая?
↓↓ 0 ↑↑   Kelly (0 / 2)   25 дек 2007 22:11   «« #23 »»   Ответить


можно совместить решение eruditor'a и lynx
тогда будет немного быстрее.
Нужно выбрать условный нулевой вагон(предположим свет там горит). Далее двигаться от него сначала вправо на 1 вагон и включить там свет(или оставить включенным) - вот тут первое изменение - мы идем вправо пока не встретим вагон без света(пусть он n-нный). Затем включаем в нем свет, также возвращаемся до 0 вагона и идем влево пока не встретим вагон с включенным светом(k-тый вагон). идем опять вправо на n вагонов а потом еще направо пока не встретим вагон без света ну и т.д. по решению lynx
↓↓ 0 ↑↑   HeKTo2 (0 / 27)   28 дек 2007 18:15   «« #24 »»   Ответить


пропустил
после "встретим вагон с включенным светом(k-тый вагон)" - возвращаемся к 0 вагону а потом только идем вправо на n вагонов
↓↓ 0 ↑↑   HeKTo2 (0 / 27)   28 дек 2007 18:16   «« #25 »»   Ответить


to Kelly
нельзя никак определить что мы выключлили свет "везде" так как неизвестно количество вагонов. на все рассуждения типа "ну возьмем большое число например 1000 и выключим свет у тысячи вагонов" можно ответить - "а если вагонов больше 1000?"
↓↓ 0 ↑↑   HeKTo2 (0 / 27)   28 дек 2007 18:18   «« #26 »»   Ответить


Fibonacci, все мы так рады, что вы поделились с нами этой новостью.
↓↓ 0 ↑↑   eruditor (133 / 441)   28 янв 2008 08:01   «« #27 »»   Ответить


по-моему можно чуть проще
нужно дойти до первого вагона, в котором горит свет, посчитать его как №1 и исходя из этого уже считать остальные вагоны, по пути выключая свет в остальных вагонах. Для удобства можно включать свет после каждого 10-го вагона.
↓↓ 0 ↑↑   Basta (0 / 1)   15 фев 2008 00:44   «« #28 »»   Ответить


2 Basta
так можно невзначай выключить и вагон №1
↓↓ 0 ↑↑   kiriw (0 / 2)   13 мар 2008 17:08   «« #29 »»   Ответить


ларчик просто открывался
а что мешает сделать следующее:
1) вырубить везде свет
2) выбрать любой вагон и там его включить
3) посчитать вагоны, двигаясь в любую сторону, пока не наткнется на горящий вагон
↓↓ 0 ↑↑   kiriw (0 / 2)   13 мар 2008 17:10   «« #30 »»   Ответить


ларчик просто открывался
А как можно узнать, что свет вырублен ВЕЗДЕ? Число вагонов бесконечно.
↓↓ 0 ↑↑   7777777 (3 / 130)   13 мар 2008 19:25   «« #31 »»   Ответить


А как можно посчитать вагоны, если их бесконечно? ХD
↓↓ 0 ↑↑   Алексей (10 / 18)   31 июл 2017 21:23   «« #56 »»   Ответить


Еще решение
шаг 0) Включаем свет в вагоне, в котором находимся, и считаем его нулевым.
шаг 1) Присваиваем i=1 и далее в каждый момент помним текущее значение i.
шаг 2) Идем сначала на i вагон вперед и выключаем там свет.
шаг 3) Возвращаемся в нулевой вагон (помня i - на сколько вагонов нужно вернуться) - свет должен гореть.
шаг 4) Идем на i вагон назад и выключаем там свет. считаем сколько вагонов прошли.
шаг 5) Возвращаемся в нулевой вагон (помня i - на сколько вагонов нужно вернуться) - свет должен гореть.
шаг 6) i=i+1, идем на шаг 2.

Если при прохождении алгортима мы вернулись в нулевой вагон, а там свет не горит - то СТОП!!!! количество вагонов в поезде = i

Долго, но можно вместо машиниста компьютер пустить, ему все равно, он железный :-)
Хотя, может еще лампочка перегореть :-)
↓↓ 0 ↑↑   Матвей (0 / 1)   02 апр 2008 16:07   «« #32 »»   Ответить


Написано до тебя уже давно! Читай посты других участников!!!
↓↓ 0 ↑↑   Enclave (3 / 140)   02 апр 2008 17:24   «« #33 »»   Ответить


2 //7777777 Число вагонов бесконечно
Тогда как их можно посчитать ?
↓↓ 0 ↑↑   davchik (0 / 3)   11 апр 2008 18:34   «« #34 »»   Ответить


Практическое (варварское)решение
Бьем лампочку или ломаем выключатель в 0-м вагоне и - вперед!
↓↓ 0 ↑↑   anikitin (0 / 1)   19 апр 2008 05:33   «« #35 »»   Ответить


а может...
находим первый вагон без света и начинаем считать со следующего вагона включая в каждом свет....при этом при встрече каждой новой группы вагонов со светом запоминаем посчитанное кол-во и начинаем считать вагоны со светом.. если встречаем вагон без света прибавляем число в уме и только посчитанное и счатаем дальше...количеством вагонов будет число в уме и так до бесконечности пока машинист не состариться и не умрет.... или чубайс свет не вырубит
↓↓ 0 ↑↑   erty (0 / 2)   25 апр 2008 12:12   «« #36 »»   Ответить


Принципы решения
Решений может быть несколько, но есть общие принципы, на которых они построены:
1. При первом проходе по составу машинист никогда не может надежно определить, прошел он уже стартовый вагон или еще нет. При этом машинист не может точно полагаться на оставленную в одном или нескольких вагонах сигнатуру (например, 5 вагонов с включенным светом), поскольку состав может быть большим и в нем любая сигнатура неоднократно может встретиться по теории вероятности. Но оставить сигнатуру в начале состава все равно необходимо, поскольку машинист должен как-то предположить, что в этой части он уже был, чтобы не бегать по кольцу до бесконечности.
2.Допустим машинист идет по составу и предположил, что некоторый вагон является стартовым (совпала сигнатура, в том числе, свет в этом вагоне). 100% способ для машиниста проверить, что он уже был в этом вагоне, состоит в том, что он должен переключить в этом вагоне свет (включить, если выключен и выключить, если включен), вернуться назад - в вагон, который, по его мнению, тот же самый, и увидеть - переключен там свет или нет. Если свет переключен, то он нашел дошел до стартового вагона и знает общее число вагонов в составе. Если свет не переключен, то нужно продолжать поиск сигнатуры
↓↓ 0 ↑↑   Слоняра (0 / 2)   03 июл 2008 11:11   «« #37 »»   Ответить


Рещение есть. приблизительное... но не сложное.
Проводнику нужно лишь выглянуть в окно из вагона при выключенном свете(так просто лучше видно) и на вскидку прикинуть примерное расстояние до вагонов напротив. так как вагонов очень много отклонение от перпендикулярности полученного таким образом диаметра круга бужет невелико и им можно будет пренебречь. Зная диаметр мы можем вычислить длину окружности. и разделив ее на длинну вагона (а она стандартна) получим их количество.
↓↓ 0 ↑↑   BuBBa (1 / 12)   18 ноя 2008 19:00   «« #38 »»   Ответить


В таком случае все зависит от точности глазомера проводника
↓↓ 0 ↑↑   BuBBa (1 / 12)   18 ноя 2008 19:02   «« #39 »»   Ответить


2BuBBa
По моему чистой воды бред.
>>так как вагонов очень много,
то можно и не увидеть "вагонов напротив".
↓↓ 0 ↑↑   igar (10 / 119)   19 ноя 2008 18:19   «« #40 »»   Ответить


2 igar
Ты можеш представить себе такой поезд? Я нет. Но даже в этом случае длина поезда строго ограничено 44 тысячами километрами и даже в ЭТОМ случае число вагонов будет конечна. Не доводите до абсурда задачу. если вагонов напротив невидно(?) то как можно узнать что поезд сцеплен покругу? принять наверу? нет...
↓↓ 0 ↑↑   BuBBa (1 / 12)   20 ноя 2008 18:49   «« #41 »»   Ответить


Странная задача!?
Похоже эта задача не имеет решения.Т.к. кол-во вагонов может быть сколь угодно большим, то
какую бы последовательность из конечного числа включенных и выключенных вагонов вы не создавали в начале отсчёта точно такая же встретится вам далее просто в соответствии с теорией вероятности и вы будете считать что прошли круг, а это может быть не так!
↓↓ 0 ↑↑   total (-4 / 9)   17 фев 2009 20:32   «« #42 »»   Ответить


total
Может, вы удосужитесь прочитать написанное выше, прежде чем писать что-то своё?
↓↓ 0 ↑↑   eruditor (133 / 441)   18 фев 2009 03:27   «« #43 »»   Ответить


Без заморочек
Машинист может оставить какую-либо свою вещь в нулевом вагоне, а затем идти и считать вагоны, пока не наткнется на оставленную вещь!
↓↓ 0 ↑↑   erray (0 / 1)   21 ноя 2010 18:36   «« #44 »»   Ответить


Все проще
При первом проходе везде включать свет. При втором в одном из вагонов свет выключить и считать вагоны пока не наткнется на вагон с выключенным светом.
↓↓ 0 ↑↑   злостный Beaver (0 / 5)   27 дек 2010 20:25   «« #45 »»   Ответить


Beaver прав)
либо сначало включить либо выключить во всех свет, затем выбрать один и изменить в нем состояние лампы, соответственно от него и вести отсчет
↓↓ 0 ↑↑   Dimqe (0 / 19)   15 май 2011 12:46   «« #46 »»   Ответить


Тактика следующая:
1. В начальном вагоне выключаем свет (нулевой вагон).
2. Идем вправо до тех пор пока не встретим вагон с выключенным светом (обозначим как N-ый вагон) и включаем свет.
3. Идем влево до нулевого вагона. Если вагон включен, значит всего N вагонов. Если нулевой вагон выключен, то следующий шаг.
4. Идем влево от нулевого вагона и включаем свет везде, пока не встретим N-ое количество включенных вагонов подряд (т.к. справа от нулевого вагона есть N-ое количество включенных вагонов).
5. Идем дальше пока не встретим выключенный вагон. Включаем его. Запомнили сколько теперь вагонов прошли слева, обозначаем как N-ое количество.
6. Повторяем шаги с 3 по 5 только в другую сторону. И так далее вправо-влево-вправо-влево. Пока не найдем точное количество вагонов.
↓↓ 0 ↑↑   Андрей (3 / 9)   08 апр 2013 16:10   «« #47 »»   Ответить


Можно усовершенствовать предыдущий способ. Когда включаешь свет в N-ом вагоне и собираешься возвращаться к нулевому вагону, то можно проверить (N+1)-ый вагон.
А. Если он выключен как и N-ый вагон и зная что с другой стороны нулевого вагона свет должен быть включен, то можно не возвращаться до нулевого вагона, а идти дальше, начав отчет "N-ых включенных вагонов с другой стороны" заново.
Б. Если вагон включен. То возвращаемся к нулевому вагону. Если он выключен, то идем дальше включая свет в вагонах до тех пор пока не встретим N-ое количество подряд включенных вагонов, где (N+1)-ый вагон выключен.
↓↓ 0 ↑↑   Андрей (3 / 9)   08 апр 2013 16:21   «« #48 »»   Ответить


Можно посто пройти включая свет во вссех вагонах:-)
↓↓ −5 ↑↑   виктор (-14 / 3)   08 ноя 2013 11:41   «« #49 »»   Ответить


И как ты определишь что включил свет уже во всех вагонах и дальше по пути нет вагонов с выключенным светом?
↓↓ +5 ↑↑   Дмитрий (5 / 4)   22 ноя 2013 15:33   «« #50 »»   Ответить


Если вагонов не много. Просто выключить свет, и идти считать вагоны, пока в выключенном вагоне не попадутся теплые лампочки:)
↓↓ 0 ↑↑   Николай (0 / 1)   10 июл 2015 11:49   «« #51 »»   Ответить


Я бы сломал выключатель, либо зафиксировал его в среднем положении. Затем просто надо идти и включать свет считая , чтобы не споткнуться)
↓↓ −5 ↑↑   Владимир (-5 / 1)   21 фев 2016 15:38   «« #52 »»   Ответить


Есть два варианта с вагонами, их либо чётное количество либо нечётное.
Итак, считаем вагоны группами по два и маркируем 1-свет есть, 0-света нет (например в первом нет света в следующем есть — 01)
Например: 11/01/10/10/10/1 — это поезд с 11 вагонами. При последовательном прохождении мы получим устойчивый сигнал вида 31222323111 — этот сигнал пришёл с "шумом", т.к количество цифр в нём нечётное, а следовательно это и есть количество элементов, т.е 11. В случае если сигнал без шума (чётное количество вагонов) — например группа 11/01/10/10/10 выдаёт сигнал 31222 — то сложив полученные цифры получим 10 вагонов. Следует помнить, что мы считаем физические объекты, а значит наличие 0 в сигнале без шума — это 2 (2-а вагона без света). Задача решена в два линейных прохода 1 массивом.
↓↓ 0 ↑↑   Alex (0 / 1)   28 июн 2016 15:45   «« #53 »»   Ответить


Что за «устойчивый сигнал» такой? Повторяющийся? Никакое количество повторений одной и той же последовательности не даёт гарантий, что эта последовательность будет повторяться и далее.
↓↓ 0 ↑↑   Кузнецов Сергей Германович (267209 / 13856)   29 июн 2016 02:16   «« #54 »»   Ответить


1. Противоречие в задаче:
Несколько вагонов сцеплены между собой по кругу. Количество вагонов может быть ну очень большим.
2. Внимательно читаем вопрос:
Он может только включать или выключать свет в вагонах. Как ему это сделать?
Ответ: Включить свет или выключить свет включателем!
↓↓ −5 ↑↑   Вячеслав Николаевич (-5 / 1)   06 фев 2017 21:41   «« #55 »»   Ответить


Я придумал более быстрое решение. Не n * n переходов, а только 5 * n (или меньше)

// Initialising
int i, n = 1;
boolean direction = true;
Turn lihgt off

// Loop starts
while (true) {

// Turn n lamps off and one on
for (i = 0; i <= n; i++) {
moveTo(train, direction);
Turn lihgt off
}
Turn lihgt on

// Change direction
direction = !direction;

// Double n
n <<= 1;
System.out.println("I check light in " + n + " carriages in " + (direction?"right":"left") + " direction");

// Check for light in the n carriages
for (i = 1; i <= n; i++) {
moveTo(train, direction);
If lihgt is on then break (exit from loop)
}

// Loop ends
if (i < n) break;
}

// Show the results
System.out.println("I think, the number of carriages is " + i);
↓↓ 0 ↑↑   ivan-kyiv (0 / 1)   04 окт 2017 15:03   «« #57 »»   Ответить


Я так понимаю, отличие от варианта #2 в том, чтобы ходить туда-сюда не до первого встреченного вагона, а забегами по [m]2^n[/m] вагонов? Но насколько оно быстрее, зависит от того, как изначально включен свет. Если весь поезд тёмный, то решение #2 найдёт ответ всего за один проход туда-сюда.
↓↓ 0 ↑↑   Кузнецов Сергей Германович (267209 / 13856)   06 окт 2017 11:21   «« #58 »»   Ответить


Что если…
1 включить свет в первом, К = 1.
2. Доходим до К — того вагона (считая от нулевой точки, включая первый вагон) с включенным светом, попутно включая свет в выключенных К вагонах.
3. Идем дальше и отсчитываем К включенных (без нас) вагонов — если таковых не насчитывается и мы встречаем выключенный свет, то это не наша комбинация, включаем свет и повторяем с пункта 2. Если же мы насчитали К включенных (без нас) вагонов, выключаем в последнем (N = 2К -том вагоне) свет и возвращаемся к К-тому вагону и проверяем его. Если он выключен — то вагонов в кольце К, если включен, то возвращаемся к 2К-тому вагону и повторяем пункт 2. Размер проходов вперед будут расти минимум в прогрессии 2 степнь М, где М — число проходов вперед, в худшем варианте включенного света во всех вагонах. Возвращаться для проверки мы будем только на половину уже пройденного пути.
↓↓ 0 ↑↑   Александр Орлов (0 / 1)   13 ноя 2017 12:27   «« #59   Ответить



Ваше имя
Email
Текст ответа
© 2006-2017   Авторы