The least round way (Codeforces 2B)
Tags: Math, dp

There is a square matrix n × n, consisting of non-negative integer numbers. You should find such a way on it that   starts in the upper left cell of the matrix;  each following cell is to the right or down from the current cell;  the way ends in the bottom right cell. Moreover, if we multiply together all the numbers along the way, the result should be the least "round". In other words, it should end in the least possible number of zeros.

Input: The first line contains an integer number n (2 ≤ n ≤ 1000), n is the size of the matrix. Then follow n lines containing the matrix elements (non-negative integer numbers not exceeding 109).

Output: In the first line print the least number of trailing zeros. In the second line print the correspondent way itself.


Sample Inputs:
3
1 2 3
4 5 6
7 8 9

Sample Outputs:
0
DDRR

Solution (Python):
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
mat = []
pow2 = []
pow5 = []
for i in range(n):
    mat.append(list(map(int, input().split())))
lowest2 = []
lowest5 = []
zeroflag = False
zerostring = ''
for i in range(n):
    arr2 = [0] * n
    arr5 = [0] * n
    for j in range(n):
        temp = mat[i][j]
        if temp == 0:
            zeroflag = True
            zerostring = j * 'R' + i * 'D' + (n - j - 1) * 'R' + (n - i - 1) * 'D'
            continue
        while temp % 5 == 0:
            arr5[j] += 1
            temp //= 5
        while temp % 2 == 0:
            arr2[j] += 1
            temp //= 2
    lowest2.append(arr2)
    lowest5.append(arr5)
dp2 = [[100000000 for i in range(n)] for i in range(n)]
dp5 = [[100000000 for i in range(n)] for i in range(n)]
dp2r = [['' for i in range(n)] for i in range(n)]
dp5r = [['' for i in range(n)] for i in range(n)]
for i in range(n):
    for j in range(n):
        if i == 0 and j == 0:
            dp2[i][j] = lowest2[i][j]
            dp5[i][j] = lowest5[i][j]
            dp2r[0][0] = ''
            dp5r[0][0] = ''
        elif j == 0:
            dp2[i][j] = lowest2[i][j] + dp2[i - 1][j]
            dp5[i][j] = lowest5[i][j] + dp5[i - 1][j]
            dp2r[i][j] = 'R'
            dp5r[i][j] = 'R'
        elif i == 0:
            dp2[i][j] = lowest2[i][j] + dp2[i][j - 1]
            dp5[i][j] = lowest5[i][j] + dp5[i][j - 1]
            dp2r[i][j] = 'D'
            dp5r[i][j] = 'D'
        else:
            dp2[i][j] = min(dp2[i - 1][j], dp2[i][j - 1]) + lowest2[i][j]
            dp5[i][j] = min(dp5[i - 1][j], dp5[i][j - 1]) + lowest5[i][j]
            if dp2[i - 1][j] > dp2[i][j - 1]:
                dp2r[i][j] = 'D'
            else:
                dp2r[i][j] = 'R'
            if dp5[i - 1][j] > dp5[i][j - 1]:
                dp5r[i][j] = 'D'
            else:
                dp5r[i][j] = 'R'
if zeroflag:
    if min(dp2[n - 1][n - 1], dp5[n - 1][n - 1]) != 0:
        print(1)
        print(zerostring)
        exit()
print(min(dp2[n - 1][n - 1], dp5[n - 1][n - 1]))
cur = 0
if dp2[n - 1][n - 1] > dp5[n - 1][n - 1]:
    cur = dp5r
else:
    cur = dp2r
x = n - 1
y = n - 1
ss = [0] * (2 * n - 2)
ind = 2 * n - 3
while x != 0 or y != 0:
    if cur[x][y] == 'R':
        ss[ind] = 'D'
        x -= 1
    else:
        ss[ind] = 'R'
        y -= 1
    ind -= 1
print(''.join(ss))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
zero_path = None
for i in range(n):
    try:
        j = a[i].index(0)
        zero_path = 'D' * i + 'R' * j + (n - 1 - i) * 'D' + (n - 1 - j) * 'R'
        break
    except ValueError:
        continue
dp2 = [[100000000.0] * n for i in range(n)]
dp5 = [[100000000.0] * n for i in range(n)]
dp2[0][0] = dp5[0][0] = 0
if a[0][0]:
    while a[0][0] % 2 == 0:
        a[0][0] >>= 1
        dp2[0][0] += 1
    while a[0][0] % 5 == 0:
        a[0][0] //= 5
        dp5[0][0] += 1
else:
    dp2[0][0] = dp5[0][0] = 100000000.0
for i in range(n):
    for j in range(n):
        if a[i][j]:
            if i:
                dp2[i][j] = min(dp2[i][j], dp2[i - 1][j])
                dp5[i][j] = min(dp5[i][j], dp5[i - 1][j])
            if j:
                dp2[i][j] = min(dp2[i][j], dp2[i][j - 1])
                dp5[i][j] = min(dp5[i][j], dp5[i][j - 1])
            while a[i][j] % 2 == 0:
                a[i][j] >>= 1
                dp2[i][j] += 1
            while a[i][j] % 5 == 0:
                a[i][j] //= 5
                dp5[i][j] += 1
a = None
if dp2[n - 1][n - 1] < dp5[n - 1][n - 1]:
    a = dp2
else:
    a = dp5
if zero_path is None or a[n - 1][n - 1] == 0:
    path = []
    i = j = n - 1
    while i != 0 or j != 0:
        if i and j:
            if a[i - 1][j] < a[i][j - 1]:
                i = i - 1
                path.append('D')
            else:
                j = j - 1
                path.append('R')
        elif i:
            i = i - 1
            path.append('D')
        elif j:
            j = j - 1
            path.append('R')
    print(a[n - 1][n - 1])
    print(''.join(path[::-1]))
else:
    print(1)
    print(zero_path)

Solution (Python):
from functools import lru_cache
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import inf

def get25(k):
    if k == 0:
        return (inf, inf)
    (num2, num5) = (0, 0)
    while k % 2 == 0:
        k = k // 2
        num2 += 1
    while k % 5 == 0:
        k = k // 5
        num5 += 1
    return (num2, num5)

def main():
    n = int(input())
    g = list()
    for i in range(n):
        g.append(list(map(int, input().split(' '))))
    dp2 = [[0] * n for _ in range(n)]
    dp5 = [[0] * n for _ in range(n)]
    g5 = [[0] * n for _ in range(n)]
    flag = False
    idx = [-1, -1]
    for i in range(n):
        for j in range(n):
            if g[i][j] == 0:
                flag = True
                idx = [i, j]
            (num2, num5) = get25(g[i][j])
            g5[i][j] = num5
            g[i][j] = num2
    g2 = g
    dp2[0][0] = g2[0][0]
    dp5[0][0] = g5[0][0]
    for i in range(1, n):
        dp2[i][0] = dp2[i - 1][0] + g2[i][0]
        dp5[i][0] = dp5[i - 1][0] + g5[i][0]
    for j in range(1, n):
        dp2[0][j] = dp2[0][j - 1] + g2[0][j]
        dp5[0][j] = dp5[0][j - 1] + g5[0][j]
    for i in range(1, n):
        for j in range(1, n):
            dp2[i][j] = min(dp2[i - 1][j], dp2[i][j - 1]) + g2[i][j]
            dp5[i][j] = min(dp5[i - 1][j], dp5[i][j - 1]) + g5[i][j]
    if flag and dp2[n - 1][n - 1] >= 1 and (dp5[n - 1][n - 1] >= 1):
        print(1)
        res = 'D' * idx[0] + 'R' * idx[1] + 'D' * (n - 1 - idx[0]) + 'R' * (n - 1 - idx[1])
        print(res)
        return
    if dp2[n - 1][n - 1] < dp5[n - 1][n - 1]:
        print(dp2[n - 1][n - 1])
        res = list()
        (i, j) = (n - 1, n - 1)
        while i > 0 and j > 0:
            (num2, num5) = (g2[i][j], g5[i][j])
            if dp2[i - 1][j] + num2 == dp2[i][j]:
                res.append('D')
                i -= 1
            else:
                res.append('R')
                j -= 1
        while i > 0:
            res.append('D')
            i -= 1
        while j > 0:
            res.append('R')
            j -= 1
        print(''.join(res[::-1]))
    else:
        print(dp5[n - 1][n - 1])
        res = list()
        (i, j) = (n - 1, n - 1)
        while i > 0 and j > 0:
            (num2, num5) = (g2[i][j], g5[i][j])
            if dp5[i - 1][j] + num5 == dp5[i][j]:
                res.append('D')
                i -= 1
            else:
                res.append('R')
                j -= 1
        while i > 0:
            res.append('D')
            i -= 1
        while j > 0:
            res.append('R')
            j -= 1
        print(''.join(res[::-1]))
    return
main()