The problem is from Codeforces: [submit your solution here]
The number of trailing zeros can be computed by checking the number of divisors (2 and 5) for all numbers. The minimal divisor number of 2 or 5 would be the number of trailing zeros.
This is because each positive integers (greater than zero) can be rewritten in the form of 
For each trailing zero, it is formed by 2 multiply by 5. We determine the number of 2 and 5, the minimal of which will be the number of trailing zero.
However, as input contains zero, which means there will be a path has the multiplication equal to zero, and that has ONE trailing zero. If there does exist a way from the left-top to the bottom-right that has trailing zeros more than one, then this exceptional case (one trailing zero) will be the solution (the requirement asks for the minimal trailing zeros)
To find the number of divisors for a integer, we can divide the number by the divisor continuously until it is no longer divisible.
1 2 3 4 5 6 7 8 | int get(int i, int n) { int c = 0; while ((i > 0) && ((i % n) == 0)) { c ++; i /= n; } return c; } |
int get(int i, int n) {
int c = 0;
while ((i > 0) && ((i % n) == 0)) {
c ++;
i /= n;
}
return c;
}Add i > 0 to avoid endless loop if given number is zero. Given a matrix num[i][j], we represent dp[i][j] for the number of divisors (e.g. 2 or 5) from the left-top coordinate (0, 0), we can easily get the dynamic programming relations:
dp[i][j] = min(dp[i – 1][j], dp[i][j – 1]) + get(num[i][j])
The final solution would be the located at dp[n – 1][n – 1] where n is the size of the input matrix.
We fill the first column and first row of the matrix dp and conduct the dynamic programming from the left-top to the right-bottom. The algorithm complexity is 
as easily observed.
Because we have to print the path, we record the path (from the right-bottom to left-top) in a separate matrix and print it in the reverse order.
We compare the number of minimal divisor for 2 and 5 finally.
The complete C++ source is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 | #include <iostream> using namespace std; int arr[1000][1000]; // for input matrix // dp array // the third dimension 0 = divisor of 2 // the third dimension 1 = divisor of 5 int a[1000][1000][2] = {9999999999}; // the third dimension 0 = direction of 2 // the third dimension 1 = direction of 5 char d[1000][1000][2] = {'\0'}; // get the number of divisor n int get(int i, int n) { int c = 0; while ((i > 0) && ((i % n) == 0)) { c ++; i /= n; } return c; } // print recursively in reverse order void print(int i, int j, int k) { if ((i >= 0) && (j >= 0)) { if (d[i][j][k] == 'D') { print(i - 1, j, k); } else { print(i, j - 1, k); } if (d[i][j][k] != '\0') { cout << d[i][j][k]; } } } int main() { int n; cin >> n; bool zero = false; int x, y; // check for zero for (int i = 0; i < n; i ++) { for (int j = 0; j < n; j ++) { cin >> arr[i][j]; if (arr[i][j] == 0) { zero = true; arr[i][j] = 10; // make it 10 x = i; y = j; } } } a[0][0][0] = get(arr[0][0], 2); a[0][0][1] = get(arr[0][0], 5); // first column and first row for (int i = 1; i < n; i ++) { a[i][0][0] += get(arr[i][0], 2) + a[i - 1][0][0]; a[i][0][1] += get(arr[i][0], 5) + a[i - 1][0][1]; a[0][i][0] += get(arr[0][i], 2) + a[0][i - 1][0]; a[0][i][1] += get(arr[0][i], 5) + a[0][i - 1][1]; d[i][0][0] = 'D'; d[i][0][1] = 'D'; d[0][i][0] = 'R'; d[0][i][1] = 'R'; } // dp for (int i = 1; i < n; i ++) { for (int j = 1; j < n; j ++) { int prev_two1 = a[i][j - 1][0]; int prev_five1 = a[i][j - 1][1]; int prev_two2 = a[i - 1][j][0]; int prev_five2 = a[i - 1][j][1]; int c2 = get(arr[i][j], 2); int c5 = get(arr[i][j], 5); prev_two1 += c2; prev_two2 += c2; prev_five1 += c5; prev_five2 += c5; if (prev_two1 < prev_two2) { a[i][j][0] = prev_two1; d[i][j][0] = 'R'; } else { a[i][j][0] = prev_two2; d[i][j][0] = 'D'; } if (prev_five1 < prev_five2) { a[i][j][1] = prev_five1; d[i][j][1] = 'R'; } else { a[i][j][1] = prev_five2; d[i][j][1] = 'D'; } } } int cost = min(a[n - 1][n - 1][0], a[n - 1][n - 1][1]); int k = 0; if (a[n - 1][n - 1][0] > a[n - 1][n - 1][1]) { k = 1; } if ((zero && (cost > 0))) { // there is a zero and it is the solution cout << 1 << endl; for (int k = 0; k < x; k ++) { cout << 'D'; } for (int k = 0; k < y; k ++) { cout << 'R'; } for (int k = 0; k < n - y - 1; k ++) { cout << 'R'; } for (int k = 0; k < n - x - 1; k ++) { cout << 'D'; } } else { cout << cost << endl; print(n - 1, n - 1, k); } return 0; } |
#include <iostream>
using namespace std;
int arr[1000][1000]; // for input matrix
// dp array
// the third dimension 0 = divisor of 2
// the third dimension 1 = divisor of 5
int a[1000][1000][2] = {9999999999};
// the third dimension 0 = direction of 2
// the third dimension 1 = direction of 5
char d[1000][1000][2] = {'\0'};
// get the number of divisor n
int get(int i, int n) {
int c = 0;
while ((i > 0) && ((i % n) == 0)) {
c ++;
i /= n;
}
return c;
}
// print recursively in reverse order
void print(int i, int j, int k) {
if ((i >= 0) && (j >= 0)) {
if (d[i][j][k] == 'D') {
print(i - 1, j, k);
} else {
print(i, j - 1, k);
}
if (d[i][j][k] != '\0') {
cout << d[i][j][k];
}
}
}
int main() {
int n;
cin >> n;
bool zero = false;
int x, y;
// check for zero
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
cin >> arr[i][j];
if (arr[i][j] == 0) {
zero = true;
arr[i][j] = 10; // make it 10
x = i;
y = j;
}
}
}
a[0][0][0] = get(arr[0][0], 2);
a[0][0][1] = get(arr[0][0], 5);
// first column and first row
for (int i = 1; i < n; i ++) {
a[i][0][0] += get(arr[i][0], 2) + a[i - 1][0][0];
a[i][0][1] += get(arr[i][0], 5) + a[i - 1][0][1];
a[0][i][0] += get(arr[0][i], 2) + a[0][i - 1][0];
a[0][i][1] += get(arr[0][i], 5) + a[0][i - 1][1];
d[i][0][0] = 'D';
d[i][0][1] = 'D';
d[0][i][0] = 'R';
d[0][i][1] = 'R';
}
// dp
for (int i = 1; i < n; i ++) {
for (int j = 1; j < n; j ++) {
int prev_two1 = a[i][j - 1][0];
int prev_five1 = a[i][j - 1][1];
int prev_two2 = a[i - 1][j][0];
int prev_five2 = a[i - 1][j][1];
int c2 = get(arr[i][j], 2);
int c5 = get(arr[i][j], 5);
prev_two1 += c2;
prev_two2 += c2;
prev_five1 += c5;
prev_five2 += c5;
if (prev_two1 < prev_two2) {
a[i][j][0] = prev_two1;
d[i][j][0] = 'R';
} else {
a[i][j][0] = prev_two2;
d[i][j][0] = 'D';
}
if (prev_five1 < prev_five2) {
a[i][j][1] = prev_five1;
d[i][j][1] = 'R';
} else {
a[i][j][1] = prev_five2;
d[i][j][1] = 'D';
}
}
}
int cost = min(a[n - 1][n - 1][0], a[n - 1][n - 1][1]);
int k = 0;
if (a[n - 1][n - 1][0] > a[n - 1][n - 1][1]) {
k = 1;
}
if ((zero && (cost > 0))) { // there is a zero and it is the solution
cout << 1 << endl;
for (int k = 0; k < x; k ++) {
cout << 'D';
}
for (int k = 0; k < y; k ++) {
cout << 'R';
}
for (int k = 0; k < n - y - 1; k ++) {
cout << 'R';
}
for (int k = 0; k < n - x - 1; k ++) {
cout << 'D';
}
}
else {
cout << cost << endl;
print(n - 1, n - 1, k);
}
return 0;
}–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Draw a Chess Board using LOGO (Turtle Graphics)
Next Post: Coding Exercise - C++ - Timus - 1787. Turn for MEGA - Online Judge