Блог пользователя rr459595

Автор rr459595, история, 6 лет назад, По-английски

Here is the link to the problem:- http://codeforces.net/problemset/problem/2/B

If we have input matrix(2 rows and 3 columns) as:-

2 3

3 4 5

5 1 5

If we take 1-indexing, then at cell (2,2), we have 2 choices to get 0 number of trailing zeroes. One is (3*4*1) or (3*5*1). But we if we take (3*4*1)=12, then at the end cell (2,3), minimum number of trailing zeroes will be 1(by path 3-4-1-5). If we take 15 at cell 2, minimum number of trailing zeroes at the end will be 0 by path (3-5-1-5).

How to decide which number should I pick at cell (2,2) so that it doesn't affect the future cell (2,3)?

Thanks.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

By prime factorization we know we have to reach min(M_2, M_5) (when M_x represent result of a DP matrix for minimizing x in prime factorization of final multiplied number)

Build two matrix for calculating M_2 and M_5, then just print minimum of them.