Три задачки
В пятницу прошла встреча с двумя приехавшими издалека подругами - Хэллот и Летицией. Во время встречи Летиция, Антон и я озвучили по одной задачке. Задачки известные и несложные, но могут подойти для разминки мозга в первый день рабочей недели.
Задача #1:
Во вторник с господином A и господином Б будет проделана следующая странная процедура: каждому из них на голову наденут шапки, на каждой шапке будет написано одно число, "1" или "2". Числа никак друг-от-друга не зависят. Каждый из них увидит, что написано на шапке другого, но будет без понятия о том, что написано на его шапке. После этого их разведут по разным комнатам, так что они не смогут ни слышать ни видеть друг-друга. В комнатах они должны будут назвать число. Если хотя бы один из них назовет число, которое написано у него на шапке, они победили, и им выдают по книжке Смаллиана. Если же нет - заставляют смотреть передачи про НЛО по каналу ТВ-3. В понедельник им дают договориться о стратегии, с которой они будут действовать во вторник. Какой же должна быть эта стратегия, чтобы не смотреть ТВ-3.
Задача #2:
В бесконечно длинную прямую траншею на парашютах десантируются 2 робота. Во время приземления роботы смотрят в одну сторону, перпендикулярно траншее. Траншея узкая и только-только вмещает робота. После приземления парашют каждого робота остается на том месте, куда данный робот приземлился. Роботы содержат в себе интерпретатор простенького языка メガメカ, состоящего из 4-х команд. Каждая поманда располагается на своей строке. Каждая строка имеет свой номер. Пустых строк нет. Команды такие:
left - роботу пойти влево на шаг, интерпретатору перейти на следующую строку;
right - роботу пойти вправо на шаг, интерпретатору перейти на следующую строку;
goto x - интерпретатору перейти на строку с номером x;
check - проверить, есть ли парашют под роботом. Если да - интерпретатору перепрыгнуть через следующую строку. Если нет - просто перейти на следующую строку.
Исполнение каждой команды занимает один тик. Если интерпретатор пытается перейти на строку за пределами программы, программа на следующем тике заканчивает свое исполнение. Длина шага у роботов одинакова. Роботы приземляются единовременно и тут же начинают исполнение своих программ. Роботы после приземления оказываются на расстоянии целого числа шагов друг-от-друга.
Существует ли программа на языке メガメカ такая, что если перед десантированием загрузить ее в оба робота, они встретятся за конечное число тиков? Если да, то приведите ее листинг:)
Задача #3:
Есть две двери, перед каждой из них стоит стражник. За одной дверью - еще одна книжка Смаллиана. За другой - ничего. Каждый из стражников может быть одного из 3-х типов:
рыцарь - всегда говорит правду
лжец - всегда говорит ложь
хитрец - по очереди(т.е. меняя состояние после каждого заданного ему вопроса) говорит правду/ложь, но неизвестно, с чего именно начинает.
Стражникам можно задавать вопросы, ответом на которые является "да" или "нет". Можно ли за два таких вопроса узнать, за какой дверью книжка? Если да, то как?
Задача #1:
Во вторник с господином A и господином Б будет проделана следующая странная процедура: каждому из них на голову наденут шапки, на каждой шапке будет написано одно число, "1" или "2". Числа никак друг-от-друга не зависят. Каждый из них увидит, что написано на шапке другого, но будет без понятия о том, что написано на его шапке. После этого их разведут по разным комнатам, так что они не смогут ни слышать ни видеть друг-друга. В комнатах они должны будут назвать число. Если хотя бы один из них назовет число, которое написано у него на шапке, они победили, и им выдают по книжке Смаллиана. Если же нет - заставляют смотреть передачи про НЛО по каналу ТВ-3. В понедельник им дают договориться о стратегии, с которой они будут действовать во вторник. Какой же должна быть эта стратегия, чтобы не смотреть ТВ-3.
Задача #2:
В бесконечно длинную прямую траншею на парашютах десантируются 2 робота. Во время приземления роботы смотрят в одну сторону, перпендикулярно траншее. Траншея узкая и только-только вмещает робота. После приземления парашют каждого робота остается на том месте, куда данный робот приземлился. Роботы содержат в себе интерпретатор простенького языка メガメカ, состоящего из 4-х команд. Каждая поманда располагается на своей строке. Каждая строка имеет свой номер. Пустых строк нет. Команды такие:
left - роботу пойти влево на шаг, интерпретатору перейти на следующую строку;
right - роботу пойти вправо на шаг, интерпретатору перейти на следующую строку;
goto x - интерпретатору перейти на строку с номером x;
check - проверить, есть ли парашют под роботом. Если да - интерпретатору перепрыгнуть через следующую строку. Если нет - просто перейти на следующую строку.
Исполнение каждой команды занимает один тик. Если интерпретатор пытается перейти на строку за пределами программы, программа на следующем тике заканчивает свое исполнение. Длина шага у роботов одинакова. Роботы приземляются единовременно и тут же начинают исполнение своих программ. Роботы после приземления оказываются на расстоянии целого числа шагов друг-от-друга.
Существует ли программа на языке メガメカ такая, что если перед десантированием загрузить ее в оба робота, они встретятся за конечное число тиков? Если да, то приведите ее листинг:)
Задача #3:
Есть две двери, перед каждой из них стоит стражник. За одной дверью - еще одна книжка Смаллиана. За другой - ничего. Каждый из стражников может быть одного из 3-х типов:
рыцарь - всегда говорит правду
лжец - всегда говорит ложь
хитрец - по очереди(т.е. меняя состояние после каждого заданного ему вопроса) говорит правду/ложь, но неизвестно, с чего именно начинает.
Стражникам можно задавать вопросы, ответом на которые является "да" или "нет". Можно ли за два таких вопроса узнать, за какой дверью книжка? Если да, то как?