15:50 

Akiza Nadesico
Взлетное поле фантазии.
Наткнулась в интернете на любопытную задачку. У неё есть 3 режима - easy, normal and hard
Общее условие: Какие-то страшные тёмные силы (видать КГБ) поймали группу эльфов и заточили по одиночным камерам. В день поимки им объяснили, что их будут допрашивать в отдельной комнате, и в тот момент у эльфов был шанс договориться как действовать. В комнату могут приводить эльфов совершенно случайно, хоть одного и того же 100 раз подряд. Никто не может никак связаться с другими. Эльфы заметили, что в комнате есть лампочка, до которой никому нет дела, её можно по желанию включить или выключить. Надо учесть, что эльфы бессмертны и может пройти сколько угодно дней, пока они не примут решение. Им обещали, что всех выпустят, если:

easy - если кто-то скажет, что уже все побывали в этой комнате. Если сказавший ошибся и побывали в комнате не все, то всех тут же убивают, но если всё верно, то выпускают.
на это найти решение очень легко

normal - условие то же, но выпускают по одному. То есть каждого в отдельности, кто сказал, что в камере побывали все (то есть каждый должен сказать отдельно, что пора ему освободиться). Если ошбка, то смертная казнь сразу для всех.

hard - предыдущее условие, но при этом охранник может выключить лампочку в любой момент, случайным образом, если заметит. Как быть?

URL
Комментарии
2015-10-21 в 18:50 

Линда Кайе
Тотальная неудачница и убийца жёстких дисков.
По easy ничего не приходит в голову кроме как рассчитать по теории вероятности сколько времени потребуется, чтобы все побывали на допросе, выждать этот период и сказать на удачу ^^' Что-то ничего больше в голову не приходит ^^'

2015-10-21 в 19:52 

Akiza Nadesico
Взлетное поле фантазии.
Решение легкого уровня.

По easy, на самом деле надо назначить одного выключающего. Все будут только включать, а он только выключать и считать сколько раз выключил. Каждый может включить лампочку только 1 раз, если она выключена.

Другие варианты сложнее. Но они аналогичны работе компьютера с памятью в 1 байт )

URL
2015-10-21 в 20:40 

PsiRat
Хаос в массы !!!
Akiza Nadesico,
Ещё проще. У лампочки кроме состояний вкл-выкл есть ещё другие состояния :) Она может быть ещё и горячей-холодной.
Итог - один включает и не выключает, второй включает и выключает по уходу, третий не трогает. Нужно всего-лишь собрать недостающие состояния. Первому достаточно застать тёплую и холодную выключенную лампу. (уровень изи пройден). Второму включённую и холодную. Третьему включённую и тёплую. Если увидел один - увидели все. Для уверенности - увидеть дважды первоначальное состояние лампочки. (нормал пройден).
Теперь интересней. У лампочки есть ещё одно состояние, которое уже перманентное. Потому, второй, заведующий теплой лампочкой, застав пару раз состояние вкл и холодное, просто её разбивает. (квест комплит).

2015-10-21 в 20:47 

Akiza Nadesico
Взлетное поле фантазии.
PsiRat, а если в группе 50 эльфов?

URL
2015-10-21 в 20:49 

PsiRat
Хаос в массы !!!
Akiza Nadesico, не учёл )

2015-10-21 в 20:59 

PsiRat
Хаос в массы !!!
Akiza Nadesico,
Ну тогда да. Считать. В первом варианте просто считать. Во втором считать и в конце раздолбать лампу. В третьем варианте считать ещё и погашенные горячие. Хотя не, третий вариант поизощрённей будет.

2015-10-21 в 21:03 

PsiRat
Хаос в массы !!!
Akiza Nadesico,
А, придумал. В харде просто доп условие для всех включателей добавляется. Если лампа тёплая, нужно оставить её теплой и не включать свою. Проверять, даже если уже включал.

2015-10-21 в 22:20 

Akiza Nadesico
Взлетное поле фантазии.
PsiRat, я позже отвечу, пока что не смотрела ответы, хочется самой додуматься. Лампа всего одна, думаю, что в условии подразумевалось, что надо пользоваться лишь 1 битом информации, ведь если в камеру приводят эльфа раз в день, то лампа уже не может быть тёплой.

URL
2015-10-21 в 22:57 

PsiRat
Хаос в массы !!!
Akiza Nadesico, Но про это не сказано :) Про время привождения и перерывы между ними ни слова ) Значит, мы можем использовать это в свою пользу )

2015-10-22 в 02:44 

Линда Кайе
Тотальная неудачница и убийца жёстких дисков.
Akiza Nadesico

Ух, что-то не додумалась ^^'

2015-10-22 в 14:46 

Akiza Nadesico
Взлетное поле фантазии.
Для normal сначала всё то же самое, что и для легкого, но эльфу, который выключает лампочку, надо будет передать информацию всем остальным. Остальные должны и сами для освобождения поработать, а именно, тоже считать, по возможности, когда застанут, смены включеных и выключеных лампочек. Ведущий эльф, который первым поймет, что в комнате побывал каждый, при последующих посещениях начинает чередовать включения и выключения. Это позволить остальным насчитать периодов не менее чем есть заключенных и определиться с решением (рано или поздно, каждый наверстает все фазы, которые оказались пропущенными).
Далее, каждый кто определился, может сообщить ведущему о себе, выключив лампу, когда она будет включена. Раз уж теперь её включает только ведущий, он сможет сосчитать количество вышедших и выйти последним, с уверенностью, что никого не забыли.

URL
2015-10-22 в 16:02 

Akiza Nadesico
Взлетное поле фантазии.
PsiRat, если относиться к ситуации как к реальной, а не идеализированной задаче, то конечно, можно всё сделать проще, можно, например, завязывать волосинку на проводе лампы, а для подстраховки клеить козявку под крышку стола ^^'

URL
2015-10-22 в 20:34 

Akiza Nadesico
Взлетное поле фантазии.
Не оптимально, но и хард решила.

Итак, хард.
Это получится долгим, но всё же. Поскольку, охранники лишь изредка выключают лампочку, но не балуются и не включают, значит передавать информацию придется лишь включеным состоянием. Одно включение на каждого не годится, следовательно, необходимо условиться о какой-нибудь цикличности.
Пусть цикл будет равен количеству эльфов (число дней после которых цикл повторится). Тогда первый приведенный в комнату решает, что он первый и включает лампу, если попадет, в первый день каждого цикла.
Во второй день приведенный так же легко может назначить себя вторым, т.к. до него мог быть только один. Он будет включать только по вторым дням каждый цикл, и по первым, если попадет в такие дни, ведь он точно знает, что был кто-то первый, а он другой.
Если случилось так, что и во второй день попал первый, он лампочку не включает.
Далее, третий может признать себя третьим, если уверен, что до него было два разных эльфа. Соответственно, если он увидел выключенную лампочку, то не присваевает себе номер и ждёт следующего цикла. Если всё прошло гладко, третий запоминает номер и если попадает в любой из дней в котором он уверен, включает лампочку.
В следующем цикле в первый день лампочку включит любой, кто бы ни попал в этот день. Второй тоже включит лампочку, а третий поступит так же как предыдущий третий: если застал лампочку включенной, оставит; если выключенной, включать не будет. Если в третий день попадет первый или второй, они выключат лампу, дав знать, что пошел повтор. Но если это оказывается третий предыдущего цикла, который знает, что до него было двое разных, в любом случае он оставляет лампочку включеной.
Итак, каждый цикл эльфы будут постепено продвигаться вперёд. Каждый кто видел лампочку включеной, может впредь включать её в тот же день, во все дни до или на следующий после запомненной лампочки.
Рано или поздно ряд включеных лампочек дойдет до конечной позиции. Тогда каждый, кто попадает в последний день знает, что все уже побывали в камере.
Далее, если есть условие, что эльфов отпускают одновремено, когда накопится 100% верных ответов, все просто продолжают своё дело и ждут, когда их выпустят. Если, назвавшего верный ответ, отпускают сразу, всё равно, рано или поздно, каждый дойдет до конца. Но, в принципе, можно выходить не сразу, а через какое- то время, что обеспечит товарищам лучшую статистику и скорейшее освобождение.

URL
2015-10-22 в 20:54 

Akiza Nadesico
Взлетное поле фантазии.
А теперь ссылки на оригинал. Право, надо было перечитать, прежде чем воспроизводить условие по памяти. На хабре красочнее описано и с полезными уточнениями.
m.habrahabr.ru/post/69642/

В комментариях есть несколько иные решения, но что-то они мне кажутся более медленными. Но не проверяла на эмуляции ^^'

URL
2015-10-23 в 02:55 

Линда Кайе
Тотальная неудачница и убийца жёстких дисков.
/* В общем, самый простой вариант - определить таймаут и сдаться по его наступлению ^^' */

2015-10-24 в 01:14 

Akiza Nadesico
Взлетное поле фантазии.
На самом деле, на сложном мой алгоритм плох при условии злой воли охранников, если бы они кого-то не выбирали вовсе, например, до статысячного дня. Вернее, он мог бы быть хорош, но внутренняя логика на все шаги не проработана. Вначале то она проста, но далее сложнее. Как ни печально, я не додумалась до идеального решения, хоть оно и рабочее в нормальной ситуации.

URL
2015-10-24 в 01:28 

Akiza Nadesico
Взлетное поле фантазии.
Линда Кайе, если верить простому распределению, то да, время само всё решит )

URL
2015-10-24 в 10:57 

Линда Кайе
Тотальная неудачница и убийца жёстких дисков.
Как ни печально, я не додумалась до идеального решения

Get the facts! Ты додумалась до всех решений, в отличие от ^^'

     

Aki neko nikki

главная