oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

leastround Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

leastround.html

In this problem, you will be given a square matrix of size N * N. Each cell in the grid will contain a non-negative number. Your task is to find a path on the square matrix such that

* The path starts in the upper-leftmost cell of the matrix;

* You can only move down one square or right one square;

* Your destination is the bottom-rightmost cell of the matrix.

Furthermore, the result we get when we multiply all the numbers only the way 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 path that results in the least-round number. At any instance, if the path goes downwards, print out 'D'. If the path goes rightwards, print out 'R'. If there exists multiple ways of making the least round number, output any valid path that gives a least-round number.

Sample Input

3
1 2 3
4 5 6
7 8 9

Sample Output

0
DDRR

Sample Explanation

The sequence of numbers traversed is "1-4-7-8-9". We notice that 1*4*7*8*9 = 2016, a number that does not end with any zeroes.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100201s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o leastround -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.