Задание 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. Лучшим считается решение, обеспечивающее одновременный переход большего количества роботов в нулевое состояние. При равенстве числа поливающих роботов лучшим считается то из них, которое обеспечит переход роботов в состояние полива за меньшее число тактов.