Задачка на алгоритмы: уничтожить роботов
medium

Задачка на алгоритмы: уничтожить роботов

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

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

Задачка на алгоритмы: уничтожить роботов

Условия

  1. Костюмы находятся в разных сторонах на огромной полосе астероидов. Можно считать, что она бесконечна. 
  2. Все астероиды одного размера и выстроены в ряд, линейно. С каждого астероида робот может переместиться либо влево, либо вправо.
  3. Все астероиды покрыты льдом и окрашены в голубой цвет. Исключение — один чёрный астероид. На старте он находится на равном расстоянии между костюмами. 
  4. Запрограммировать можно только два костюма сразу, одной и той же программой. Запрограммировать их по отдельности нельзя. 
  5. Запрещены пустые циклы и обращение к несуществующим строкам. 
  6. Как только два робота оказываются на одном квадрате, программа завершается. 

Доступные команды

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

Step to the left — шаг влево на следующий астероид → переключение на следующую строку программы. 

Step to the right — шаг вправо на следующий астероид → переключение на следующую строку программы. 

If black asteroid — проверить, есть ли под ногами чёрный астероид. Если да — переключиться на следующую строку программы. Если нет — вернуться к предыдущей строке программы. 

Teleport N — переключиться на N-ю строку программы. 

На команды Step и проверки IF костюмы тратят по 1 секунде. У команды Teleport N мгновенное выполнение.

  1. Step to the right. 
  2. If black asteroid. 
  3. Teleport 5. 
  4. Teleport End. 
  5. Step to the right. 
  6. Teleport 5.

Рассуждение

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

Выбираем право и ждём, пока один из костюмов не встретит чёрный астероид — это первые две строки программы.

При однонаправленном движении только один костюм встретится с чёрным астероидом

До встречи с чёрным астероидом оба костюма двигались с одинаковой скоростью — они проходили один астероид за две секунды: одну секунду занимала первая команда (Step to the right) и одну секунду — вторая (If black asteroid). Теперь эту скорость сохраняет только один костюм — тот, что не встретил чёрный астероид. 

Второй костюм ускоряет движение за счёт команды Teleport 5. Он может за две секунды пройти два астероида — двигается в два раза быстрее первого костюма.

После нахождения чёрного астероида один костюм в два раза быстрее другого

Костюмы двигаются в одну сторону с разной скоростью — это значит, что найдётся конечная точка, где они встретятся и уничтожат друг друга. Финал!

Задачка на алгоритмы: уничтожить роботов

Текст

Александр Бабаскин


Редактура

Максим Ильяхов


Корректор

Ира Михеева


Иллюстратор

Даня Берковский


Вёрстка

Маша Дронова


Соцсети

Олег Вешкурцев


Во имя

памяти Тони Старка

Алгоритмы — основа разработки
Изучите алгоритмы, чтобы легко проходить ИТ-собеседования и делать более совершенный софт. Старт — бесплатно. После обучения — помощь с трудоустройством.
Новый уровень тут
Алгоритмы — основа разработки Алгоритмы — основа разработки Алгоритмы — основа разработки Алгоритмы — основа разработки
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
Задача для дата-сайентистов
Задача для дата-сайентистов

Это будет сложно.

medium
Андрюха, у нас логика! Возможно, криминал

Логическая задача о преступности.

easy
Задача на импортозамещение
Задача на импортозамещение

Немного логики, капля математики и много любви к российским фермерам.

medium
Итого — 9 поездок, в два раза меньше, чем первым способом! Граждане, берегите лифт!
Логическая задача про лифт

Сколько нужно выдержать поездок, чтобы попасть на свой этаж?

easy
Задача Эйнштейна

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

hard
Инженерная задачка для программистов

Как запрограммировать датчик для вращающегося диска?

medium
Задача: математика против колоды карт
Задача: математика против колоды карт

Интуитивное решение и вероятности

hard
Коктейльная задача про доли и крепость

Ну, будем!

easy
Простая задача о почти сорванном дедлайне

Как всё успеть в последний момент.

easy
medium