Ограничения: время – 200ms/200ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Напишите программу для робота, который движется по полю из пяти клеток с числами от 1 до 5 и может менять числа в соседних клетках.
Первоначально робот всегда находится на двух первых клетках слева. Ваша задача - написать программу для робота,
которая расставит числа по порядку от 1 до 5, независимо от их начального расположения.
Дополнительной подзадачей является минимизация количества перемещений робота по полю в худшем случае (подробнее ниже).
Для управления роботом вы можете использовать следующие команды:
Первая команда позволяет выбрать варианты действий в зависимости от чисел в клетках, на которых находится робот.
Вторая команда позволяет повторить заданное количество раз некоторую последовательность действий.
Команды движения позволяют перейти роботу на соседнюю клетку влево или вправо. Если выполнение команды движения невозможно, то она игнорируется.
Последняя команда позволяет поменять числа в клетках, на которых находится робот.
Например, для упорядочения перестановки на рисунке робот должен переместиться на 2 клетки вправо и выполнить обмен.
Эту последовательность действий можно задать следующей программой:
*Система оценки и описание подзадач*
||.u|Подзадача 1 (20 баллов)||
В этой подзадаче 1 тест, показанный на рисунке. Количество перемещений робота не учитывается.
||.u|Подзадача 2 (70 баллов)||
Числа от 1 до 5 на поле расположены в произвольном порядке. Количество перемещений робота не учитывается.
Необходимые подзадачи: 1.
В этой подзадаче 7 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
||.u|Подзадача 3 (10 баллов)||
Необходимые подзадачи: 1, 2.
В этой подзадаче 1 тест.
В зависимости от начального расположения чисел на клетках для их упорядочения может потребоваться разное количество перемещений робота по полю.
Существует перестановка, для которой теоретический минимум количества перемещений
для упорядочения этой перестановки является максимальным по сравнению с другими перестановками (худший случай). Пусть он равен `N`.
Программа запускается на всех возможных перестановках чисел от 1 до 5, и определяется
максимальное количество перемещений робота `M` (количество успешно выполненных команд движения робота),
которое потребуется для упорядочения какой-либо из этих перестановок (худший случай).
Тест считается пройденным, если `M` = `N`.
---
Для написания программы для робота используется [специальная версия среды Blockly](blockly/2522.html).
Вы можете использовать полную среду Blockly при решении других задач этого соревнования, выбрав пункт Blockly в информационном меню задачи.
Для проверки работы используйте кнопки:
Первая кнопка позволяет отправить ваше решение для проверки в проверяющую систему соревнований, вторая кнопка выполняет запуск программу локально, третья –
пошаговое выполнение или временная остановка программы, четвертая – завершение выполнения программы, после которой программа будет выполняться сначала.
Щелкая мышкой по клеткам начального состояния поля, можно задать исходный порядок чисел для тестирования программы.
Начало
Рабочее место участника
Олимпиадные задачи на русском языке