Тут загадывают и разгадывают загадки

 

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

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

Если будут заданы две загадки автор загадки, которая была позже заданной, ОБЯЗАН (!) стереть свою. В противном случае все последующие мессаджи будут являться флудом и подлежат уничтожению."

 

(с) Хентайщик

 

Приветствуются:

- авторские загадки, то есть придуманные Вами.

 

Не приветствуются:

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

- классические загадки. Задачу Эйнштейна тут уже несколько раз решали. Да, и на загадку сфинкса ответ известен.

Изменено 17 октября, 201014 г. пользователем Nox (смотреть историю редактирования)

Количество городов расположенных между городом, где живет Василиса и Конюшней - соответствует минимальной дозе которую необходимо дать ушастому...Далее повышать дозу на +1 город, пока не будет найден искомый (если с первого раза не вышло.)

Количество городов расположенных между городом, где живет Василиса и Конюшней - соответствует минимальной дозе которую необходимо дать ушастому...Далее повышать дозу на +1 город, пока не будет найден искомый (если с первого раза не вышло.)

В условиях задачи єтот метод отметается - написано, что Русь-матушка большая, и брутфорс не катит...

 

ЗЫ. Блин, и почему Баба Яга с Василисой не в Израиле живут?:) Или, ещё лучше, не в монако, или Андорре?:)

Аццкая задача... =__=

Пока только два пути решения этой задачи предполагаю. Первый - локализация участка списка, на котором вероятность появления искомых объектов максимальна. Но про принцип расположения городов в нём нам абсолютно ничего не известно, значит, по василисиной и бабкиной вероятности список однороден, способ не подходит. Раз так, Ивану надо исхитриться за одну ходку успевать проверять более одного города. Но тут техническое ограничение наложено на коня, а вторым ходом Иван должен вернуться, чтоб царя не злить. Значит, этот способ тоже не подходит. Никакая хитрая система выбора следующего города для просмотра преимуществ не даст, потому что как ни тыкайся - всё равно больше 1/N вероятности попадания не получим. Либо что-то упускаю, либо одно из двух.

Makoto, может подскажешь что-нибудь?

Мне кажется странным, но...

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

Возьмем город k < N/2... Тогда, чтобы попасть в него нужно зохавать k дури... А чтобы попасть в город 2k нужно зохавать 2k дури, нэ?

Но тогда, чтобы попасть из города k в город 2k мы не знаем, сколько нужно чего зохавать, так как достоверно известно, что зохавав k дури мы попадаем в 0...

Получается, что для каждого города остальные города упорядочены по-своему?

Прошу прощения, /me тупой

Изменено 4 февраля, 200817 г. пользователем Ayanami-kun (смотреть историю редактирования)

Поиск в несортированном множестве имеет сложность порядка N. Тут даже нельзя определить отношение больше-меньше, так как в "двусвязном списке" хранятся булевские переменные (true/false - есть Василиса или нет). Поэтому можно сократить число гиперпрыжков, в 1.5 - 2 раза, если царю показываться через сутки, например (двое, трое и т.д. - чем больше промежуток, тем быстрее).

 

Если все это неверно, присоединюсь к Shinsaku-To - подсказочку бы...

Makoto, в таком случае делаем так - если "встречаются" города василисы и бабы яги. В том городе, который оказывается ниже, т. е. в который Ванёк смог попасть, благодаря камням система остаётся такой же, а во втором городе она меняется. Т.е. идёт в плюс. Соответственно, если конюшня встречается с искомым городом, то системы меняются у обоих городов. Конюшня идёт в минус, т.е. N-1, N-2 и т.д. а найденный город в плюс :huh:

Так что, если не ошибаюсь, в самом "пиковом" случае - придётся перелопатить только 2/3 городов.

 

Не, если я правильно понял вашу мысль, то если мы сдвинем на предыдущей картинке бабку и Василису против часовой стрелки, то всё равно найдём такое их расположение, что придётся делать N гиперпрыжков, даже если по какой-то хитрой схеме менять схему движения из каждого города.

 

Но тут техническое ограничение наложено на коня, а вторым ходом Иван должен вернуться, чтоб царя не злить.

 

Ну, в общем-то, Ваня может поднапрячь Горбунка и выкраивать по недельке свободной от заданий царских - это Ваня тоже в расчёт берёт. Но всё равно все N городов (при наихудшем раскладе) обскакивать - тяжко :(.

 

 

Поиск в несортированном множестве имеет сложность порядка N. Тут даже нельзя определить отношение больше-меньше, так как в "двусвязном списке" хранятся булевские переменные (true/false - есть Василиса или нет).

 

(буду потихоньку давать подсказки)

Пришлось бы Ваньке действительно через все N городов Русских скакать, если бы он знал лишь, что есть на Руси город дивный, в котором живёт красавица чудная. Да такая, что ни в сказке сказать, ни пером описать, и звать её Василиса-прекрасная.

Но повезло Ваньке, ох повезло - рядом живёт его ненаглядная. Можно сказать, рукой подать. То подарок судьбы невероятный, в отыскании лошадиной дозы крайне пользительный.

 

И есть среди людей добрых, вызвавшихся помочь Ивану, мудрец один, и зовут его asc. Мыслит он в направлении нужном, принимая подарок этот судьбы невероятный во внимание. Идею бы его развить, расширить, да ещё хитрость маленькую применить - и не мотаться Ивану по земле Русской до старческих седин.

Изменено 4 февраля, 200817 г. пользователем Makoto (смотреть историю редактирования)

Допустим, съедает конь одну таблетку, и оказывается Иван в соседней деревне.

На следующий день коню дают две таблетки. И т.д. Все города отмечаются на карте и соединяются линией.

Через несколько дней Иван сможет начертить приблизительный график, по которому отмечены города (т.е, в какую сторону идёт отсчёт). Если отсчёт идёт по направлению к Василисе, то можно прикинуть примерное до неё расстояние (по верстам, или по количеству населенных пунктов), и методом научного тыка постепенно приблизиться к резкльтату. Если же Василиса живёт в другую сторону, то тогда начинаем кормить коня более плотно, начиная с почти полной ложки, и так, пока не дойдёт до Василисы.

 

Это при условии, что она рядом живёт.

G.K., она рядом географически, а в "гиперпространстве" может быть где угодно.

Ммм, сейчас голова болит, думаю не сильно чётко, но, учитывая переезд по земле, возможно так: поиск вести из двух точек, то есть с конюшни и из города Василисы. Просмотреть несколько случайных городов оттуда, пототом несколько городов отсюда. Ну и вести при этом учёт посещённых мест. И так до тех пор, пока не попадёт на какой-нибудь город дважды. Зная, сколько закинул в коня при прыжке из столицы и сколько из василисиной малой родины, - получит Иван все данные для прямого перемещения между работой и семьёй.

Адекватно оценить сейчас этот хитровыверт по указанной причине не могу, так что извините, ежели туплю.

Изменено 4 февраля, 200817 г. пользователем Shinsaku-To (смотреть историю редактирования)

Shinsaku-To, вооооо, пошли интересные мысли. Правда, именно эту идею высказывал asc в своём #6347, на что я ответил в #6350.

Изменено 4 февраля, 200817 г. пользователем Makoto (смотреть историю редактирования)

Хы, гоменнасаи и сумимасены, пропустил этот кусочек темы. Матожидание можно не считать. Если пренебречь затратами времени на шатание между конюшней и Василисой (бабкой), то эффективность метода будет в худшем случае не меньшая, чем при поиске из одного пункта. Хотя в лучшем не большая, но посерединке выигрыш в вероятности получим =)

Кстати, фразу про "простого парня" надо понимать в том ключе, что повышение вероятности успеха на каждом отдельном тыке нам не годится, а ответом будет только алгоритм, устойчивый по максимальному числу шагов? :)

Изменено 4 февраля, 200817 г. пользователем Shinsaku-To (смотреть историю редактирования)

Shinsaku-To а ответом будет только алгоритм, устойчивый по максимальному числу шагов?

 

Да, есть способ верный, сокращающий скитания по городам Русским значительно.

 

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

Изменено 4 февраля, 200817 г. пользователем Makoto (смотреть историю редактирования)

Игра есть дивная, древняя, “Star control II: the Ur-Quan masters” называемая. И мест в ней можно посетить видимо-невидимо:

http://www.imagehost.ro/thumbnail.php/0501020747a7996f376e8.png[/img]

каждая точечка - звезда; вокруг одних немного планет вращается, вокруг других - поболе. И коль планета необитаема, высадиться на шаттле на нее можно, да ресурсы пособирать: иногда за один раз все собрать можно, а иной раз, если планета богата, много раз высаживаться надо. При том это мероприятие весьма рискованным быть может: тут тебе молнией шарахнет, где-то землетрясение весьма сильное, а еще, на планете температура дюже высока бывает. Ресурсы ценность имеют разную, но на базе, при переработке, все в единый числовой показатель хитро пересчитываются.

И вот какие карты люди делают:

http://www.imagehost.ro/thumbnail.php/0501443247a7a360a9cee.gif[/img]

карта сия показывает сколько ресурсов (в этом самом числовом показателе) с планет какой звезды собрать можно.

Дайте месяц, дайте два, дайте год!..

 

То присказка была, а теперь сказка:

 

Долго ли, коротко ли сидел Иван призадумавшись да решил, наконец, что будет он из двух городов на Горбунке вылетать: раз из конюшни своей, раз от Василисы. Причем, от Василисы вылетать по простой методе: в первый раз скормить одну гранулу, второй - две, следующий раз - три, и так далее. Смекнул Иван, что скормив в конюшне своему скакуну половину гранул из Ложки, и записав город, в который тот отнесет - иначе говоря - "поставив метку", он вдвое уменьшит время перебора.

http://www.imagehost.ro/thumbnail.php/0503194447a7b9b0afb08.png[/img]

А ведь метки можно ставить еще и еще! Следующий раз, вылетая из конюшни, отсыпать Горбунку четверть гранул, а остольное - в карман. Потом, напротив, четверть - в карман, остальное - коню, и т. п.

http://www.imagehost.ro/thumbnail.php/0503300347a7bc1bb1740.png[/img]

И так, пока не сойдется путь, откладываемый от Василисы, с одной из меток.

А потом и с Ягой можно будет разобраться тем же образом - благо, меток уже много будет.

Эх, вспомнить бы теперь, как тот город незнакомый назывался?..

Твою дивизию, точно. Я дурак =___=.

*Тоном Осаки *Ааа? Бинари сеарч? Я ведь думал об этом... только не придумал реализацию...

e^cha, всё правильно. Задачка для Ваньки заметно упрощается, если ввести жёсткую сетку из собственных меток. Можно заранее её построить, а потом уже приниматься за поиски; можно, действительно, и в процессе. Только в последнем случае надобно ещё запоминать, какие города попались по пути от Василисы, а то ненароком можно сгоряча пару меток проскочить, верно?

 

[маленькая справка для любопытных]

 

Помимо старконтрола, данная задача достаточно известна в дискретной математике, которая лежит в основе всей криптографии. Там эта задача называется . Очень широко используется в ассиметричных системах шифрования (с открытым ключом) и системах цифровой подписи. В частности, она лежит в основе [url="http://ru.wikipedia.org/wiki/Схема_Эль-Гамаля" target="_blank" rel="nofollow">схемы цифровой подписи Эль-Гамаля (стандарты электронной цифровой подписи в США и России базируются именно на ней) и .

 

В общем, дело это серьёзное и на болших бабках замешанное, а потому умы учёные привлекающее изрядно. Например, для вышеуказанных алгоритмов народ сообразил, как считать логарифмы не с экспоненциальной сложностью (т.е. когда время выполнения алгоритма растёт экспоненциально вместе с длиной ключа шифрования: время=O(e^m), m - число бит в ключе), а с субэкспоненциальной (т.е. вместе с увеличением количества бит в ключе скорость растёт медленнее, чем в экспоненциальных алгоритмах, но всё же быстрее, чем в полиномиальных, для которых время выполнения выражается некоторым многочленом от m, например m^8+m^5+m^2+1).

Естественно, не всем такая лазейка, ускорению способствующая, нравится, и народ изголяется с нечисловыми структурами типа [url="http://ru.wikipedia.org/wiki/Эллиптическая_кривая" target="_blank" rel="nofollow">эллиптических кривых. Там, увы, ничего умнее экспоненциальных алгоритмов придумать пока не получилось.

 

Идея, озвученная камрадом e^cha, лежит в основе алгоритма Шенкса (он же "baby-step giant-step") для логарифмирования в цикловых структурах любого вида. Он имеет сложность О(sqrt(N))=O(e^m/2). А точнее, количество опробований при самом худшем случае = 2*sqrt(N): сначала мы делаем sqrt(N) меток в городах, а потом нам придётся сделать ещё sqrt(N) шагов до ближайшей метки от Василисы. И, хоть для поломания цифровой подписи такая скорость всё равно никуда не годится (алгоритм экспоненциальный), но для Ваньки вполне подходит: например, если в России 10000 городов, то Ване нужно обскакать только 200: 100 меток и ещё 100 городов до ближайшей метки. И это в самом худшем случае. А там, видит Бог, повезёт Ваньке как всегда, да и не 200 раз надо будет ему Горбунка понапрасну по Земле Русской гонять :lol:.

 

Кстати, ежели заготовить метки заранее, как предлагает камрад Шенкс, то можно сэкономить не только время, но и бересту казённую примерно вдвое, чем ежели ставить их на ходу и записывать и метки и города от Василисы. Мелочь, а приятно.

 

[/маленькая справка для любопытных]

 

e^cha, загадывай.

Изменено 5 февраля, 200817 г. пользователем Makoto (смотреть историю редактирования)

[offtop]

За каким-то чёртом ночью написал в билдере программку, которая считает вероятность удачного окончания поиска на шаге m при рандомном поиске из одной точки, и при ранодомном поиске из двух точек. Вбиваем число городов русских, сколько Иван просматривает из одного города перед переездом в другой и сколько всего уже просмотрели. Зелёным выводит рузультат для двух, красным - для одногородового поиска. Иногда разница очень весомая, до пары порядков.

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

[/offtop]

IvanVsTeorver.zip

Ясно, в общем как обычно, "чукча не писатель, чукча - читатель" -_-.

Думаю, загадывать может кто угодно.

Изменено 7 февраля, 200817 г. пользователем Makoto (смотреть историю редактирования)

Подавляющее большинство героев этой книги (если не все) имеют реальные прототипы, хотя все события в книге вымышлены.

 

Так сложилось, что о внешнем виде героев книги в разных странах представления могут быть разные, причём, на западе эти представления, как правило, более приближены к прототипам, чем, скажем, в странах СНГ.

 

Что за книга?

Винни-Пух?

Маленький принц? о_О

Винни-Пух?

Придётся тебе стать писателем:) Загадывай:)

Продолжение загадки про Ивана-дурака и Чудо-Траву.

 

Во время очередного Слёта Волшебников и Чародеев Земли Русской, пожаловал на него гость заморский, маг известный. И, в порядке обмена опытом, презентовал Бабе Яге и Кощею Бессмертному свиток магический, содержащий заклинание Метеоритного Дождя. Презентовал его сразу двоим в целях создания коллективной ответственности. Понимал мудрый маг, что каждый, владея таким заклинанием единолично, множество бед способен причинить простому люду.

 

Вручить-то он его вручил, и оба Великих кудесника Земли Русской успешно его опробовали по возвращении на специальном магическом полигоне. Только что же дальше со свитком этим делать? Где хранить - не сидеть же над ним всю оставшуюся жизнь вместе? Нельзя оставить у Кащея в замке - Баба Яга последний зуб даёт, что тот, заполучив в единоличное пользоване такой артефакт, снова пустится чинить козни Русскому народу. Кащей тоже Бабе Яге не верит - та чуть что, непременно сдаст заклинание очередному доброму молодцу, снарядившемуся освобождать Землю Русскую от "Гнёта Кащеева" (известную слабость питала Баба Яга к добрым молодцам) а ему, Кащею-угнетателю, расхлёбывать, да за нанесённый казённым землям ущерб перед Царём ответ держать. Царю же такой свиток также давать опасно - был он мужик боевой, чего глядишь, почуяв силу, на соседних князей войной пойдёт, а с таким заклинанием в руках грозит такая война страшными бедами всему народу Русскому.

Долго они сидели в башне магии у Бабы Яги, думали думу тяжёлую. Но как ни обдумывали, никак не получалось ни на кого положиться и никак спрятать свиток окаянный, чтобы никто единолично, без согласия другого, не мог им воспользоваться.

 

А тут вдруг Иван пожаловал, за новой порцией Чудо-Травы. И Баба Яга, пребывая в пущей злости от безвыходности положения с заклинанием, возьми да и скажи ему: "Не будет тебе, Ванюша, Чудо-Травы, покуда не придумаешь как нам свиток окаянный так спрятать, чтобы никто из нас двоих не смог им воспользоваться без ведома и согласия другого."

 

"Вот так так!" - подумал Иван. "И как же мне теперь к Василисе наведываться?"

 

Действительно, как бы Ивану и его верному Коньку-горбунку так изловчиться, чтобы разрешить проблему чародейскую, ну и благосклонность Бабы Яги, соответственно, возвратить - совсем ему тяжко станет без Чудо-Травы.

Изменено 10 февраля, 200817 г. пользователем Makoto (смотреть историю редактирования)

(Чувствую, ненароком загнул последний раз задачку "на базу нетривиальных знаний". Перезагадал - смотрите предыдущий пост #6373)

Изменено 10 февраля, 200817 г. пользователем Makoto (смотреть историю редактирования)

Я так понял, резать свиток нельзя?

 

Тогда варианты:

 

1) Отдать свиток Василисе. она ж премудрая, глупостей не наделает.

2) Закопать на острове-буяне.

3) Отдать безграмотному человеку (не все ж на Руси читать умели до электрификации всей страны)

 

Список можно продолжать - если думаю в ту степь - подтверди, буду дальше думать. Если не в ту - буду думать в другую сторону:lol:

Порвать на две половинки каждый свиток. И пусть у Яги и у Кащея по две одинаковых половинки будет. Нужна вторая - иди к коллеге на поклон.