Discussion @ 1044. Lucky Tickets. Easy! @ Timus Online Judge

can 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).

Posted by Vlad Veselov 5 Apr 2004 22:22

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!

Discussion of Problem 1044. Lucky Tickets. Easy!