Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2319
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2319
Penalidade Mínima
Por OBI - Olimpíada Brasileira de Informática 2006 
Brazil
Timelimit: 1
A Sra. Bastos é uma elaboradora de passatempos matemáticos e pediu para que você criasse um programa que conseguisse jogar de forma eficiente a sua mais nova criação.
O jogo consiste em um tabuleiro formado por casas dispostas em N linhas por N colunas. Cada casa contém um inteiro não-negativo. No começo do jogo, uma peça é colocada na casa localizada no canto superior esquerdo, ou seja, na posição (1,1). O objetivo do jogo é mover a peça até a casa localizada no canto inferior direito (posição (N,N)) somente movendo um único quadrado para baixo ou para a direita em cada passo. Além disso, a peça não pode ser colocada em nenhum quadrado que contenha o número zero.
O custo do caminho utilizado para percorrer o tabuleiro corresponde ao produto de todos os números das casas percorridos no caminho. A penalidade é definida utilizando a representação decimal do custo, sendo representada pelo número de dígitos zeros, contados da direita para a esquerda, antes do primeiro dígito diferente de zero. Por exemplo, um custo igual a 501000 tem penalidade 3, e um custo igual a 501 tem penalidade zero.
O objetivo do jogo é conseguir chegar à casa (N,N) através de um caminho “otimizado”. Dizemos que o caminho foi otimizado se a penalidade for mínima.
Escreva um programa que, dado um tabuleiro, determine a penalidade do custo otimizado.
Entrada
A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém um inteiro N que indica o número de linhas e colunas do tabuleiro (1 ≤ N ≤ 1000). As N linhas seguintes contêm N inteiros I cada (1 ≤ I ≤ 1000000), que representam o valor da casa do tabuleiro naquela posição. Existe pelo menos uma solução possível para todos os casos de teste.
Saída
Seu programa deve imprimir, na saída padrão, uma única linha, contendo a penalidade do custo “otimizado”.
| Exemplos de Entrada | Exemplos de Saída |
|
3 |
0 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#define MAXN 1001
using namespace std;
const int INF = 1e7;
int m[MAXN][MAXN], processado2[MAXN][MAXN], processado5[MAXN][MAXN],
dp2[MAXN][MAXN], dp5[MAXN][MAXN], c2[MAXN][MAXN], c5[MAXN][MAXN], n;
int solve2(int x, int y) {
if (x > n || y > n) {
return INF;
}
if (processado2[x][y]) return dp2[x][y];
processado2[x][y] = 1;
if (m[x][y] == 0) return dp2[x][y] = INF;
if (x == n && y == n) {
return dp2[x][y] = c2[x][y];
}
return dp2[x][y] = c2[x][y] + min(solve2(x + 1, y), solve2(x, y + 1));
}
int solve5(int x, int y) {
if (x > n || y > n) {
return INF;
}
if (processado5[x][y]) return dp5[x][y];
processado5[x][y] = 1;
if (m[x][y] == 0) return dp5[x][y] = INF;
if (x == n && y == n) {
return dp5[x][y] = c5[x][y];
}
return dp5[x][y] = c5[x][y] + min(solve5(x + 1, y), solve5(x, y + 1));
}
int main() {
scanf("%d", &n);
for (int i = 1; i < = n; i++) {
for (int j = 1; j < = n; j++) {
scanf("%d", &m[i][j]);
if (m[i][j] == 0) continue;
int pot2 = 0, pot5 = 0;
while (m[i][j] % 2 == 0) m[i][j] /= 2, pot2++;
while (m[i][j] % 5 == 0) m[i][j] /= 5, pot5++;
c2[i][j] = pot2;
c5[i][j] = pot5;
}
}
printf("%d\n", min(solve2(1, 1), solve5(1, 1)));
return 0;
}
Input
1 2 3
4 5 6
7 8 9