← 返回题目列表

Codeforces · 2/B

B. 最少回合数

中文机器翻译题面 查看原题

有一个方阵 n × n,由非负整数组成。你应该找到这样的方法

- 从矩阵的左上角单元格开始;
- 每个后续单元格位于当前单元格的右侧或下方;
- 道路在右下单元格结束。

此外,如果我们将一路上的所有数字相乘,结果应该是最不“圆”的。换句话说,它应该以尽可能少的零结尾。

输入

第一行包含一个整数n (2 ≤ n ≤ 1000),n是矩阵的大小。然后n行包含矩阵元素(不超过109的非负整数)。

输出

在第一行中打印最少数量的尾随零。在第二行中打印相应的方式本身。

示例

输入 #1

3
1 2 3
4 5 6
7 8 9

输出 #1

0
DDRR