http://www.spoj.com/problems/NY10E/
This task can be solved eaither with math calculaions or with DP (dynamic programming). I will suggest a solution with DP. So we will keep an 2 dimensional array. A[I][J] will show the number of non-decreasing numbers of lenght I which starts with teh digit J. Initialy a[1][0],a[1][1],a[1][2].....a[1][9] are equal to 0. Now we need to count others. For the lenght 2 if the number starts with 0 then after it we can have any number which we made i a previous step . If the number starts with 1 that means that after that we can have all 1 digit numbers which start with a digit greater or equal to 1. The genertal formula will be like this
a[i][j]=a[i-1][j]+a[i-1][j+1]+.....+a[i-1][9]. And I also suggest to keep the sum of the row in the 10the element so that you can be able to output the answer just after reading teh input. Also check teh source code for a better understanding.
This task can be solved eaither with math calculaions or with DP (dynamic programming). I will suggest a solution with DP. So we will keep an 2 dimensional array. A[I][J] will show the number of non-decreasing numbers of lenght I which starts with teh digit J. Initialy a[1][0],a[1][1],a[1][2].....a[1][9] are equal to 0. Now we need to count others. For the lenght 2 if the number starts with 0 then after it we can have any number which we made i a previous step . If the number starts with 1 that means that after that we can have all 1 digit numbers which start with a digit greater or equal to 1. The genertal formula will be like this
a[i][j]=a[i-1][j]+a[i-1][j+1]+.....+a[i-1][9]. And I also suggest to keep the sum of the row in the 10the element so that you can be able to output the answer just after reading teh input. Also check teh source code for a better understanding.
thanks !
ReplyDeletethanks!
ReplyDelete