|
|
back to boardcan someone tell about the math formula of this problem? Posted by breeze 5 Apr 2004 10:00 can everyone tell me a good method? Best method that I know. (DP, O( (Q - 1) * K * K) , Q = 10 without long arithmetics). Calculate amount of K-digits numbers with any possible sum of digits (S, S <= 9 * K) - A[K,S]. Amount of 2K-digits lucky tickets is equal to A[K,0] * A[K,0] + A[K,1] * A[K,1] + ... + A[K,9 * K] * A[K,9 * K]. If you can think a little then you can optimize this solution in 20 times and solve problem 1036 in 0.031 sec. Re: Best method that I know. (DP, O( (Q - 1) * K * K) , Q = 10 without long arithmetics). Posted by breeze 6 Apr 2004 08:20 Oh!thank so much! |
|
|