|
|
back to boardPlease help. Is my algo corect!? Posted by Lomir 17 Jan 2007 21:16 Is my algo correctm or it's defenetely wrong? Firstly, i count all possible changes 2^n. Then i withdraw changes which do not siunt the censor (by fixing k+1 not changed lemons). Later i fix k+2 (one banana and k+1 lemons) and count new unsiutable chages. res = 2^n; res = res - 2^(n-k-1); for (int i = 0; i <= k && i+k+1<n; ++i) { int t = n - k - 2; if (t<0) break; res = res - 2^t; } I've got WA9, so this is cause my algo or my implementation? :) P.S. Nothing to change, then n==k, also must be counted or not? Re: Please help. Is my algo corect!? This problem like a 1009 (k=2) Solution - dp try to find f[n] through previous values(f[n-1],f[n-2],..) Re: Please help. Is my algo corect!? And you must to use long arithmetics... Re: Please help. Is my algo corect!? Posted by Lomir 17 Jan 2007 23:43 Thant for clue. Now I got AC. Java's BigInteger and none need for long arithmetic. Mine first algo was wrong, it's need about 2 cicles with minus more to be correct. Re: Please help. Is my algo corect!? Can you say some clue about your DP, because mine gets TL on test 13, I use Java, btw. Re: Please help. Is my algo corect!? Posted by Shyrik 26 Sep 2007 19:42 F(n,1/0) i - position 1 - limon 0 - banana F(i,1) = sum(F(z,0)); F(i,0) = F(i-1,1)+F(i-1,0) |
|
|