Это как в старом анекдоте: Жена посылает программиста за хлебом и говорит: - Если будут яйца, возьми десяток. Программист пришёл с 10 батонами хлеба. На вопрос жены "зачем ты купил 10 батонов?" он ответил: "ну яйца же были, я и взял 10".
Я впервые в своей жизни смог самостоятельно решить заявленно сложную логическую задачку. Причём после каких-то пяти минут размышлений ответ пришёл будто бы озарением! Спасибо за полученные эмоции!
так смысл - не лажануть и не вякнуть глупость, чтоб не попасть на казнь. а так сидишь и играешь в игры начальника, живёшь с надеждой... и Виктор Франкл улыбается с облачка)
Урааа, обожаю, когда получается решить такие задачки самому, прямо как по алгоритму изобретения решений. В большинстве случаев в таких задачках стоит вчитываться в условие, чтобы понять, на что там акцентируется внимание. Перечитав условие довольно быстро пришло решение на моменте со «сколько угодно раз». Классно!
пока не сказали про счётчик, не было никакой идеи как решить..... а как только произнесли это слово, то ответ оказался на поверхности )) спасибо )) интересно ))) программист. периодически пользуюсь таким приёмом, как пример, перед оператором цикла объявляем переменную counter - cчётчик и, как вариант, выходим из цикла по достижению требуемого значения )))
На самом деле не такая уж и сложная задачка оказалась. Решение пришло минут за 5-10, но я сильно засомневался только потому, что с условием любых по времени перерывов между посещениями шанс того, что, вероятно, каждому из заключенный придётся побывать в камере около 100 раз, а счетчику минимум 100 раз, становится абсурдным вариант, что их выпустят до того, как они, мм, умрут от старости. Тем не менее, задачка чисто математическая и к реальным условиям не имеет никого отношения.
Введите элемент сколько им осталось сидеть, и допустим, тот кто выходит из тюрьмы первым, выпускайте его через эту комнату. И продолжайте игру. И тд и тп
@@СашаКовалевский-у4я красавчик. А я бы задался вопросом, что если один из заключенных забудет включить свет, либо включит его повторно, у них же бесконечное количество повторений. Да и много чего может произойти за бесконечное количество времени)) В общем, я как лирик не могу согласиться, что данное решение является истинно верным ))
@@Penobarbital если заключенный забудет включить, ничего не произойдет, он просто отсрочит освобождение. А если включит повторно, то с высокой вероятностью они все умрут (каждое включение - 1 человек)
Почти догадался-не подумал про одного человека-счётчика и что только он может сказать-"здесь все побывали" а пытался решить, что бы каждый мог так сказать
Задача понравилась. Сам думал долго. Думал о том как каждый может узнавать количество переключений. Но не придумал. Но нас словах о том что бы выбрать одного считающего сразу всё понял.
Приходит заключённый с лампочкой в комнату, а там сидит начальник-грузин. Он спрашивает: -Все побывали в комнате? -Побывали, - отвечает заключённый. Начальник гасит лампочку...
Все очень просто, у нас два события возможны для передачи информации о том, был ли человек в комнате, он может либо включить, либо выключить свет. Так вот, все просто, все, кроме счетчика могут лишь раз включить свет (или выключить) свет, а счетчик приводит выключатель в обратное положение, чтобы посчитать следующего
@@rotmerka2820 пусть 0-когда лампочка не горит,а 1-когда лампочка горит,тогда у нас есть изначально число 0000000.когда человек,который еще ни разу не был в комнате, заходит, то он прибавляет к числу единичку.так можно получить 1111111(7единиц),то есть 2^7-1=128-1=127.когда человек заходит в комнату и видит число,равное 100, то говорит об окончании игры.
У меня была та же мысль, но гасить лампочку если ты там не был. Но если лампочка выключена, но ты там не был, слегка выкрутить её на четверть оборота. Для лампочки в зависимости от произволителя надо около от 5 четвертей оборотов что бы вытащить Получается 5 человек может передать что они там были
Идея, что надо назначить одного «избранного», который будет считать пришла прямо во время оглашения условия, дальше до полного решения думал не больше пол-минуты. Но задачка прикольная.
Второй раз смотрю, и второй раз не могу решить :( Подсознательно хочется, чтобы как только последний человек придёт в комнату, можно было дать ответ, но это далеко не так))
Получилось решить минуты за 3, но решение то же. И в правду идея очень похожа на идеи решения кучи задач по программированию, единственное, мне кажется, человек который считал ошибётся в арефметике, и они все умрут
если я ничего не прослушал, то в камере никто не мешает царапать стены или вообще писать на них что то, так что счетчик может отметки ставить и нет проблем)
@@wmrinchester а я и не пытался, это был ответ на предположение, что зек может затупить в арифметике, а я и сказал, как он может это посчитать, смысл решения от этого не меняется
@@wmrinchester нельзя для других отметки делать, для передачи информации. Делать отметки для себя, в своей камере, чтоб не сбиться со счета - не является попыткой обойти условия...
Для страховки от ошибок счетчику нужно считать не до 99, а скажем до 102. Или досчитав до 99 и сомневаясь, не ошибся ли он, счетчик может еще подождать и если в течении длительного времени, так никто лампочки и не включит, то можно предположить, что он не ошибся.
Я бы добавил к уже показанной стратегии обязанность каждого заключённого считать число переходов, 1 в 0. Т.е. если он увидел лампу уже включённой (не им самим), а потом увидел лампу уже выключенной. Это значит кто-то из обычных заходил, а потом счётчик заходил. Когда он насчитает таких переходов 97 (т.е. 97 обычных и счётчик уже заходили), то когда следующий раз будет 1 (лампа горит), значит уже 98 обычных (кроме него) и счётчик уже в комнате побывали. Можно заявлять, что уже все побывали. С небольшой вероятность, но возможно, что это событие наступит раньше последнего визита счётчика.
Мне кажется, что это не совсем верно. Если какой-нибудь номер 2 увидел включенную лампу, вышел, зашел счетчик - выключил, зашел номер 3 - включил, зашел опять счетчик - выключил, зашел номер 4 - включил, зашел счетчик - выключил, и теперь зашел номер 2 и видит выключенную лампу. По твоей идее произошел 1 переход, хотя на самом деле было два (3-> счетчик, 4-> счетчик).
@@Укажитеназваниеканала-б8з В этой стратегии у всех событий вероятность маленькая, потому и время эксперимента выбрано бесконечным. Не придумал как посчитать, при каком количестве заходов вероятность успешного завершения игры, при игре по данной стратегии, достигнет 50%. Так сказать время полувыйгрыша стратегии. Любое дополнение или изменение стратегии, при котором количество заходов до полувыйгрыша уменьшится, следует считать улучшением стратегии.
@@AndreySkakun изначально собрался похвалить тебя, но нашел ошибку. Второй счетчик, увидевший 98 переходов, никогда не может быть уверен, что настоящий счетчик побывал в комнате. Поэтому стратегия не гарантированная, а рискованная.
сначала не догадался, решил посмотреть решение, как только услышал идею со счетчиком, я сразу понял в чем прикол)) так что процентов на 50 я сам догадался)
У меня был вариант, что каждый из них нажмëт кнопку 10 раз и типо когда лампочка перегорит, то уже тут по любому было 100 человек. (Это первое, что мне пришло в голову, я тогда даже не подумал, что могут вообще 1 человека постоянно только звать, а потом уже второго)
звучит красиво, но самого "счётчика" могут больше ни разу не повести в комнату. Или водить очень редко. А другие свет выключить не могут и ничего не делают. Все могут побывать не один раз... Т.е. когда следующий раз поведут счётчика, он выключит свет и посчитает 2. Но на самом деле все уже там побывали))
@@РоманРоман-б2ы с чего бы это? 1 раз он там побывал и выключил свет. Это уже 2, если с ним считать. А если без него, то второй раз, когда его приведут, после кого-нибудь, кто был 1-й раз и включил свет - и посчитает "2"
Когда ты сказал поставить видео на паузу и подумать, я не придумал ничего, но когда ты после паузы сказал, "уходя они выключат свет", я решил за две секунды. А возможно ли решить, если нельзя зафиксировать начальное положение?
@@tufoedнет. Если не известно первоначальное состояние лампочки то первый раз когда зайдет счетчик (а лампочка будет гореть он скажет 0 (не станет засчитывать а начнет с 2го посещения когда лампочка будет гореть) а если не горит значит он первый оказался в комнате). И да, это надо бы занести в условие задачи, но по умолчанию - логически если подумать то свет будет выключен на начало игры т.к. по идее после того как их соберут вместе и выведут из комнаты свет выключат и запрут комнату. Вероятно поэтому Борис и предложил так. П.с. Я бы добавил этот пункт в условие задачи, но что бы состояние лампочки было не известно на момент начала игры.
долго думал над алгоритмами, когда кто-то будет поочерёдно включать и выключать свет, но в таких решениях ничего не удавалось, всегда у надзирателя была стратегия не выпустить заключённых. в какой-то момент неожиданно придумал правильное решение, то же, что и в видео. очень обрадовался)
Не смог дойти до конца коментом, может все это уже было, но попробую собрать в одном месте. Задачу слышал уже давно, но там было 3 лампочки, что сбивало с толку и изрядно добавляло сложности. Хорошо бы найти предысторию задачи, было бы очень интересно. Начальное состояние лампочки не важно, достаточно договориться включать ее по два раза каждому. Что касается ускорения процесса, есть такой вариант - каждый становится счетчиком, то есть, каждый просто меняет состояние лампочки на противоположное. При этом он запоминает число своих "выключений" и действует так, что бы число его "включенний" не превышало число "выключений" на 1. Надеюсь, идея понятна, тем более, что скорее всего ее уже предлагали. Кажется, что при некоторых условиях этот подход может заметно ускорить процесс, но тут все зависит от того, по какому принципу их "вызывают". Вообще, было бы интересно обсудить и развить идею, может быть кто нибудь предложит более удобную площадку, чем комменты ютуба. Задачка того стоит, имхо )
Кажется ускорение не сработает, так как могут просто приводить одного и того же человека много раз подряд, в итоге у него будет равное число включений и выключений с любым их количеством
@@artemcherkashin1928 да, в некоторых случаях эта стратегия будет хуже исходной, мне тоже так кажется, я поэтому и написал: "при некоторых условиях". Но, условие случайного вызова несколько неопределенно: тут уже писали, в других комментах, что при некоторых распределениях вероятности вызова время, за которое сходится исходная стратегия может быть устремлено к бесконечности. Так что даже численный эксперимент не поставишь. Но, если дополнительно ограничить условия, например сказать, что всех вызовут по одному разу в случайном порядке, потом по второму заходу и т.д, то мой вариант будет многократно быстрее исходного. Примитив, конечно, но я не знаю, как бороться с дурными бесконечности исходного условия. Тут могло бы матмоделирование помочь, но для него, как раз, придется алгоритм вызова сделать более определенным, можно, в принципе, предлагать варианты и пробовать )
Минут 5 ушло. Сначала они оставляют свет включённым, и назначают одного который будет считать. Если заключённый заходит первый раз в комнату с включённым светом, то он выключает его. Когда назначенный заходит и видит выключенный свет, он запоминает что один уже побывал, прибавляет к сумме побывавших и включает лампу. Когда он досчитает до числа заключённых кроме себя, то он говорит что всё побывали.
На практике из людей обязательно найдутся те, кто будет выключать свет вместо включения, будут включать свет много раз и т.п. И потом со словами: А што, не так надо было делать штоле? Ну тогда включите там свет после меня, сложно штоле одну кнопочку нажать.
Еще не смотрел видео, вот моя идея: На митинге заключенные нумеруют себя для определенности. Начальника просят оставить свет включенным. Далее будет происходить следующее: все заключенные от 1 до n-1 выключают свет в конмнате (могут ТОЛЬКО выключать и ТОЛЬКО каждый один раз) Когда n-ный заходит в комнату, он, во-первых включает свет, во-вторых царапает черточку на руке. Когда n-ый нацарапет n-1 черточку на руке, они победили.
Щас на 3:56. Подумал 3-4 минуты, придумал так, для удобства обозначу состояния 1- горит и 0-нет. Мы договариваемся, что изначально горит(не суть важно тогда просто состояния поменять), и если кто-то видит состояние 1, то он её выключает, но сделать так он может только 1 раз, но если состояние 0, то он просто уходит. Таким образом, я приду и увижу что если лампа в состоянии 0, то я её включу и уйду + с свой счётчик я добавлю +1 и так пока он не станет 99
Надо рассматривать задачу посложнее, когда первоначальное состояние лампочки не известно (а собирают их на совещание в другом месте). Ну и ещё круче загадывать с двумя лампочками. Вторая очень здорово вводит в заблуждение.
Если первоначальное состояние лампочки не известно, то задача сложнее не становится - просто когда счетчик попадет в комнату, ему для безопастности вычислений нужно просто выключить лампочку и НЕ прибавлять 1 к счету. Другие заключенные также не должны трогать выключатель, пока лампочка будет гореть в комнате. Изменено: это работает только для включенного состояния лампочки, для выключенного механизм ломается - не следуйте моему решению)
@@balansodumar2619 Если не известно, то твоя идея сработает только если лампочка была включена. Никто же не знает кого первым запустят в комнату. То есть, когда счётчик зашёл в комнату первый раз, а там горит лампочка, есть 2 варианта. Первый (который ты описал) лампочка была включена изначально. Второй лампочка была выключена изначально и 1 из других заключённых её уже включил.
@@dragonsnyashers6309 Ну так я правильно вроде все написал, если заключенным не известно первоначальное состояние лампочки, для избежания ошибки в расчетах счетчику нужно пропустить в своем счету первую единицу, если лампочка горит в первый раз прихода счетчика. Если она не горит в первый раз прихода счетчика , то счетчик просто должен уйти и в следующий раз повторить вышеописанную мной процедуру. А когда счетчик прийдет в комнату следующий раз, то он просто должен следовать плану Трушина. Правильно обьяснил?
Решение действительно очень простое. Мы просто договариваемся включать свет единожды и выключать, если мы уже были в комнате. Когда "Счётчик" приходит и видит, что свет выключен - он говорит, что все в комнате были. ::)
Ваше решение не учитывает такую ситуацию: Приходит первый заключённый впервые - включает свет. Его снова заводят через какой-то промежуток - он выключает свет. Заходит счётчик - видит потушенный свет - говорит, что все тут были, и всех расстреливают
В свое время я её решил, но есть два обязательных условия: 1. Во время этого эксперимента никто из заключённых не умрет; 2. Все заключённые умеют считать.
Считать достаточно уметь только счëтчику. Всем остальным достаточно запомнить, что каждый включает лампочку самостоятельно только один раз за всë время.
Ну не знаю, насколько она прям сложная, я пока слушал БВ, без паузы придумал решение. Хотя может годы программирования дают о себе знать 😄, но идея ввести счётчик пришла сразу
Решил за 5 минут Аж сам того не ожидал. В размышлениях шёл от обратного. У нас есть бинарная система вкл/выкл, а нужно посчитать 100 человек. Если каждый будет проверять значение в комнате, то нереально построить какую-то комбинацию всего из 2 значений. Тогда подумал, что только часть из них будет проверять. Но поскольку они не могут друг с другом общаться, проверяющий может быть только один. Ну и последнее - все остальные включают только 1 раз - уже было легко додуматься.
@@leonidrozenblum6880 конечное, но не известное заранее. Поэтому нужно жить бесконечно, иначе (если известно сколько они живут) экспериментатор придумает алгоритм как сделать чтобы они все умерли в тюрьме
@@Alpac999 У них организм может быть настроен не на бесконечное время, а только на то время, пока они находятся в тюрьме. Т.е. это все таки конечное (хоть и неизвестное) время.
За первые 10 секунд после озвучивания условия придумал ответ. Изначально надо выключить лампочку и каждый человек если он ещё не включал лампочку и при этом лампочка не горит включает её, один человек считает количество включенных лампочек и каждый раз после себя выключает её
01.08.2023. Узнал в день выпуска. Придумал сейчас. Решения по сути одинаковы. Только "Счётчик" - "Избранный", включает свет только он, а другие в свое первое посещение его выключают и подсчёт ведётся по выключенным лампочкам. Спасибо за задачу)
Привет! Был чемпионом по 10 заключённым. Задача была на элементах ру про 10 заключённых. Самая красота в выборах счетчика. Идея пришла независимо, на иностранных источниках её называют динамическим счетчиком для задачи на 100 заключённых. Красота моего решения была в ограниченном количестве заключённых. Выборы заканчиваются на 4 дня раньше. Иглобрюх довёл решение до абсолюта, спасибо, тебе, неизвестный друг!
Удалось довести до 92.39968 дня с первоначальных 120! С неофициалами можно довести на 0.0002-0.0003 лучше. Классная задачка, на пару выпусков тянет, с историей решений.
Надо подумать, а как лампочка помогает. Понять, что надо считать включенные (или наоборот выключенные, если сначала лампочка горит), понять, что считать в теории может только 1. А к этому моменту уже все поймут решение. Мы при заходе понимаем, что был заключенный новый или нет, а по лампочке мы понимаем горит или не горит, т.е. нужно задать соответствие между состоянием лампочки и новым побывавшим заключенным. Но раз задаем соответствие, то каждый включает 1 раз, но нам надо считать и бла бла бла и все короче.
Странно, решение очень простое, а я к нему не пришел ни сегодня, ни годами ранее, когда впервые услышал задачку. С намека на счетчик сразу стало понятно, но блин
я видел формулировку где не известно начальное состояние лампочки.Эти 100 бедолаг собирались не в этой комнате , а где то еще в другом месте. Тут предполагается что лампочка выключена сразу.В таком виде задача очень простая.
Если не известно начальное состояние, то решение несильно усложняется. Все должны по два раза включать лампочку, тогда после 198 выключений все точно были хотя бы раз
В условие еще надо добавить, что они бессмертные. От сидения в одиночной камере ни у кого здоровья не прибавлялось пока. Счетчика выбрали, а он через месяц загнулся, и привет.
О, я тоже так додумался: каждый по разу включит, а какой-то один гасить будет. Конечно, так может много времени пройти, но тут время бесконечное. Только я не продвинутый программист, а больше математик.
Решение у меня такое же, только свет не включать, а выключать может один раз каждый заключенный. Так большинство заключённых будут сидеть в этой камере при свете, а это лучше чем без света😂
Почему? Пронумеруем от 1 до 100, 1-ый "счётчик". Вначале заходит и включает второй, потом заходит и выключает первый. Затем также третий, потом опять первый. И того, мин время 2n, формально это вообще О(n)
@@mega_mango По условию задачи, приводят людей рандомно. Значит, кто-то может быть ни разу, а кто-то уже 10 раз. Конечно, если по условию каждый должен попасть хотя бы 1 раз к лампочке, то рано или поздно, это случится. Но в любом случае, в подобных задачах пренебрегают человеческим фактором тех, кто принимает решение выбора.
@@mega_mango если вероятность выбора каждого конкретного заключённого распределена равномерно -- то "счётчик" будет заходить в камеру каждый n-ый раз, и сделать это он должен n-1 раз. Вот и выходит что сложность n^2. Если попробовать смоделировать это программно то придётся использовать 2 цикла, что значит О (n^2) (если так нагляднее
Вы, вроде, не говорили о Наяальном состоянии лампочки. А раз так, то она изначально может быть включена, тогда счётчик может подсчитать первого заключённого за себя и таким образом на 99 счëт комнату посетят 98 человек
Кстати, не-счётчик может включить свет не в первый раз, когда свет не горит, а, например, в пятый. Главное, чтобы только один раз. Из-за него, правда, _все_ сидеть будут дольше.
Мое решение (пока что не смотрел ответ): выбираем одного человека. Он делает следующее: если лампочка включена, то он ничего не делает; если выключена, то включает и прибавляет к n единицу (в начале n = 0). Остальные: если лампочка выключена, то ничего не делают. Если лампочка включена и они до этого ещё ее не выключали, то выключают. Если уже выключали до этого, то ничего не делают. Таким образом все 99 людей выключат лампочку по одному разу. А тот исключительный человек включит 99 раз лампочку. Соответственно, когда будет 99 раз, то он может спокойно сказать, что все 100 заключённых были в этой камере.
У меня был вариант, что раз их в этой комнате собрали, значит они уже там все побывали
По моему скромному мнению это шедевральный ответ.
Это как в старом анекдоте:
Жена посылает программиста за хлебом и говорит:
- Если будут яйца, возьми десяток.
Программист пришёл с 10 батонами хлеба. На вопрос жены "зачем ты купил 10 батонов?" он ответил: "ну яйца же были, я и взял 10".
Тоже так сразу подумал, но от ролика оставалось пять минут, потому пришлось отбросить вариант
Товарищ, ты Гений)
@@Zlobny-Kotyara 🤣 (самый программистский анекдот в мире)
Программист. Догадался как решать после того как Борис сказал про то что мы вводим счётчика :)
+
да уж кто-то считает, ага...
Чем-то напоминает тему про мьютексы с семафорами из freeRTOS.
+
Наверно, все программисты одинаковы😂+
Я впервые в своей жизни смог самостоятельно решить заявленно сложную логическую задачку. Причём после каких-то пяти минут размышлений ответ пришёл будто бы озарением! Спасибо за полученные эмоции!
Студент.
Догадался сам, учусь на прогера)))
Спасибо за классную головоломку, так доволен собой)))
После озвученного условия, пришла мысль, что раз человек может побывать возможно вообще раз в 10 лет, то никто оттуда не выйдет)
Ну типа это сработает в бесконечном промежутке времени, с бессмертными узниками)
Ага. Да ещё если этот человек окажется щотчиком.
@@northwardcoreи с бессмертной лампочкой ;)
так смысл - не лажануть и не вякнуть глупость, чтоб не попасть на казнь. а так сидишь и играешь в игры начальника, живёшь с надеждой... и Виктор Франкл улыбается с облачка)
Нужно больше подобных задачек на канале.
Урааа, обожаю, когда получается решить такие задачки самому, прямо как по алгоритму изобретения решений. В большинстве случаев в таких задачках стоит вчитываться в условие, чтобы понять, на что там акцентируется внимание. Перечитав условие довольно быстро пришло решение на моменте со «сколько угодно раз». Классно!
пока не сказали про счётчик, не было никакой идеи как решить..... а как только произнесли это слово, то ответ оказался на поверхности )) спасибо )) интересно ))) программист. периодически пользуюсь таким приёмом, как пример, перед оператором цикла объявляем переменную counter - cчётчик и, как вариант, выходим из цикла по достижению требуемого значения )))
На самом деле не такая уж и сложная задачка оказалась. Решение пришло минут за 5-10, но я сильно засомневался только потому, что с условием любых по времени перерывов между посещениями шанс того, что, вероятно, каждому из заключенный придётся побывать в камере около 100 раз, а счетчику минимум 100 раз, становится абсурдным вариант, что их выпустят до того, как они, мм, умрут от старости. Тем не менее, задачка чисто математическая и к реальным условиям не имеет никого отношения.
Введите элемент сколько им осталось сидеть, и допустим, тот кто выходит из тюрьмы первым, выпускайте его через эту комнату. И продолжайте игру. И тд и тп
Если взять 10 человек, то все могут выйти за год
БОЖЕ МОЙ Я РЕШИЛ ЕЕ САМ, Я ТАК СЧАСТЛИВ, СПАСИБО ЗА ПОДНЯТИЕ САМООЦЕНКИ И ПРЕКРАСНУЮ ЗАДАЧУ!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Поздравляю! Молодец
@@СашаКовалевский-у4я красавчик. А я бы задался вопросом, что если один из заключенных забудет включить свет, либо включит его повторно, у них же бесконечное количество повторений. Да и много чего может произойти за бесконечное количество времени)) В общем, я как лирик не могу согласиться, что данное решение является истинно верным ))
@@Penobarbital Но стратегия-то верная. А сработает ли она это уже неважно
@@user-lu3jb8oe5y это с точки зрения математика, где всё чётко и определенно, но, как правило, вне квантового мира это не работает )
@@Penobarbital если заключенный забудет включить, ничего не произойдет, он просто отсрочит освобождение. А если включит повторно, то с высокой вероятностью они все умрут (каждое включение - 1 человек)
Решил сам, очень доволен собой. Спасибо за видео!
Почти догадался-не подумал про одного человека-счётчика и что только он может сказать-"здесь все побывали" а пытался решить, что бы каждый мог так сказать
Решил задачу довольно быстро, а потом долго не открывал этот ролик и думал, а какое же там "красивое" решение))))
Задача понравилась. Сам думал долго. Думал о том как каждый может узнавать количество переключений. Но не придумал. Но нас словах о том что бы выбрать одного считающего сразу всё понял.
Ура, новое видео!
Благодаря Вашим роликам стал по-настоящему понимать и интересоваться математикой.
Спасибо за Ваш труд!
Как только любой человек заходит в комнату он сразу же говорит что все 100 людей уже тут побывали. Всех казнят, все довольны
Приходит заключённый с лампочкой в комнату, а там сидит начальник-грузин. Он спрашивает:
-Все побывали в комнате?
-Побывали, - отвечает заключённый.
Начальник гасит лампочку...
ААЗАЗАХАЗХ
Вазелин, заходи...
гачи-фанфик на логическую задачу. Воистину эпоха метаиронии
Ахах
Ты попу мыл? 😂
И гасит лампочку
я так понимаю на категорию б можно где угодно наткнуться
Все очень просто, у нас два события возможны для передачи информации о том, был ли человек в комнате, он может либо включить, либо выключить свет. Так вот, все просто, все, кроме счетчика могут лишь раз включить свет (или выключить) свет, а счетчик приводит выключатель в обратное положение, чтобы посчитать следующего
Спасибо. Классная задача. Жаль не догадался, хотя это чисто программная задача на массив и цикл do while. Обидно, не сообразил.
Трушин решил в одном видео собрать всех программистов, да 🤣
Круто! Сразу посмотрели с детьми)
Очень понравилась задача, спасибо!
Я мыслил в верном направлении - что каждый только один раз меняет состояние, а Счетчика назвал - Избранным
😂 Я назвал его Включатель. У меня все гасили а он включал лампочку.
Я лишь придумал решение с 7 лампочками при помощи двоичной системы счисления
То же самое:)
А как?
@@rotmerka2820 пусть 0-когда лампочка не горит,а 1-когда лампочка горит,тогда у нас есть изначально число 0000000.когда человек,который еще ни разу не был в комнате, заходит, то он прибавляет к числу единичку.так можно получить 1111111(7единиц),то есть 2^7-1=128-1=127.когда человек заходит в комнату и видит число,равное 100, то говорит об окончании игры.
@@MoonLight-jr5hl Надо не забыть повесить 8 выключателей
У меня была та же мысль, но гасить лампочку если ты там не был.
Но если лампочка выключена, но ты там не был, слегка выкрутить её на четверть оборота. Для лампочки в зависимости от произволителя надо около от 5 четвертей оборотов что бы вытащить
Получается 5 человек может передать что они там были
Сразу в голову пришла идея на счет единого развого включения света, но не стерпел и посмотрел решение. Эх, а я так был близок :(
Всё гениальное просто!
Очень круто и красиво!
Идея, что надо назначить одного «избранного», который будет считать пришла прямо во время оглашения условия, дальше до полного решения думал не больше пол-минуты. Но задачка прикольная.
Что так, что иначе, им освобождение не грозит.
Поезд с вагонами в помощь😊 Версия 2.0: начальник тюрьмы бросает 10 кубиков с 11-мя гранями(от 0 до 10). Спасибо за контент, задача интересная.
Задачка огонь!! 👍
Второй раз смотрю, и второй раз не могу решить :( Подсознательно хочется, чтобы как только последний человек придёт в комнату, можно было дать ответ, но это далеко не так))
Решил. Очень круто. Спасибо.
Забавно, что раньше я не понимал это решение) Спасибо
Получилось решить минуты за 3, но решение то же. И в правду идея очень похожа на идеи решения кучи задач по программированию, единственное, мне кажется, человек который считал ошибётся в арефметике, и они все умрут
если я ничего не прослушал, то в камере никто не мешает царапать стены или вообще писать на них что то, так что счетчик может отметки ставить и нет проблем)
@@whatisblink в видео Борис отдельно пояснил, что нельзя. Подобные задачи всегда на логику, а не попытку как-то обхитрить условия.
@@wmrinchester а я и не пытался, это был ответ на предположение, что зек может затупить в арифметике, а я и сказал, как он может это посчитать, смысл решения от этого не меняется
@@wmrinchester нельзя для других отметки делать, для передачи информации. Делать отметки для себя, в своей камере, чтоб не сбиться со счета - не является попыткой обойти условия...
Для страховки от ошибок счетчику нужно считать не до 99, а скажем до 102. Или досчитав до 99 и сомневаясь, не ошибся ли он, счетчик может еще подождать и если в течении длительного времени, так никто лампочки и не включит, то можно предположить, что он не ошибся.
Я бы добавил к уже показанной стратегии обязанность каждого заключённого считать число переходов, 1 в 0. Т.е. если он увидел лампу уже включённой (не им самим), а потом увидел лампу уже выключенной. Это значит кто-то из обычных заходил, а потом счётчик заходил. Когда он насчитает таких переходов 97 (т.е. 97 обычных и счётчик уже заходили), то когда следующий раз будет 1 (лампа горит), значит уже 98 обычных (кроме него) и счётчик уже в комнате побывали. Можно заявлять, что уже все побывали.
С небольшой вероятность, но возможно, что это событие наступит раньше последнего визита счётчика.
Мне кажется, что это не совсем верно. Если какой-нибудь номер 2 увидел включенную лампу, вышел, зашел счетчик - выключил, зашел номер 3 - включил, зашел опять счетчик - выключил, зашел номер 4 - включил, зашел счетчик - выключил, и теперь зашел номер 2 и видит выключенную лампу. По твоей идее произошел 1 переход, хотя на самом деле было два (3-> счетчик, 4-> счетчик).
Кажется понял, но шанс, что наступит 97 переходов крайне мал.
@@Укажитеназваниеканала-б8з В этой стратегии у всех событий вероятность маленькая, потому и время эксперимента выбрано бесконечным.
Не придумал как посчитать, при каком количестве заходов вероятность успешного завершения игры, при игре по данной стратегии, достигнет 50%. Так сказать время полувыйгрыша стратегии.
Любое дополнение или изменение стратегии, при котором количество заходов до полувыйгрыша уменьшится, следует считать улучшением стратегии.
@@AndreySkakun изначально собрался похвалить тебя, но нашел ошибку. Второй счетчик, увидевший 98 переходов, никогда не может быть уверен, что настоящий счетчик побывал в комнате. Поэтому стратегия не гарантированная, а рискованная.
"2-й счётчик" - это любой из 99-ти обычных заключённых. А чтобы знать наверняка, что счётчик уже был, достаточно увидеть всего 1 переход (1->0).
Охранники их всех пускают по кругу))00(0)0)0))00)0 10:09
сначала не догадался, решил посмотреть решение, как только услышал идею со счетчиком, я сразу понял в чем прикол)) так что процентов на 50 я сам догадался)
Я наоборот дошел до счетчика, но не понял как считать. Почему то думал, что обязательно надо дать разные инструкции четным и нечетным заключенным.
сразу понял, что лампочкой будут считать. Иного варианта не дано.
Давно знаю эту задачу, и сам решил точно также, но до сих пор уверен, что есть решение лучше.
Жиза... по-любому задачу коммивояжёра можно решить за О(х^n) и захватить весь мир, зная что p = np😅
Здравствуйте хотел бы узнать что будет если счетчик не придет первым?
Супер задачка! И очень красивое решение!
Мне удалось решить! Замечательная задача на бинарную логику, спасибо.
У меня был вариант, что каждый из них нажмëт кнопку 10 раз и типо когда лампочка перегорит, то уже тут по любому было 100 человек. (Это первое, что мне пришло в голову, я тогда даже не подумал, что могут вообще 1 человека постоянно только звать, а потом уже второго)
звучит красиво, но самого "счётчика" могут больше ни разу не повести в комнату. Или водить очень редко. А другие свет выключить не могут и ничего не делают. Все могут побывать не один раз... Т.е. когда следующий раз поведут счётчика, он выключит свет и посчитает 2. Но на самом деле все уже там побывали))
Если свет изначально выключен , а включить каждому можно только по 1 разу и счётчик только выключить может , то "2" никак не посчитает.
@@РоманРоман-б2ы с чего бы это? 1 раз он там побывал и выключил свет. Это уже 2, если с ним считать. А если без него, то второй раз, когда его приведут, после кого-нибудь, кто был 1-й раз и включил свет - и посчитает "2"
Изначально должен свет быть выключен а не включен быть.
При этом не будет такого что ты описал. Тогда всё нормально пройдёт.
Когда ты сказал поставить видео на паузу и подумать, я не придумал ничего, но когда ты после паузы сказал, "уходя они выключат свет", я решил за две секунды. А возможно ли решить, если нельзя зафиксировать начальное положение?
Да, тогда каждому придется по два раза свет включать, ну и займет вдвое больше времени
@@tufoed ничего не понял
@@kasitskyi в соседней ветке комментариев есть более детальный разбор.
@@tufoedнет. Если не известно первоначальное состояние лампочки то первый раз когда зайдет счетчик (а лампочка будет гореть он скажет 0 (не станет засчитывать а начнет с 2го посещения когда лампочка будет гореть) а если не горит значит он первый оказался в комнате). И да, это надо бы занести в условие задачи, но по умолчанию - логически если подумать то свет будет выключен на начало игры т.к. по идее после того как их соберут вместе и выведут из комнаты свет выключат и запрут комнату. Вероятно поэтому Борис и предложил так.
П.с. Я бы добавил этот пункт в условие задачи, но что бы состояние лампочки было не известно на момент начала игры.
@@sergioprofessor4038 если лампочка горит, как понять, горела ли она самого начала или ее кто-то включил?
долго думал над алгоритмами, когда кто-то будет поочерёдно включать и выключать свет, но в таких решениях ничего не удавалось, всегда у надзирателя была стратегия не выпустить заключённых. в какой-то момент неожиданно придумал правильное решение, то же, что и в видео. очень обрадовался)
Не смог дойти до конца коментом, может все это уже было, но попробую собрать в одном месте. Задачу слышал уже давно, но там было 3 лампочки, что сбивало с толку и изрядно добавляло сложности. Хорошо бы найти предысторию задачи, было бы очень интересно.
Начальное состояние лампочки не важно, достаточно договориться включать ее по два раза каждому.
Что касается ускорения процесса, есть такой вариант - каждый становится счетчиком, то есть, каждый просто меняет состояние лампочки на противоположное. При этом он запоминает число своих "выключений" и действует так, что бы число его "включенний" не превышало число "выключений" на 1. Надеюсь, идея понятна, тем более, что скорее всего ее уже предлагали. Кажется, что при некоторых условиях этот подход может заметно ускорить процесс, но тут все зависит от того, по какому принципу их "вызывают". Вообще, было бы интересно обсудить и развить идею, может быть кто нибудь предложит более удобную площадку, чем комменты ютуба. Задачка того стоит, имхо )
8
Кажется ускорение не сработает, так как могут просто приводить одного и того же человека много раз подряд, в итоге у него будет равное число включений и выключений с любым их количеством
@@artemcherkashin1928 да, в некоторых случаях эта стратегия будет хуже исходной, мне тоже так кажется, я поэтому и написал: "при некоторых условиях". Но, условие случайного вызова несколько неопределенно: тут уже писали, в других комментах, что при некоторых распределениях вероятности вызова время, за которое сходится исходная стратегия может быть устремлено к бесконечности. Так что даже численный эксперимент не поставишь. Но, если дополнительно ограничить условия, например сказать, что всех вызовут по одному разу в случайном порядке, потом по второму заходу и т.д, то мой вариант будет многократно быстрее исходного. Примитив, конечно, но я не знаю, как бороться с дурными бесконечности исходного условия. Тут могло бы матмоделирование помочь, но для него, как раз, придется алгоритм вызова сделать более определенным, можно, в принципе, предлагать варианты и пробовать )
Минут 5 ушло. Сначала они оставляют свет включённым, и назначают одного который будет считать. Если заключённый заходит первый раз в комнату с включённым светом, то он выключает его. Когда назначенный заходит и видит выключенный свет, он запоминает что один уже побывал, прибавляет к сумме побывавших и включает лампу. Когда он досчитает до числа заключённых кроме себя, то он говорит что всё побывали.
На практике из людей обязательно найдутся те, кто будет выключать свет вместо включения, будут включать свет много раз и т.п. И потом со словами: А што, не так надо было делать штоле? Ну тогда включите там свет после меня, сложно штоле одну кнопочку нажать.
Тем временем тот самый заключенный, который по приколу решил включить свет второй раз)
Ну да, красивое решение❤
Решил! Интересная задача, спасибо! "Счётчика" назвал "смотрящим" :)
Еще не смотрел видео, вот моя идея: На митинге заключенные нумеруют себя для определенности. Начальника просят оставить свет включенным. Далее будет происходить следующее: все заключенные от 1 до n-1 выключают свет в конмнате (могут ТОЛЬКО выключать и ТОЛЬКО каждый один раз) Когда n-ный заходит в комнату, он, во-первых включает свет, во-вторых царапает черточку на руке. Когда n-ый нацарапет n-1 черточку на руке, они победили.
Пару минут понадобилось, чтобы придумать решение. Удивительно, я походу не такой уж и тупой
Придумал решение минуты за 3, решил быстрее Бориса Викторовича получается😎
Щас на 3:56. Подумал 3-4 минуты, придумал так, для удобства обозначу состояния 1- горит и 0-нет. Мы договариваемся, что изначально горит(не суть важно тогда просто состояния поменять), и если кто-то видит состояние 1, то он её выключает, но сделать так он может только 1 раз, но если состояние 0, то он просто уходит. Таким образом, я приду и увижу что если лампа в состоянии 0, то я её включу и уйду + с свой счётчик я добавлю +1 и так пока он не станет 99
Надо рассматривать задачу посложнее, когда первоначальное состояние лампочки не известно (а собирают их на совещание в другом месте).
Ну и ещё круче загадывать с двумя лампочками. Вторая очень здорово вводит в заблуждение.
Если первоначальное состояние лампочки не известно, то задача сложнее не становится - просто когда счетчик попадет в комнату, ему для безопастности вычислений нужно просто выключить лампочку и НЕ прибавлять 1 к счету. Другие заключенные также не должны трогать выключатель, пока лампочка будет гореть в комнате.
Изменено: это работает только для включенного состояния лампочки, для выключенного механизм ломается - не следуйте моему решению)
А с двумя лампочками интересно, возможно можно ускорить процесс выхода заключенных на свободу, но я пока не придумал решение.
@@balansodumar2619 Если не известно, то твоя идея сработает только если лампочка была включена. Никто же не знает кого первым запустят в комнату.
То есть, когда счётчик зашёл в комнату первый раз, а там горит лампочка, есть 2 варианта. Первый (который ты описал) лампочка была включена изначально. Второй лампочка была выключена изначально и 1 из других заключённых её уже включил.
@@dragonsnyashers6309 Ну так я правильно вроде все написал, если заключенным не известно первоначальное состояние лампочки, для избежания ошибки в расчетах счетчику нужно пропустить в своем счету первую единицу, если лампочка горит в первый раз прихода счетчика. Если она не горит в первый раз прихода счетчика , то счетчик просто должен уйти и в следующий раз повторить вышеописанную мной процедуру. А когда счетчик прийдет в комнату следующий раз, то он просто должен следовать плану Трушина. Правильно обьяснил?
@@balansodumar2619 заключённые могут включить лампочку ровно 99 раз. Суммарно. Если пропустить единицу, то "счётчик" может никогда не досчитать до 99.
Я в восторге
Решение действительно очень простое. Мы просто договариваемся включать свет единожды и выключать, если мы уже были в комнате. Когда "Счётчик" приходит и видит, что свет выключен - он говорит, что все в комнате были. ::)
Первый же зэк, побывавший дважды приведёт к сбою этой схемы подсчёта
Ваше решение не учитывает такую ситуацию:
Приходит первый заключённый впервые - включает свет.
Его снова заводят через какой-то промежуток - он выключает свет.
Заходит счётчик - видит потушенный свет - говорит, что все тут были, и всех расстреливают
почему я сразу до этого додумался... "да ты программист!"
И я программист. За пару минут придумал РОВНО такое же решение. Только назвал его не счётчиком, а сторожем
Боже, какое простое решение для, казалось бы, сложной задачи
Прикольная задача 👍
В свое время я её решил, но есть два обязательных условия: 1. Во время этого эксперимента никто из заключённых не умрет; 2. Все заключённые умеют считать.
Верно
Считать достаточно уметь только счëтчику.
Всем остальным достаточно запомнить, что каждый включает лампочку самостоятельно только один раз за всë время.
Ну не знаю, насколько она прям сложная, я пока слушал БВ, без паузы придумал решение. Хотя может годы программирования дают о себе знать 😄, но идея ввести счётчик пришла сразу
Гений.
Решил за 5 минут Аж сам того не ожидал. В размышлениях шёл от обратного. У нас есть бинарная система вкл/выкл, а нужно посчитать 100 человек. Если каждый будет проверять значение в комнате, то нереально построить какую-то комбинацию всего из 2 значений. Тогда подумал, что только часть из них будет проверять. Но поскольку они не могут друг с другом общаться, проверяющий может быть только один. Ну и последнее - все остальные включают только 1 раз - уже было легко додуматься.
Неделю думал над задачей, сразу решение не пришло, потом пару раз вспоминал о должке, и так, во время чистки зубов, додумался наконец-то😅
Офигенная логическая задачка
Прикольно 😃
А что по времени жизни заключённых?
считается что они живут бесконечно долго
@@Alpac999 Не обязательно жить вечно. Достаточно жить, пока они в тюрьме. А это -- конечное время.
@@leonidrozenblum6880 конечное, но не известное заранее. Поэтому нужно жить бесконечно, иначе (если известно сколько они живут) экспериментатор придумает алгоритм как сделать чтобы они все умерли в тюрьме
@@Alpac999 У них организм может быть настроен не на бесконечное время, а только на то время, пока они находятся в тюрьме. Т.е. это все таки конечное (хоть и неизвестное) время.
@@leonidrozenblum6880 тогда экспериментатор может дождаться пока они умрут, а потом начать вызывать
Сразу понял, что нужно использовать счётчик
огонь-задача!!!
За первые 10 секунд после озвучивания условия придумал ответ. Изначально надо выключить лампочку и каждый человек если он ещё не включал лампочку и при этом лампочка не горит включает её, один человек считает количество включенных лампочек и каждый раз после себя выключает её
О, нифига, решение пришло почти сразу же после озвучивания условия
01.08.2023.
Узнал в день выпуска. Придумал сейчас. Решения по сути одинаковы.
Только "Счётчик" - "Избранный", включает свет только он, а другие в свое первое посещение его выключают и подсчёт ведётся по выключенным лампочкам.
Спасибо за задачу)
Боюсь, что к тому времени счётчика и его сокамерников уже съедят черви 😂
Охрана тюрьмы пару раз включила свет сама и парам-парам-пам :)
Догадался сам
элегантное решение. Нужно вводить счетчика)))))
Блин! Почти решил, совсем чуточку не докрутил. Стоило подумать на минуту дольше...
Привет! Был чемпионом по 10 заключённым. Задача была на элементах ру про 10 заключённых. Самая красота в выборах счетчика. Идея пришла независимо, на иностранных источниках её называют динамическим счетчиком для задачи на 100 заключённых. Красота моего решения была в ограниченном количестве заключённых. Выборы заканчиваются на 4 дня раньше. Иглобрюх довёл решение до абсолюта, спасибо, тебе, неизвестный друг!
Удалось довести до 92.39968 дня с первоначальных 120! С неофициалами можно довести на 0.0002-0.0003 лучше. Классная задачка, на пару выпусков тянет, с историей решений.
хорошая задача. можно не давать возможность выбора начального положения и задача все равно решаема, не намного сложнее.
Да )
все не так и трудно. горящая лампочка это "да" был один раз. негорящая я уже был. Вот и считай горящие
Реклама у Бориса Викторовича - это что-то новое
напомнило задачу про зеленые глаза и заключенных.
Надо подумать, а как лампочка помогает. Понять, что надо считать включенные (или наоборот выключенные, если сначала лампочка горит), понять, что считать в теории может только 1. А к этому моменту уже все поймут решение. Мы при заходе понимаем, что был заключенный новый или нет, а по лампочке мы понимаем горит или не горит, т.е. нужно задать соответствие между состоянием лампочки и новым побывавшим заключенным. Но раз задаем соответствие, то каждый включает 1 раз, но нам надо считать и бла бла бла и все короче.
крутая задача, я понял как решается после фразы о том, что есть один "счётчик"
Считаю это не совсем верным. Где счетчик, там всегда куча вариантов.
@@user-is3d21e3s имеется в виду, что счётчик один, а не все вкладывают немного в подсчёт, как я думал до этой фразы.
Задачка на программерскую смекалочку. Лаек😼
1:28
За один день привести 50 человек с интервалом в полчаса это, конечно, сильно :)
да норм. просто надо выбрать день, когда часы переводят
Ощущение, что надзирателям заняться больше нечем, как заключённых туда сюда перемещать
Странно, решение очень простое, а я к нему не пришел ни сегодня, ни годами ранее, когда впервые услышал задачку. С намека на счетчик сразу стало понятно, но блин
я видел формулировку где не известно начальное состояние лампочки.Эти 100 бедолаг собирались не в этой комнате , а где то еще в другом месте. Тут предполагается что лампочка выключена сразу.В таком виде задача очень простая.
Если не известно начальное состояние, то решение несильно усложняется. Все должны по два раза включать лампочку, тогда после 198 выключений все точно были хотя бы раз
@@trushinbv эти 198 учитывают возможный случай : счётчик оказался самым первым кто вообще зашёл в комнату и лампа там горит?
@@АлексейНеизвестный-ь6р да. Он после этого насчитает ещё 197. А это значит, что всех, кроме одного, он посчитает дважды
Супер! Спасибо!
В условие еще надо добавить, что они бессмертные. От сидения в одиночной камере ни у кого здоровья не прибавлялось пока. Счетчика выбрали, а он через месяц загнулся, и привет.
догадался, что считать включения выключения, но не сразу додумался до одного человека-счетчика
Не один
О, я тоже так додумался: каждый по разу включит, а какой-то один гасить будет. Конечно, так может много времени пройти, но тут время бесконечное. Только я не продвинутый программист, а больше математик.
И так прошло 30 лет и их всех освободили
Решение у меня такое же, только свет не включать, а выключать может один раз каждый заключенный. Так большинство заключённых будут сидеть в этой камере при свете, а это лучше чем без света😂
Интересно было б доказать что нельзя решить задачу быстрее чем за O(n^2)
Почему? Пронумеруем от 1 до 100, 1-ый "счётчик". Вначале заходит и включает второй, потом заходит и выключает первый. Затем также третий, потом опять первый. И того, мин время 2n, формально это вообще О(n)
@@mega_mango По условию задачи, приводят людей рандомно. Значит, кто-то может быть ни разу, а кто-то уже 10 раз. Конечно, если по условию каждый должен попасть хотя бы 1 раз к лампочке, то рано или поздно, это случится. Но в любом случае, в подобных задачах пренебрегают человеческим фактором тех, кто принимает решение выбора.
@@Андрейчикус а. Ага. Ну, я дэбик просто, я знаю что сложность алгоритма означает его самое долгое время выполнения, просто тут затупил что-то 😶
@@mega_mango если вероятность выбора каждого конкретного заключённого распределена равномерно -- то "счётчик" будет заходить в камеру каждый n-ый раз, и сделать это он должен n-1 раз. Вот и выходит что сложность n^2. Если попробовать смоделировать это программно то придётся использовать 2 цикла, что значит О (n^2) (если так нагляднее
Вы, вроде, не говорили о Наяальном состоянии лампочки. А раз так, то она изначально может быть включена, тогда счётчик может подсчитать первого заключённого за себя и таким образом на 99 счëт комнату посетят 98 человек
Было сказано, что они сами решают, каким будет начальное состояние
Как записать решение?
Кстати, не-счётчик может включить свет не в первый раз, когда свет не горит, а, например, в пятый. Главное, чтобы только один раз. Из-за него, правда, _все_ сидеть будут дольше.
Мое решение (пока что не смотрел ответ): выбираем одного человека. Он делает следующее: если лампочка включена, то он ничего не делает; если выключена, то включает и прибавляет к n единицу (в начале n = 0).
Остальные: если лампочка выключена, то ничего не делают. Если лампочка включена и они до этого ещё ее не выключали, то выключают. Если уже выключали до этого, то ничего не делают.
Таким образом все 99 людей выключат лампочку по одному разу. А тот исключительный человек включит 99 раз лампочку. Соответственно, когда будет 99 раз, то он может спокойно сказать, что все 100 заключённых были в этой камере.