- PVSM.RU - https://www.pvsm.ru -
Всего несколько часов назад начался конкурс ICFPC-2012, который продлится все выходные. Я решил перевести задачу для этого конкурса в надежде, что кто-то из заинтересовавшихся людей успеет принять участие.
Задача вполне понятная, так что дерзайте.
Шахты с лямбдами обнаружены в Шотландии! Ваша задача — прочитав карту шахты суметь составить программу для робота.
Карта — это сетка m×n клеток, координата (1,1) расположена внизу и слева.
Каждая клетка содержит один из следующих символов:
Ничто не может проникнуть сквозь стену. Ничто не может выйти за пределы поля m×n. Робот может копать землю, собирать λ и двигать камни. Камни падают. Камни могут убить робота.
Пример начального состояния:
#######
#..***#
#..\#
# ..**#
#.*.*#
LR....#
#######
Если координаты робота (x, y):
Двигаться можно в клетку с открытым выходом, в пустую, в клетку с землёй и клетку с λ. Ещё можно двигаться (только налево и направо) в клетку с камнем, если за камнем пустое место. После ухода из клетки робот всегда оставляет в клетку пустоту.
После движения робота проходит шаг симуляции. Во время этого этапа всегда читается старое состояние и пишется в новое. В следующем порядке по координатам: (1, 1), (2, 1), ..., (n, 1), (1, 2)… (n, m).
Правила проверяются по порядку, сверху вниз. Если одно сработало, то следующее уже не сработает.
Если на карте больше нету λ, все закрытые выходы открываются.
Если под только что упавшим камнем стоял робот — робот ломается, это — поражение.
За один шаг симуляции камни падают на 1 клетку вниз.
Иногда камни с разных сторон могут упасть в одну клетку. В этом случае в этой клетке теперь лежит 1 камень.
Ввод с stdin, вывод в stdout
Если некоторые строки короче максимальной по длине строки, то они считаются дополненными пробелами справа.
На каждой карте в начале нет открытых выходов. Есть ровно 1 робот и ровно 1 закрытый выход.
Карта может быть 1000×1000 и более.
За каждый шаг -1
За собранную λ +25
За собранную λ в момент выполнения команды A +25
За собранную λ в момент достижения выхода +50
Скрипт для тестирования своих вариантов прохождения тестовых карт: validator [1]
Программа должна работать на 32bit Debian-linux c 1 Gb RAM.
Через 150 секунд программа получает SIGINT, после этого у неё есть 10 секунд на вывод ответа.
После этих 10 секунд SIGKILL и 0 очков.
В течение конкурса будет от 1 до 4 изменений правил.
Детали на английском: icfpcontest2012.wordpress.com/ [2]
Автор: jerom
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/11403
Ссылки в тексте:
[1] validator: http://undecidable.org.uk/~edwin/cgi-bin/weblifter.cgi
[2] icfpcontest2012.wordpress.com/: http://icfpcontest2012.wordpress.com/
Нажмите здесь для печати.