Задача для реальных пацанов

[SailorMoon]

Поймал огр-маг 100 гномов. У каждого есть порядковый номер от 1 до 100 (имя как бы).

Огр сделал 100 сундуков (они тоже пронумерованы) и в каждый положил число от 1 до 100, притом числа не повторяются и каждое встречается 1 раз.

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

Гномы могут договорится до того, как начнётся "эксперимент". Перед "экспериментом" все гномы изолируются и с этого момента не получают никакой (вообще никакой информации), о том, кто из гномов какие чемоданы открывал, в каком порядке они открывали сундуки, в каком порядке огр пускал гномов в комнату с сундуками, с какого раза кто угадал и так далее.

Требуется найти оптимальную стратегию для гномов и оценить (весьма трудно посчитать её точно) вероятность, с которой смогут выжить гномы.

 

Задача без подъёбов (гномы не обладают телепатией, у них рентгеновских очков, они не могут уебать огру с прогиба, они не могут сыграть с ним в доту, трахнуть его, среди них нет Чака Норриса, огра невозможно наебать)

 

-----------------------------------------------------------------------------------------------

 

Пишу решение. Буду рад, если кому-то не похуй.

 

Стратегия: гном заходит, открывает сундук со своим номером и далее открывает сундук, номер которого совпадает с только что найденным числом. (например, зашёл 2 гном, открыл 2ой сундук, нашёл там число "29", открыл сундук 29, нашёл там "94", открыл сундук 94 и тд)

Вот решение:

У нас есть 100 пронумерованных сундуков, и в каждом есть число от 1 до 100. Построим ориентированный граф (обычный граф, только у него на рёбрах ещё стрелочки) слежующим образом: от каждого сундука проведём стрелочку к тому сундуку, номер которого совпадает с числом, лежащим в нём (то есть если в 26 сундуке лежит число 58, то в нашем графе будет идти стрелочка от точки 26 к точке 58).

Что мы можем сказать про этот граф? От каждой его точки будет выходить одна стрелочка и в каждую точку будет приходить одна стрелочка. Отсюда следует, что этот граф будет иметь циклы, причём каждая точка данного графа будет принадлежать какому-нибудь циклу.

Как многие, наверное, уже догадались, движение "гнома по сундукам" описывается стрелочками в графе, то есть стрелочка указывает на тот сундук, который откроет гном после открытия заданного.

Также заметим, что искомый гномом сундук будет находится в том же цикле, что и сундук с его номером и чтобы добраться до него, необходимо пройти по всему циклу (потому что искомый сундук как раз указывает на сундук с номером гнома), причём если длина цикла будет <= 50, то гном "успеет" найти то, что нужно.

Таким образом, если есть хоть один цикл, в котором больше 50 сундуков, то стратегия провальна, а если нет, то она спасает всех сразу.

А если посчитать количество графов, подходящих условию, в которых нету циклов больше 50, то получится что их ~32%. Возьмите конфетку тот, кто дочитал до сюда yes

[NN_1]

заебали

[Tmn.Steam]

заебали

[DISK-mGN]

Поймал огр-маг 100 гномов. У каждого есть порядковый номер от 1 до 100 (имя как бы).

 

дальше не читал :._.:

[SailorMoon]

заебали

Уж не маму ли твою?

[kondrat]

можно поставить вард

[Гость Venomancer]

Я зарабатываю 300$ в интернете на огрочек хватает.

[Tmn.Steam]

можно поставить вард

НС научит 

[Jes]

Я зарабатываю 300$

[Дэфрэл]

они не могут уебать огру с прогиба, они не могут сыграть с ним в доту, трахнуть его, среди них нет Чака Норриса, огра невозможно наебать)

[Yak]

какая тут нахуй стратегия если у первого же гнома щанс проебаться 50% полюбому

[NabaT]

Требуется найти оптимальную стратегию для гномов и оценить (весьма трудно посчитать её точно) вероятность, с которой смогут выжить гномы.

думаю, что аффтар сам нефега не знает ответа

[eso.falex]

заебали уже со своими гномами

[D.I.T.C.]

заебали

[666eViL666]

можно поставить вард

[SailorMoon]

Требуется найти оптимальную стратегию для гномов и оценить (весьма трудно посчитать её точно) вероятность, с которой смогут выжить гномы.

думаю, что аффтар сам нефега не знает ответа

Я знаю, могу сразу сказать, что есть стратегия, действуя по которой вероятность остаться в живых ~30%

[Tmn.Steam]

можно поставить вард

А ТЫ СЛУЧАЙНО НЕ ИЗ 99 ДОТА РУМ? НЕ ЗНАЕШЬ 777DEMON777 или VASYA.84RUS.PRO ???????

[Jes]

Требуется найти оптимальную стратегию для гномов и оценить (весьма трудно посчитать её точно) вероятность, с которой смогут выжить гномы.

думаю, что аффтар сам нефега не знает ответа

Я знаю, могу сразу сказать, что есть стратегия, действуя по которой вероятность остаться в живых ~30%

нахуй такие задачи в которых могут погибнуть гномы 

 

автор 

 

 

[Whatsup]

1.один гном должен задать вопрос.

"огр , а почему у тебя 2 головы , а среш ты из одной жопы?"

пока он будет думать все 100 гномов съябывают по норам , профит.

 

2.Гномы включают бкб , становится невоспримчивым к заклинанию "сожрать и высрать"

пока огр нахуячит нескольких с руки , гномы съебут по норам. профит.

 

3.Гном скажет огру "хантер иди лучше бигмак съеш , а то налепил костюм огра на хелуин"

Хантер растроится изза того что он жырный . а гномы съебутся. профит.

[Гость Venomancer]

Требуется найти оптимальную стратегию для гномов и оценить (весьма трудно посчитать её точно) вероятность, с которой смогут выжить гномы.

думаю, что аффтар сам нефега не знает ответа

Я знаю, могу сразу сказать, что есть стратегия, действуя по которой вероятность остаться в живых ~30%

Предложи гномам свои услуги за 300$ заработать в интернете.