|
|
вернуться в форумI don't understaind the algo please i don't understaind . a[0]=1; a[1]=(k-1); a[i]=(k-1)*(a[i-1]+a[i-2]); for n=2 and k = 10 the answer is 90 allright,but ,from my point of view for n=2 and k = 9 the right answer is 99 ,2 digits number 9 based, but the algo show 72 , I've AC but, is this the right algo?. sorry but my english is too bad . Re: I don't understaind the algo Послано KIRILL 11 сен 2006 23:47 a[2] = k*k-k This is all numbers from 10 to 88 (if k = 9 and n = 2) Re: I don't understaind the algo not all, the number 19, 29, 39, 49 .. 79 is not allowed ! Re: I don't understaind the algo FireHeart: you don't have the digit '9' when k=9 Re: I don't understaind the algo that is a CLASSICAL math problem , i didnt realize it till i got 6 WAs. we fix the first number to be nonzero,and let f(n) be all the correct numbers . suppose the second digit is not zero ,we have f(n-1) correct ways. otherwise,we have f(n-2) ways. by addition law ,we have f(n)=(k-1)(f(n-1)+f(n-2)) . the idea is very classical and we should remember it all the time . Re: I don't understaind the algo It is a classical combinatorial problem. You can solve it with the elegant recurrent relation, but figuring it out how to do it yourself is more valuable. I did it using some combinatoric (i.e.: the number we seek is sum of the K-based numbers with N digits who have exactly X zeroes (i.e. K-X free digits from 1..K-1) and don't have adjacent zeroes (sometimes this is zero, when X > N-X). If f(N,K,X) is this number, we seek sum(X=0 to N-1) f(N,K,X) (we can lower the upper bound X-1 but there's no need if you compute f properly) Edited by author 22.07.2008 15:30 |
|
|