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

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

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

Условия

  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. Он может за две секун­ды прой­ти два асте­ро­и­да — дви­га­ет­ся в два раза быст­рее пер­во­го костюма.

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

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

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

Текст:
Алек­сандр Бабаскин

Редак­ту­ра:
Мак­сим Ильяхов

Кор­рек­тор:
Ира Михе­е­ва

Иллю­стра­тор:
Даня Бер­ков­ский

Вёрст­ка:
Маша Дро­но­ва

Соц­се­ти:
Олег Веш­кур­цев

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