-3

Моя олимпиадная задача

Прочитал пост http://pikabu.ru/story/veselaya_zadachka_4534715 и вспомнил задачу, которую решал на  олимпиаде по информатике году эдак в 1991 - единственную, которая мне запомнилась из всех задач на всех олимпиадах, в которых я участвовал, из-за необычной подачи условия ))


Итак, если кому интересно.


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


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


1. Проверка условия "нашёл парашют" (если нашёл парашют, то...).

2. Шаг влево.

3. Шаг вправо.

4. Переход на строку программы №.


Собственно, нужно составить программу для роботов )

Моя олимпиадная задача Задача, Олимпиада, Роботы убийцы

Дубликаты не найдены

+1

Сегодня на собеседовании мне задали эту задачу. Решение такое, как мне кажется:
1. Иди направо
2. Если нашёл парашут, то перейди на строку N4
3. Перейти на строку N1
4. Иди направо
5. Иди направо
6. Перейди на строку N4.

раскрыть ветку 1
0

Надо же, кто-то там читал  пикабу, похоже.



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

+1

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

раскрыть ветку 1
-1
Тоже вариант, но не самый короткий.
+1

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

раскрыть ветку 7
+1
я может что-то не правильно понял но разве такой алгоритм не запорется при следующих условиях: движемся пусть в право, Р1,Р2 - роботы, П1,П2 - парашюты

.....П1..Р1...........Р2..П2...

ониж вроде поступят одинаково и так и уйдут в правый закат? или нет?

раскрыть ветку 5
0

В условии вообще про это не сказано, я подразумевал, что парашюты просто остаются в точке приземления :)

раскрыть ветку 2
-1

О, кстати, да. Похоже, парашюты должны отстреливаться в одну сторону, точно уже не помню.

раскрыть ветку 1
-1

Бинго! И код ещё запили.

+1

"на поверхность, представляющую собой идеальную бесконечную прямую"

0

Я не программист. Но задача логическая. У ОБОИХ роботов одинаковая программа.

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

Робот появился на парашюте. Это значит решение вот такое:

1.Влево

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

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

3.Если парашют не найден переходит к этой команде: вправо, вправо

4.Если парашют найден то бесконечно вправо (по принципу из пункта 2), а если не найден то к пункту 5

5. "влево влево влево" и опять поиск парашюта если найден то по принципу из пункта 2, а если нет, то


то

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

то есть код будет бесконечным без этих циклов=



=код будет бесконечным, если будет писаться не в реальном времени, а если в реальном, то задача будет решена как только роботы встретятся.

0

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

раскрыть ветку 5
-1

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

Ну и вообще, роботы-то одинаковые, так что да )

раскрыть ветку 4
-1

Бедные марсоходы. Едут такие по Марсу, должны исправлять заданный путь по алгоритму, но на каждую команду программы тратят время равное времени минимального беспрерывного движения (что вряд ли равно даже паре десятков тактов его процессора на 300мГц, ибо инерция и все дела. Цифры условные)


В моем решении поверхность в виде бесконечной прямой (Что?) будет на ленте Мебиуса. Точка. Алгоритм сами напишите?

раскрыть ветку 3
0

А решение не покажешь?)))

раскрыть ветку 1
-1

Хитрый какой )))

-1

Идти налево 100 метров.

Если не встретил друга, развернуться и идти 200 метров.

Если не встретил друга, развернуться и идти 400 метров.

Ну и так далее, пока не найдут друг друга.

...

Провести процедуру активации боеголовки.



Лень записывать с переменными, но смысл ясен)

раскрыть ветку 3
-1

Переменных нет.

Программа одинаковая у обоих.

Низачод )

раскрыть ветку 2
-1

Оставить заряд в парашюте.

Идти до бесконечности вправо пока не найдешь чужой парашют.

Взять оттуда заряд.

Идти до бесконечности влево пока не найдешь свой парашют

Взять вторую половину заряда.

Взорваться.

раскрыть ветку 1
Похожие посты