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

← →
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]

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

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