Легенда

Разведовательный беспилотник «Фаина Клементьевна» совершал плановый облёт местности на метеорите, имеющем форму тора, когда его застала сильная космическая буря с грозой. Удар молнии повредил ряд важных модулей, в том числе модуль геопозиционирования, а порыв ветра отнес беспилотник в неизвестную точку метеорита. К счастью, память не пострадала и сохранила точную посекторную карту метеорита с информацией о количестве ориентиров трёх типов: холмы, кратеры и вкрапления руды.

Загруженная карта имеет один из двух форматов:

  • формат 1 хранит информацию о количестве ориентиров всех типов в пределах данного сектора.
  • формат 2 хранит информацию о группе ориентиров в северно-западном углу данного сектора. В данном случае подразумевается, что группы ориентиров расположены на угловых пересечениях секторов, при этом на каждом пересечении встречается произвольное количество ориентиров одного конкретного типа.

Запаса батареи «Фаины» хватит ещё на 20 секунд. За одну секунду беспилотник может переместиться в соседний сектор и сразу выполнить быстрое сканирование, в результате которого будет получена информация о примерном количестве ориентиров в текущем секторе. При быстром сканировании «Фаина» обнаруживает их по отдельности с вероятностью 80%, 70% и 60% соответственно.

Вместо очередного перемещения «Фаина» может передать сигнал бедствия в окрестности космоса. Но для успешного обнаружения беспилотник должен передать свои координаты с точностью до сектора.

Опишите стратегию, при которой «Фаина» сможет успешно сориентироваться и запросить помощь.

Это интерактивная задача, и это значит, что ваша программа взаимодействует с проверочной системой посредством стандартных потоков ввода и вывода. Иными словами, после отправки сообщения программа должна очистить буфер (выполнить flush) и считать ответ от системы (прочесть строку). В случае некорректного ответа, проверка прерывается с вердиктом PE (Presentation Error).

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

Формат принимаемых сообщений:

  • MAP 1 20 15 – готовьтесь принять карту в формате 1 размером 15 строк с 20 ячейками в каждой.
  • 5;2;3 5;2;3 10;2;3 5;2;30 10;2;3 – передаётся строка из пяти ячеек формата 1 с информацией об количествах ориентиров, разделённых точкой с запятой.
  • 0-20 1-25 2-13 1-23 0-2 – передаётся строка из пяти ячеек формата 2 с информацией о типе (от 0 до 2) и количестве ориентиров, разделённых дефисом.
  • 10 23 10 – в текущем секторе обнаружено такое количество ориентиров.
  • YES или NO – завершите программу.

Формат отправляемых сообщений:

  • HELPME 0 5 – передать сигнал помощи с координатами (0; 5), столбец и строка соответственно. (нумерация координат с 0!)
  • LEFT, RIGHT, UP, DOWN – переместиться по карте на соседний сектор и отсканировать его.

Ваше решение будет проверено 200 раз, и итоговая оценка будет рассматриваться по числу успешных обнаружений. Ваше решение засчитывается на полный балл, если доля успешных испытаний составит не меньше 90%.

Для решения этой задачи у вас есть 20 попыток.

Видео-разбор