|
Задание C. "Роботы"
Рассмотрим конечную (но произвольно длинную) шеренгу роботов. Все роботы одинаковы,
за исключением самого левого и самого правого. Крайние роботы обозначены на рисунке
буквами "Л" и "П". Рядом с левым роботом имеется табло, на которой может быть записано
одно из двух чисел: 1 или 0. Все роботы действуют синхронно. Задача каждого робота - полить
растущий перед ним цветок (на картинке цветок не обозначен, так как он пока еще не вырос).
Желательно, чтобы все цветы расцвели одновременно, но для этого их необходимо и поливать
одновременно!
Каждый робот имеет ячейку памяти, в которой хранится его текущее состояние (на картинке
состояние проставлено числом 1 в овале на груди робота). Каждый робот видит состояния своих
соседей. Кроме того, у каждого робота имеется управляющая таблица, в которой предусмотрено:
в какое состояние должен перейти робот в зависимости от состояний его соседей и его
собственного состояния. Эта таблица одинакова для всех внутренних роботов. У левого и правого
роботов задана своя таблица. Ниже приведена структура таблиц управления. Одна строка в таблице
должна быть задана обязательно. Задача участника - придумать остальные строки.
Таблица управления для левого робота.
Состояние табло |
Состояние самого себя |
Состояние правого робота |
Новое состояние самого себя |
1 |
1 |
1 |
1 |
... |
... |
... |
... |
Таблица управления для внутренних роботов.
Состояние левого робота |
Состояние самого себя |
Состояние правого робота |
Новое состояние самого себя |
1 |
1 |
1 |
1 |
... |
... |
... |
... |
Таблица управления для правого робота
Состояние левого робота |
Состояние самого себя |
Новое состояние самого себя |
1 |
1 |
1 |
... |
... |
... |
Первоначально все роботы находятся в состоянии 1. В таблице управления у каждого
робота всегда должна быть строка, состоящая из всех единиц. Эта строка означает, что
робот постоянно находится в состоянии 1, если его соседи находятся в состоянии 1. С первыми
лучами солнца садовник вписывает в табло число-состояние 0, которое служит сигналом для
робота "Л" к началу работы. Далее роботы действуют по своим таблицам управления.
Каждый такт работы каждого робота состоит в следующем:
определить состояния роботов-соседей и свое состояние,
найти в таблице соответствующую строку и запомнить свое новое состояние,
в конце такта перейти в это новое состояние, изменив число у себя на груди.
Все роботы действуют синхронно, то есть каждый такт работы у всех роботов начинается
одновременно.
Роботы начинают поливать цветы, когда они перейдут в нулевое состояние.
Задание
Участнику необходимо составить три таблицы управления (первая таблица - для левого
робота, вторая - для каждого из внутренних роботов, третья - для правого робота). Порядок
строк внутри таблицы может быть произвольным. В каждой таблице должна быть строка из всех
единиц. Количество используемых состояний в каждой из таблиц не должно превышать 256 (с
номерами из диапазона 0..255).
Необходимо, чтобы в какой-то момент времени как можно больше роботов одновременно
перешли в состояние 0. Число допустимых тактов ограничено величиной 10*n, где n - количество
роботов. Количество строк каждой из таблиц не должно превышать 1000. Тестирующая программа
жюри прекращает проверку решения в одном из случаев:
в таблице управления какого-либо робота не предусмотрена текущая комбинация состояний,
превышено максимально установленное число тактов,
один или несколько роботов перешли в нулевое состояние.
В последнем случае участнику начисляется количество очков, равное количеству роботов,
находящихся в нулевом состоянии.
Демонстрационное программное обеспечение для тестирования решений
Участники могут воспользоваться демонстрационной программой, которая позволит проверить
смену состояний роботов при заданном файле с управляющими таблицами. Для этой программы
действуют ограничения: число состояний не превышает 256 (состояния нумеруются числами от 0
до 255), количество строк в каждой управляющей таблице не должно превышать 1000, а количество
тактов не превышает величины 10*n (n - количество роботов). При запуске демонстрационной
программы через командную строку вводятся два обязательных параметра: наименование файла,
содержащего управляющие таблицы, и количество роботов, участвующих в испытании (максимальное
число роботов, отображаемых на экране, равно 159). Допустим и третий (необязательный)
параметр - латинский символ "u" - запрещающий вывод демонстрационного экрана.
Формат файла исходных данных
1. В первой строке задаются через пробелы три числа: количество строк в таблице для левого
робота, количество строк в таблице для внутреннего робота, количество строк в таблице для
правого робота.
2. Далее подряд записываются строки управляющих таблиц: сначала для левого, затем для
внутреннего и, наконец, для правого роботов. Внутри строк числа разделяются пробелами и идут
в порядке, указанном в примерах. Для отделения одной таблицы от другой допустимо использовать
пустые строки.
Методика оценивания
Жюри будет проверять решения участников на количестве роботов в диапазоне 3..500. Лучшим
считается решение, обеспечивающее одновременный переход большего количества роботов в нулевое
состояние. При равенстве числа поливающих роботов лучшим считается то из них, которое обеспечит
переход роботов в состояние полива за меньшее число тактов.
|
|