Вагоны поезда образуют кольцо, в каждом вагоне - лампочка которую можно включать или выключать, изначальное состояние лампочек - произвольно. Как посчитать количество вагонов?
Bump.
Bump.
Bump.
Включаешь одну лампочку, потом следующую через одну, пятую - отключаешь. Вот тебе и количество вагонов.
Bump.
Bump.
Bump.
Bump.
Ходишь вдоль сраных вагонов, говоришь: "Раз" и помечаешь вагон мелом, ставишь на нём крестик или рисуешь хуй. Идёшь в следующий.
У меня есть решение, которое для N вагонов требует порядка O(N²) шагов. Есть что-нибудь лучше?
Пиздуешь вдоль них и считаешь пиздюк, бумажку с карандашом возми чтоб на обратном пути не забыть сколько получились. Пиздец ты нулевой.
?
Bump.
>Как посчитать количество вагонов?
Насрать в одном из вагонов дабы отметить его. Потом по кругу пойти и посчитать.
Если всего вагонов N, то моё решение потребует сделать N * (N + 1) шагов (переходов из одного вагона в другой).
Что за решение?
Выкручивать лампочки по очереди
/тред
Ебешь мамашу опа в тамбуре
Bump.
Bump.
Bump.
Допустим, мы думаем, что всего вагонов K. Чтобы убедиться в этом, сделаем следующее: запомним, в каком состоянии лампочка в текущем вагоне. Сделаем K шагов вправо, если мы попали в вагон с лампочкой в другом состоянии, то значит предположение неверно. Если же состояние такое же, то поменяем его и сделаем K шагов влево. Если теперь и в первоначальном вагоне состояние лампочки поменялось, значит предположение было верным.
Так можно для любого K проверить, является ли оно ответом (ну, на самом деле, не совсем — если ответ N, то для K = 2N это даст false positive, но главное, что ответ для любого K < N отрицателен), так что можем перебрать K от 1 до бесконечности, пока не получим первый положительный ответ. Несложно показать, что шагов будет N * (N + 1).
- Дети, на дереве сидели три птицы. Одна ворона и два воробья. Вопрос: сколько мне лет?
- 50!
- Молодец, а теперь расскажи, как ты решил эту задачу.
- Да у меня сосед наполовину долбоеб, так вот ему 25.
Есть менее громоздкое решение.
Берешь и считаешь, хули сложного-то?
Bump.
выключаешь все лампочки, потом включаешь по одной
Как ты поймёшь, что выключил все?
конечно это не 100% способ, т.к. мы не знаем длина вагона может быть бесконечной но 99.99999%. для уверенности можно можно сделать много кругов
1. Идти и записывать вкл или выкл лампочка сверяясь с предыдущими записями.
2. Последовательность начала повторяться? Считаем число вагонов. И придумываем новую, свою последовательность.
3. Повторяем путь включая-выключая олампочки согласно заданной последовательности.
4. Пару кругов для проверки.
5. PROFIT.
Придумал за O(N log N), но описывать лень. Идея такая же, но суть в том, что, два раза выходя из одной точки на K единиц вправо и назад (с разными состояниями лампочки в начальной точке), можно узнать, верно ли, что K < N, а если это неверно, то сразу точно определить K = N, поэтому можно в качестве K использовать 1, 2, 4, 8, ...
Оставить включенной первую лампочку
В принцыпе, можно пропустить первый шаг, но тогда надо придумать последовательность с определенной закономерностью, но неограниченную длиной.
кун
Длина не может быть бесконечно, это в условии сказано.
Шаг 1. Выкручиваешь лампочку в том вагоне, с которого начинаешь отсчёт.
Шаг 2. Идёшь и считаешь все включенные и выключенные лампочки.
Шаг 3. Натыкаясь а открученную лампочку, заканчивает считать и подводишь итог.
>то сразу точно определить N
слоуфикс
>лампочка которую можно включать или выключать
Пролетишь мимо начальной точки.
Ой иди нахуй.
Bump.
В том-то и прикол, что если дважды выходить из начальной на K вправо и сразу возвращаться (с разным состоянием начальной), то, если K > N, то на втором заходе будет легко определить, где начальная точка (потому что её состояние будет отличаться от её состояния в первом заходе).
То что её можно включать, а можно и не включать, не остановаит меня от выкручивания оной. И вообще, тебе нужна эффективность или что? Мой метод прост и эффективен.
замерить угол между соединением вагонов. посчитать кол-во сторон правильного многоугольника
Нужна эффективность в рамках данных условиях
Это если k не экспоненциально растёт.
Ух ты.
Лолшто? Если K < N, то мы на обоих обходах не видим отличий, если K >= N, то мы за два обхода точно узнаём N, то есть наша задача — это просто по возможности быстро найти такой K, что K >= N. Легко пояснить, что самый быстрый способ это сделать — начать с какого-то значения и на каждом шагу его удваивать. Общее количество переходов будет порядка O(N log N)
У каждого вагона есть свой уникальный номер. Запомнить 1 и идти по кругу, пока не будет встречен такой же.
Лол, только недавно вспоминал об этой задаче, пока производил дефекацию.
Хм. Я не понял. Перечитаю еще раз.
Да хотя ну нахуй, не хочу думать. Хочу дефекацию проводить.
Нигде не сказано, что лампочки нельзя выкручивать.
И да, при необходимости [посчитать вагоны], с условием (нельзя выкручивать лампочки), я ыб всё равно нарушил (), так как () противоречит [], а задача [] является основной, а значит, необходимость [] перекрывает условность (), тем самым нигилируя её важности и тем же самым снимая запрет и решает конфликт противоречий.
1)спавнимся в некотором вагоне (обозначим его Х), включаем в нём свет.
2)Идём в X+1, выключаем свет, возвращаемся в Х и проверяем, что в нём ещё горит свет.
3)Идём в Х+2, выключаем свет, возвращаемся в Х и проверяем, что в нём ещё горит свет.
...
к) Идём в Х+к, выключаем свет, возвращаемся в Х и ХУЯК, СВЕТА-ТО И НЕТУ, А БРАТИШКИ И НЕ ДОГАДЫВАЛИСЬ, А ВАГОНОВ-ТО к
2)Идём в X+1, выключаем свет, возвращаемся в Х и проверяем, что в нём ещё горит свет.
3)Идём в Х+2, выключаем свет, возвращаемся в Х и проверяем, что в нём ещё горит свет.
...
к) Идём в Х+к, выключаем свет, возвращаемся в Х и ХУЯК, СВЕТА-ТО И НЕТУ, А БРАТИШКИ И НЕ ДОГАДЫВАЛИСЬ, А ВАГОНОВ-ТО к
Почти верно, но можно не каждый раз возвращаться.
Да все поняли, что ты дебил, да.
Продемонстрируй пожалуйста на примере 6 вагонов, если ты во втором.
Я - решил задачу. Но тебе не нравится способ, и ты поэтому называешь меня дебилом? Это называется АБАСРАЛСЯ@АПТИКАЙ
Ты тупой. Уходи.
ну можно и по степеням двойки наверное, как этот хуй сверху говорит, да, хули бы и нет.
ебучие оценщики сложности алогритмов, У НАС ТИПЕРЬ НИ КА КВАДРАТ, А КА УМНОЖИТЬ НА ЛОГАРИФМ, КАК ЖЕ ОХУЕННО, ПОЙДУ ЕЩЁ ПРОКАЧУСЬ НА ВОЛОСАТОЙ МАШИНЕ ТЬЮРИНГА
Я не понял, как мы узнаем n, если наше k больше его?
1 2 3 4 5 6
+ - - - + +
ты во 2, свет выключен. допустим, что вагонов 4
проверяем
идем до 4 вагона - свет выключен - идем назад во 2, включаем свет
опять идем до 4. свет по-прежнему выключен - наше предположение неверно
-----------------------
допустим, что вагонов 12
проверяем
свет во 2м вагоне выключен, идем 12 вагонов запоминаем "орнамент" лампочек
доходим до 12 вагона, свет выключен - идем на 12 вагонов назад, переключаем свет
по пути "орнамент" лампочек меняется - там, где он изменился легко посчитать кол-во вагонов
да вроде он предлагает по очереди брать n=1,2,4,8 и т.д., чтобы не возвращаться каждый раз в начальный вагон. Можно и по степеням тройки, и хоть чего, но оценка лучше чем к на логарифм к всё равно не получится.
Ах орнамент...
иди нахуй
Пролетишь мимо начального вагона.
можно еще раз, как рассчитать оптимальные интервалы?
беру свои слова назад, можно получить ещё лучше ебучую оценку, даже линейную, можно идти по как угодно быстро возрастающей последовательности, скажем 2^n, или ещё что быстрее.
Проблема в том, что когда мы найдём нужный n, то придётся искать нужное к между 2^n и 2^(n-1), такие дела. Но это уже такое дрочерство что пиздец.
присел-на-колешки-к-дяде-Алану
Замерить расстояние от крепления до крепления вагона. Вычислить периметр кольца ( P = Pi x D ) и поделить его на длину вагона. Лампочки можешь произвольно загнать в свой анус.
Запомни орнамент.
ну дык я и спрашиваю, существуют ли какие-то математически-оптимальные интервалы для таких случаев?
ясно.
да в хуй подуй
тут компромисс между скоростью последовательности a(n) и геморроем проверки к в интервале (a(n-1), a(n)], вот и всё.
Они все эквивалентны по задрачиваемости. %%%С точностью до изоморфизма.%
>да в хуй подуй
это было этому
и таким макаром сложность отыскания n будет кароч как угодно близка к линейной, такие дела
получается что "усовершенствованное" решение не имеет смысла и один хуй что и перебирать с шагом в 1 вагон
Почему?
"Усовершенствованное" решение - не решение (если без "орнаментов").
чому ты такой тупой, я же написал, что всегда нужно будет выбирать компромисс между скоростью роста a(n) и выяснения к из интервала (a(n-1), a(n)]
потому что ты можешь выбрать a(n) = 2^2^2^2^2^2...^2^n, тогда к < ln ln ln ln ln ... ln n
съеби со своими орнаментами, болезный, я в начальном вагоне включаю свет, а во всех остальных выключаю.
какой нахуй компромисс, маня. ты начинаешь оперировать какми-то субъективными понятиями в чисто математической задаче
АТЯТЯ, петушок не знает оптимальности по парето
съеби
Тред не читай@отвечай. Запоминаешь состояние первого вагона, идёшь в одну сторону до тех пор, пока не встретишь вагон с таким же состоянием, возвращаешься в первый, смотришь, не поменялось ли там состояние, если нет, повторить
Аккуратнее.
во, этого харкачну, мне даж больше нравится, лойс тебе от глиномеса Тьюринга
В худшем случае это потребует O(N²) шагов.
зато по-минимуму включений-выключений лампочек
И ваще, ебучие шакалы охуели, считают, что 100000000000000000 n ln n лучше чем 2 n^2, нахуй так жить.
Блин, ну состояние же поменять всё-таки надо, перед тем как назад идти? Понимаю, что "очевидно" но аккуратней с формулировками.
Спросить по рации у оператора сколько вагонов на пути, еба
Bump.
ну и что? в нём же я всё равно выключу свет
18 вагонов. Демонстрируй.
в первом включаю свет.
иду вперёд a(1) = 2 вагонов, по пути выключаю свет во всех, возвращаюсь в первый, проверяю что свет ещё включен.
иду вперёд a(2) = 15 вагонов, по пути выключаю свет во всех, возвращаюсь в первый, проверяю что свет включен
иду вперёд a(3) = 60 вагонов, по пути выключаю свет во всех, возвращаюсь в первый, свет оказался выключен. Таким макаром, k <= 60, дальше дело техники
но ещё раз повторюсь, мне решение этого хлопца больше нравится , там ничего запоминать не надо и по-минимуму дрочить свет
Выключить все включённые, а затем установив произвольную начальную точку, начать последовательно их все включать.
хуилка, а как ты поймёшь, что ты полный круг совершил, а ?
С теорией скорости роста функций ты не знаком, шакал?
Когда не останется ни одной включённой лампочки, очевидно ведь.
ух, ещё как знаком, но всегда ссу на лицо любителям ОПТИМИЗИРОВАТЬ ОЦЕНОЧКИ
и как ты поймёшь, что настал этот момент, вась? Вдруг впереди ещё мильон вагонов без света, а мильон первый со светом
Как у тебя задана последовательность?
На каждом вагоне есть 8 знаков запоминаешь их и считаешь
как угодно, главное что возрастает. И чем быстрее возрастает, тем быстрее локализуется к, такие дела.
Допустим, что последовательность - 2k. Вагонов n = 18. Дальше.
что дальше? на пятом шаге (2^5) ты возвращаешься в начальный вагон, а свет там не горит. Это значит, что ты его выключил, когда шёл вперёд. А ещё это значит, что везде теперь потушен свет. Теперь включаешь в своём вагоне свет и идёшь по тёмным и считаешь, пока не встретишь снова светлый, получаешь число вагонов. Хули неясного?
Ладно, принял. Но c'est la truc и решение с оговоркой, что лампочку выключать надо здесь:
Нумеруем все вагоны от -1 до +бесконечности. Ты изначально стоишь в вагоне под номером 0. Идешь в вагон под номером 1 выключаешь в нем лампу, идешь обратно в вагон под номером -1, включаешь в нем лампу, потом опять идешь в вагон номер 1 проверяешь, не изменилось ли состояние лампы, если нет то идешь в вагон под номером 2, выключаешь в нем лампу, идешь обратно в вагон номер -1, смотришь не изменилось ли состояние лампы в вагоне номер -1, если нет то идешь в вагон номер 3, выключаешь, проверяешь лампу в вагоне -1, и так до n-ного вагона, где ты заметил, что лампа в -1 вагоне погасла. Так кол-во вагонов будет равно n+1
Когда остановится нумерация?
Bump.
Bump.
Bump.
Bump.
Ходишь по всем вагонам и выключаешь лампочки. Для проверки того, что ты выключил их все, включаешь её в одном из поездов и пиздуешь в любом направлении, считая заодно количество вагонов. Как только наткнешься на включенную лампочку включаешь рядом еще одну и пиздуешь обратно, вновь считая вагоны. Если наткнешься после такого же числа вагонов на две лампочки, то ты победитель и знаешь число вагонов.
