
CLASS	Бизнес- классики CLASS Поле для игры в бизнес-классики – это прямоугольник, состоящий из 3´N клеток. В некоторых клетках лежит по одному рублю, в остальных – ничего нет. Играющий выбирает для начала игры одну из трех левых клеток. За один ход играющий перепрыгивает в одну из клеток, имеющих общую сторону с той, в которой он находится. При этом запрещено прыгать в те клетки, в которых он уже побывал. При очередном прыжке все деньги, собранные к этому моменту удваиваются, а затем, если в новой клетке лежит рубль, то он прибавляется к имеющейся сумме денег. Считается, что в начале игры денег у играющего нет. Закончить прыжки надо в одной из трех правых клеток поля и при этом заработать как можно больше денег. Требуется написать программу, которая по известному значению N и расположению рублей в клетках находит такую последовательность прыжков, при которой играющий заработает наибольшее количество денег. Если таких последовательностей несколько, то следует выбрать любую последовательность, количество прыжков в которой минимально. Технические характеристики: Входной файл: CLASS.IN Выходной файл: CLASS.OUT Ограничение по времени: 5 секунд на тест Максимальная оценка: 35 баллов Входные данные: В первой строке входного файла с именем CLASS.IN записано натуральное число N (1£N£80). В каждой из последующих трех строк находится N чисел (0 или 1), описывающих расположение рублей в клетках первой, второй и третьей строки игрового поля соответственно. Единица обозначает наличие рубля в клетке, ноль – его отсутствие. Числа в каждой из этих трех строк входного файла расположены через пробел. Выходные данные: Выходной файл с именем CLASS.OUT должен содержать 2 строки. В первой строке должен находиться номер строки игрового поля (1, 2 или 3), с которой играющему следует начать игру. Вторая строка файла должна описывать последовательность прыжков. Каждый прыжок в этой последовательности нужно обозначить одним из следующих символов: U – если в результате прыжка номер строки, на которой находится играющий, уменьшился на 1 D – если номер строки увеличился на 1 L – если номер столбца уменьшился на 1 R – если номер столбца увеличился на 1 Символы во второй строке выходного файла должны быть выведены без пробелов. Пример: CLASS.IN 4 1 1 1 0 1 1 1 0 1 1 1 1 CLASS.OUT 1 DDRUURDDRUU

CLASS

Бизнес- классики
CLASS

Поле для игры в бизнес-классики – это прямоугольник, состоящий из 3´N клеток. В некоторых клетках лежит по одному рублю, в остальных – ничего нет. Играющий выбирает для начала игры одну из трех левых клеток. За один ход играющий перепрыгивает в одну из клеток, имеющих общую сторону с той, в которой он находится. При этом запрещено прыгать в те клетки, в которых он уже побывал. При очередном прыжке все деньги, собранные к этому моменту удваиваются, а затем, если в новой клетке лежит рубль, то он прибавляется к имеющейся сумме денег. Считается, что в начале игры денег у играющего нет. Закончить прыжки надо в одной из трех правых клеток поля и при этом заработать как можно больше денег.

Требуется написать программу, которая по известному значению N и расположению рублей в клетках находит такую последовательность прыжков, при которой играющий заработает наибольшее количество денег. Если таких последовательностей несколько, то следует выбрать любую последовательность, количество прыжков в которой минимально.

Технические характеристики:

Входной файл: CLASS.IN
Выходной файл: CLASS.OUT
Ограничение по времени: 5 секунд на тест
Максимальная оценка: 35 баллов

Входные данные:
В первой строке входного файла с именем CLASS.IN записано натуральное число N (1£N£80). В каждой из последующих трех строк находится N чисел (0 или 1), описывающих расположение рублей в клетках первой, второй и третьей строки игрового поля соответственно. Единица обозначает наличие рубля в клетке, ноль – его отсутствие. Числа в каждой из этих трех строк входного файла расположены через пробел.

Выходные данные:
Выходной файл с именем CLASS.OUT должен содержать 2 строки. В первой строке должен находиться номер строки игрового поля (1, 2 или 3), с которой играющему следует начать игру. Вторая строка файла должна описывать последовательность прыжков. Каждый прыжок в этой последовательности нужно обозначить одним из следующих символов:

U – если в результате прыжка номер строки, на которой находится играющий, уменьшился на 1
D – если номер строки увеличился на 1
L – если номер столбца уменьшился на 1
R – если номер столбца увеличился на 1

Символы во второй строке выходного файла должны быть выведены без пробелов.

Пример:

CLASS.IN
4
1 1 1 0
1 1 1 0
1 1 1 1

CLASS.OUT
1
DDRUURDDRUU