Минитест на сообразительность

← →
Sha (2003-04-24 09:48) [0]

Во вчерашнем "Хакере" была задачка на сообразительность:

На числовую прямую (кому надо ближе к реальности - на железную дорогу)
на парашютах одновременно приземляются два робота и сбрасывают парашюты
себе под ноги. Расстояние между ними - целое число шагов.
Каждый робот несет рюкзак с половинкой ядерного заряда. Если они
встретятся в одной точке в одно время, произойдет взрыв.
Сразу после приземления роботы начинают исполнять заложенную в них
программу. Они понимают всего 4 команды (шаг влево, шаг вправо,
безусловный переход, условный переход, если под ногами парашют),
а исполнение одной команды занимает у них ровно 1 секунду (ну, тупые!).
Ваша задача - взорвать железную дорогу, написав программу для роботов
как можно короче (мозгов-то у них почти нет).

Сознаюсь честно, думал больше минуты :(
Обидно, да? :)

← →
MBo (2003-04-24 10:05) [1]

Один стоит, другой сканирует - N шагов влево, 2N вправо, 4N влево и т.д.

← →
Sha (2003-04-24 10:10) [2]

2MBo © (24.04.03 10:05)

Программа у обоих роботов должна быть одинакова - их на фабрике делают :)

← →
Sha (2003-04-24 10:11) [3]

>MBo © (24.04.03 10:05)
>...и т.д.

Какой длины программа будет?

← →
Внук (2003-04-24 10:19) [4]

По прямой. Потому что я верю, что наши роботы способны наступить на горло собственному парашюту. Или он неуязвим для будущего ядерного взрыва? :)

← →
Palladin (2003-04-24 10:21) [5]

ядерным... жд...

← →
Sha (2003-04-24 10:23) [6]

>Внук © (24.04.03 10:19)
>По прямой.
Не понял.

>Или он неуязвим для будущего ядерного взрыва? :)
Кого волнует судьба двух отдельно взятых роботов? :)

← →
REA (2003-04-24 10:23) [7]

Стоять и ждать пока проедет поезд...

← →
Думкин (2003-04-24 10:25) [8]

> Sha © (24.04.03 10:10)

Как MBo.
На фабрике - Когда встретишь чужой парашют встань и все. Хозяин когда-нибудь припрется.

← →
Sha (2003-04-24 10:26) [9]

2Palladin © (24.04.03 10:21)
2REA © (24.04.03 10:23)

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

← →
Sha (2003-04-24 10:27) [10]

2Думкин © (24.04.03 10:25)
Нужна программа из команд, понятных роботам :)

← →
Думкин (2003-04-24 10:30) [11]

> Sha © (24.04.03 10:27)
То есть стопа нет?
Но память у них есть?

← →
Mike Kouzmine (2003-04-24 10:34) [12]

А что, условие "Если они
встретятся в одной точке в одно время, произойдет взрыв." обязательно. А если они встретятся в разное время?

← →
Sha (2003-04-24 10:35) [13]

>Думкин © (24.04.03 10:30
>То есть стопа нет?
Нет.

>Но память у них есть?
Небольшая. Победит тот, кому потребуется меньше. Хотя, я думаю, всем потребуется одинаково. :)

← →
Sha (2003-04-24 10:40) [14]

>Mike Kouzmine © (24.04.03 10:34)
>А если они встретятся в разное время?

Сам над этим думал, когда набирал текст. Но решил оставить как есть - подумал, что так всем понятнее будет. Хотя кое-кто все еще задает уточняющие вопросы, вместо того, чтобы решать :)

← →
pasha676 (2003-04-24 10:54) [15]

> Как MBo.
> На фабрике - Когда встретишь чужой парашют встань и все.
> Хозяин когда-нибудь припрется.

> Один стоит, другой сканирует - N шагов влево, 2N вправо,
> 4N влево и т.д.

Может быть будет оптимальней оба сканируют, встретил чужой парашют, встал на месте? Нет стопа - фиг с ним. Пусть зацикливается на шаг вправо-шаг влево. Безусловный переход есть.
Опознание "свой-чужой парашут" можно сделать запоминая шаги "влево-вправо".

← →
Danilka (2003-04-24 10:57) [16]

почти как MBo © (24.04.03 10:05)
"..N шагов влево, 2N вправо, 4N влево и т.д..." пока не встретит чужой парашют. после чего, продолжать идти без изменения направления.

а как иначе?

← →
Sha (2003-04-24 11:00) [17]

2pasha676 (24.04.03 10:54)
2Danilka © (24.04.03 10:57)

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

← →
Danilka (2003-04-24 11:05) [18]

Sha ©
переменных нет, цикла нет так?

← →
han_malign (2003-04-24 11:07) [19]

N,2N,4N - насчет наличия арифметических операций и аккумулятора/счетчика ничего не говорилось, так что облом.

← →
pasha676 (2003-04-24 11:07) [20]

> Sha

Если грок алгоритм во всей полноте, то писать программу уже не интересно.

> Danilka

Да, точно так. Наверное это оптималистее.

← →
han_malign (2003-04-24 11:10) [21]

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

← →
pasha676 (2003-04-24 11:11) [22]

> N,2N,4N - насчет наличия арифметических операций и аккумулятора/счетчика
> ничего не говорилось, так что облом.

Да нет. Наверное и переменные и мат операции (хотя бы сложение- вычитание) должны быть.

← →
Sha (2003-04-24 11:11) [23]

>Danilka © (24.04.03 11:05)
>переменных нет, цикла нет так?
Нет.

>pasha676 (24.04.03 11:07)
>Если грок алгоритм во всей полноте, то писать программу уже не интересно.
Не знаю, что такое "грок алгоритм". Это нормальный алгоритм с небольшим числом команд.

← →
REA (2003-04-24 11:12) [24]

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

← →
Sha (2003-04-24 11:15) [25]

2han_malign © (24.04.03 11:10)
Поздравляю!
Просто для интереса: какова четность числа команд в вашей программе?

← →
Sha (2003-04-24 11:17) [26]

>REA © (24.04.03 11:12)
>Если они в состоянии попасть на парашютах на железную дорогу, то могут и в одно место попасть.

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

← →
NewN (2003-04-24 11:18) [27]

Метка1
Шаг влево
Шаг влево
Шаг вправо
Если под ногами парашют, то GoTo Метка2
GoTo Метка1
Метка2
Шаг влево
GoTo Метка2

← →
Danilka (2003-04-24 11:19) [28]

Sha ©
игра в догонялки? :))

← →
Danilka (2003-04-24 11:19) [29]

NewN (24.04.03 11:18)
опередил...

← →
Sha (2003-04-24 11:24) [30]

>REA © (24.04.03 11:12)
>Им парашюты что ли двигаться мешают или они просто могут опознать парашют?

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

← →
IGOREK (2003-04-24 11:24) [31]

влево
1: если парашют под ногами то переход на метку 2
влево
влево
вправо
переход на метку 1:
2:
влево
переход на метку 2

← →
han_malign (2003-04-24 11:25) [32]

>NewN (24.04.03 11:18)
если команды перехода(и проверки условия) занимают тоже время, то
...
Шаг влево
Шаг вправо
- лишние
З.Ы. Интересно, почему всех на лево тянет, я вот почему то тоже влево ломанулся :)))

Итого пять команд, интересно, а можно ли за четыре???

← →
evvcom (2003-04-24 11:26) [33]

Ну память должна быть, раз есть где программу разместить!
Итак, что-то типа того:
1. Ну, например, шаг влево, считая шаги.
2. Если под ногами нет парашюта, то п.1
3. Иначе (есть парашют под ногами), значит второй робот впереди. Безусловный переход на уже пройденное количество шагов (ну плюс-минус, считать лень, а отладчиком пройтись было бы проще). Попадаем точно на второго робота и взрыв!

Вроде так должно пройти.

← →
pasha676 (2003-04-24 11:28) [34]

> Метка1
> Шаг влево
> Шаг влево
> Шаг вправо
> Если под ногами парашют, то GoTo Метка2
> GoTo Метка1
> Метка2
> Шаг влево
> GoTo Метка2

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

← →
Sha (2003-04-24 11:29) [35]

NewN (24.04.03 11:18)
Danilka © (24.04.03 11:19)
IGOREK © (24.04.03 11:24)

Поздравляю!
У кого короче? :)

← →
REA (2003-04-24 11:35) [36]

Я вот тоже это момент не понял. Они же в обе стороны должны сканировать. И парашют может чужой под ноги попасть...

← →
Sha (2003-04-24 11:40) [37]

>REA © (24.04.03 11:35)
>Я вот тоже это момент не понял. Они же в обе стороны должны
>сканировать. И парашют может чужой под ноги попасть...

Еще есть шанс занять первое место, улучшив решения тех, кто понял.

← →
pasha676 (2003-04-24 11:41) [38]

2REA
При этом алгоритме свой парашют не попадет, но...

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

← →
Sha (2003-04-24 11:46) [39]

>pasha676 (24.04.03 11:41)
>Похоже в условии задачи допущена грубейшия ошибка.
>Роботы делают шаги "влево-право" не относительно себя...

Не надо путать. Именно относительно себя. Т.е. при шаге вправо координата робота увеличивается на 1, при шаге влево - уменьшается на 1.

← →
Mischka (2003-04-24 11:48) [40]

2pasha676
Роботы не могут быть ориентированы по разному на числовой прямой. На ней четко указаны и лево и право. А железная дорога - это для тех, кто плохо с прямыми знаком.

← →
Sha (2003-04-24 11:50) [41]

В догонку.
Влево/вправо - имеется ввиду на числовой прямой влево/вправо. А в реальной жизни замените это на запад/восток.
Хотя тоже можно сказать, что дорога-то кривая и т.д. и т.п.

← →
Sha (2003-04-24 11:56) [42]

2han_malign © (24.04.03 11:25)
Поздравляю! Вы победитель!

P.S. У меня тоже пять, но ходил я вправо :)

← →
Sha (2003-04-24 11:58) [43]

>evvcom © (24.04.03 11:26)
>Ну память должна быть, раз есть где программу разместить!

Память-то есть, а вот команды "поместить в память" нет!

← →
evvcom (2003-04-24 12:03) [44]

Ну извиняйте, согласен. Интересная задачка, а сколько споров!

← →
pasha676 (2003-04-24 12:04) [45]

2Mischka

> Роботы не могут быть ориентированы по разному на числовой
> прямой. На ней четко указаны и лево и право. А железная
> дорога - это для тех, кто плохо с прямыми знаком.

Хм. Давай так. Роботы могут ходить влево-вправо относительно себя (иного я просто не мог предположить, специфика работы наверное). Дорога ведет с севера на юг. Один робот падает носовой частью на запад. Другой носовой частью на восток. Тогда при хотьбе обоих "влево" или "вправо" они могут или сходиться, или расходиться. Т.е. алгоритм не работает в 50% случаев.

ЗЫ Я кстати минут десять медитировал на алгоритм, не понял его. Пока до меня не дошло, что "лево-право" - это относиться к линии, а не к роботу.

← →
Sha (2003-04-24 12:08) [46]

>pasha676 (24.04.03 12:04)
>Хм. Давай так. Роботы могут ходить влево-вправо относительно
>себя (иного я просто не мог предположить, специфика работы
>наверное). Дорога ведет с севера на юг. Один робот падает
>носовой частью на запад.

А куда идти роботу, если он упал носом на север? У меня бы сразу такой вопрос возник :)
см. Sha © (24.04.03 11:50)

← →
han_malign (2003-04-24 12:10) [47]

>pasha676 (24.04.03 11:41)
>Похоже в условии задачи допущена грубейшия ошибка.
>Роботы делают шаги "влево-право" не относительно себя...

В условии:
На числовую прямую...
- что убирает кривотолки насчет лево и право - sapienty sat,
робот вообще создание шарообразное и не знает ни лево, ни право, ни перед, ни зад, ни верх, ни низ, а только dec и inc :)))

>Ну память должна быть, раз есть где программу разместить!
>Итак, что-то типа того:
>1. Ну, например, шаг влево, считая шаги.
- ПЗУ - нет там счетчиков, только регистр адреса команды, к тому же "шаг влево, считая шаги" это несколько команд, и задача оптимизировть размер программы, а не время сходимости метода...

← →
JibSkeart (2003-04-24 12:20) [48]

Гыы сделать шаг робот сподкнется об парашют и ВЗРЫВ !!!

← →
evvcom (2003-04-24 12:20) [49]

> - ПЗУ - нет там счетчиков, только регистр адреса команды
В ПЗУ также нет и регистра адреса команды, если на то пошло. И кроме того ПЗУ вообще по барабану команда у нее в ячейке записана или байт (бит, слово и т.д.) данных.
А регистр адреса команды - это у процессора.

Я уже извинился за свою невнимательность.

← →
evvcom (2003-04-24 12:21) [50]

> JibSkeart
Не... Только полвзрыва.

← →
REA (2003-04-24 12:22) [51]

Ну так еще:

1: влево
If 2
goto 1
2: влево
goto 2

← →
pasha676 (2003-04-24 12:24) [52]

2han_malign

> а только dec и inc

Я понимаю неточность в моем понимании. Но и ты меня пойми. Если ты сделаешь робота который будет отличать дек и инк в глобальной системе координат, да еще с недоразвитыми мозгами - тебе памятник при жизни поставят.
Дек и инк относительно робота на числовой прямой - может тоже быть в две разные сторны в зависимости от ориентации робота :). Это как два вектора на одной прямой, но с разными направлениями.
Попробуйте составить алгоритм в условиях что роботы понятие не имеют, где увеличение и уменьшение этих самых координат на прямой. Обломаетесь без ОЗУ.

Имхо - так надо было и формулировать условие задачи - "роботы могут двигаться вдоль числовой прямой в сторну увеличения или уменьшения координат на этой прямой".
Судя по всему, я не один кто так подумал. Думкин, МВо, Данилкин и REA - тоже так думали.

← →
Sha (2003-04-24 12:25) [53]

← →
REA (2003-04-24 12:27) [54]

Тьфу ты блин. Думал что-то хитрое придумал, а алгоритм из 5 ходов уже давно сделали. Время только потратил. Из четырех никто не придумал?

← →
REA (2003-04-24 12:29) [55]

А вправо ходить чтобы всех запутать? Лучше бы Not сделали...

← →
Sha (2003-04-24 12:31) [56]

2pasha676 (24.04.03 12:24)

Согласен. Если кому-нибудь еще буду задавать эту задачу, обязательно буду говорить:
...на железную дорогу (запад-восток)...
...шаг влево(на запад), шаг вправо(на восток)...

← →
REA (2003-04-24 12:33) [57]

А еще лучше не сбрасывать второго робота.

← →
Sha (2003-04-24 12:34) [58]

>REA © (24.04.03 12:29)
>А вправо ходить чтобы всех запутать? Лучше бы Not сделали...

Ага. Чтобы запутать.
Я давал эту задачу своим детям.
Дочери пришлось дать подсказку, что одна команда в арсенале робота лишняя.

← →
REA (2003-04-24 12:35) [59]

А еще лучше не сбрасывать обоих роботов, а сделать один таймер.

← →
Sha (2003-04-24 12:36) [60]

>REA © (24.04.03 12:27)
>Тьфу ты блин. Думал что-то хитрое придумал, а алгоритм из 5
>ходов уже давно сделали. Время только потратил. Из четырех
>никто не придумал?

Из 4-ех не существует.

← →
han_malign (2003-04-24 12:37) [61]

> Дек и инк относительно робота на числовой прямой - может тоже быть в две разные сторны в зависимости от ориентации робота :)
- а ну-ка, сориентируйте мне "головку"("перо") в машине Тьюринга, что бы оно начало в обратную указанной сторону двигаться...
У глобальной системы координат - глобальные лево и право, а вот в относительной...

> тоже так думали
- я тоже думал... Вы программисты, или где, или вам всегда дают полностью завершенное ТЗ, с эскизами GUI, отношениями таблиц, et cetera...

← →
pasha676 (2003-04-24 14:12) [62]

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

На линии две точки. Двигаються только вдоль линии. У одной вектор движения направлен в сторну увеличения координат на прямой, у другой наоборот. Помоему я доступно объясняю. Причем тут машина Тьюринга?

> Вы программисты, или где, или вам всегда дают полностью
> завершенное ТЗ, с эскизами GUI, отношениями таблиц, et cetera...

Кстати именно потому что я программист (причем роботов), я и не смог решить эту задачу. У меня в голову мысль бы никогда не пришла, что робот может знать где "лево-право" в глобальной системе координат.

> - я тоже думал...

Если уже пять человек так подумали - то извини, но это свидетельствует о явной ошибке в формулировке, которая влияет на саму возможность решаемости задачи. В этом кстати уже создатель топика признался. Да и сам ты признался, что сначала так подумал. К чему спор непонятно. Завязываем.
Вообщем давай заканчивать

← →
evvcom (2003-04-24 14:35) [63]

А где она глобальная система координат? Еще Эйнштейн доказал, что все в мире относительно.

← →
Lancelot (2003-04-25 00:44) [64]

Мы эту задачку решали на олимпиаде по информатике еще в 89-м году :)

← →
Sha (2003-04-25 08:34) [65]

>Lancelot © (25.04.03 00:44)
>Мы эту задачку решали на олимпиаде по информатике еще в 89-м году :)

Интересно, каков был масштаб и уровень той олимпиады (школьная-вузовская, районная, городская, все..., континентальная, всемирная / для ккольников x-классов, студентов каких-то там вузов) ?

Минитест на сообразительность Найти похожие ветки