Please 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)