http://adf.ly/joZ9p
http://www.spoj.com/problems/SAFECRAC/
We will solve this task using dynamic programming. Let us have an array A of size 100000x10 where A[i][j] shows the number of codes which have the length i and end with a digit j. Initially all the elemenets of A[1] are 1 because there are 10 codes of length 1 and each of them ends with a separate digit. Now we need build the next lines. We can tell what digits can come after any digit for example if the code which has a length of M ends in digit 1 that means we can make 2 times more codes of length M+1 where we will add the digits 2 and 4 (the neighbors of digit 1) and form new codes ending with digits 2 and 4. I also suggest keeping the sum of elements in every 10th element on every row so that we can make our code easier. Check the source code for a better understanding.
http://www.spoj.com/problems/SAFECRAC/
We will solve this task using dynamic programming. Let us have an array A of size 100000x10 where A[i][j] shows the number of codes which have the length i and end with a digit j. Initially all the elemenets of A[1] are 1 because there are 10 codes of length 1 and each of them ends with a separate digit. Now we need build the next lines. We can tell what digits can come after any digit for example if the code which has a length of M ends in digit 1 that means we can make 2 times more codes of length M+1 where we will add the digits 2 and 4 (the neighbors of digit 1) and form new codes ending with digits 2 and 4. I also suggest keeping the sum of elements in every 10th element on every row so that we can make our code easier. Check the source code for a better understanding.
No comments:
Post a Comment