Три задачки

[ankalagonblack]

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

Comments

[the_oldest]

1. А как же гномики? Решение просто помню.

[ankalagonblack]

Ненене, гномиков ставят в ряд так, чтобы они не видели предыдущих(и себя), но видели следующих :) А это господа А и Б.

[the_oldest]

Этих задач тысячи. В частности, господ я тоже в варианте гномиков решал первый раз.

[ankalagonblack]

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

[nedoearendil]

Можно ли уточнить про некоторые задачи?
Как в задаче 2 роботы проверяют встретились ли они? Программа завершается при встрече?
Допустимы ли составные вопросы ("если A и B, то ты ответишь да?") в задаче 3?

[nedoearendil]

Я бы сказал, что в языке メガメカ не хватает дополнительного условия для выхода из цикла.

[ankalagonblack]

Не понял тебя. Можешь привести программу на расширенном(с этим самым условием выхода из цикла) языке メガメカ, которой бы не было соответствующей программы на оригинальном メガメカ?

[the_oldest]

Я тоже сначала пошел по его пути. На расширенном как раз просто.

[the_oldest]

2. О, сообразил, наконец!

1 left
2 check
3 goto 1
4 left
5 left
6 goto 4

Можно сделать больше команд типа 4 и 5, тогда встретятся быстрее.

[the_oldest]

Действуем в предположении, разумеется, что между точками приземлений целое число шагов.

[ankalagonblack]

Встретиться не обязательно в тик, так что предположение можно и опустить:)

[ankalagonblack]

Хотя, формулировка "за конечное число тиков" и вправду неоднозначна. Имелось в виду "существует натуральное N такое что до N-го тика произошла встеча роботов". А можно было понять как "существует натуральное N, такое, что в N-й тик они встретились ."

[the_oldest]

3. Задача является чуть усложнённой версией задачи с рыцарем, лжецом и одним вопросом. Первые две интересней.

[ankalagonblack]

Не спорю:) Но, может, это только потому что мы нарешались таких задач?

[the_oldest]

Да уж, да уж.

[nedoearendil]

Полагаю, что чтобы выиграть с наибольшей вероятностью господину А и господину Б надо условиться, что один будет называть число которое увидел, а второй то, которое не увидел. Тогда у первого угадать вероятность 1/2, а у второго 1/4.
Если ответ не правилен, то не пиши правильный, ок?

[ankalagonblack]

Стратегия правильная у тебя, а вот следствия(ну, по поводу вероятностей - нет).

[nedoearendil]

Ну да, вероятность, что числа одинаковые - 1/2, разные тоже 1/2.

[ankalagonblack]

Да. Ну и чтобы подытожить - вероятность того, что второй не угадает, если не угадал первый - 0.