SWEA 7673 - 영이는 영이 시져시져!

swea-7673.cpp

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long lld;

const int INF = 0x3f3f3f3f;

struct cell {
    int two, five;
    int zero() const {
        return min(two, five);
    }
    bool operator < (const cell& o) const {
        return zero() < o.zero();
    }
    cell operator + (const cell& o) {
        return {two + o.two, five + o.five};
    }
};

int a[1000][1000];
cell D[1000][1000];

// Count Trailing Zero
cell ctz(int k) {
    int two = 0, five = 0;
    for (int i = k; i % 2 == 0 && i > 0; i /= 2) two++;
    for (int i = k; i % 5 == 0 && i > 0; i /= 5) five++;
    return {two, five};
}

int solve() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            scanf("%d", &a[i][j]);
            D[i][j] = {0, 0};
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            D[i][j] = ctz(a[i][j]);
            if (i + j == 0 || a[i][j] == 0) continue;
            cell prev = {INF, INF};
            if (i > 0 && a[i - 1][j] != 0) prev = min(prev, D[i - 1][j]);
            if (j > 0 && a[i][j - 1] != 0) prev = min(prev, D[i][j - 1]);
            D[i][j] = D[i][j] + prev;
        }
    }
    return D[n - 1][n - 1].zero();
}

int main() {
    int T;
    scanf("%d", &T);
    for (int tc = 1; tc <= T; ++tc) {
        printf("#%d %d\n", tc, solve());
    }
    return 0;
}