ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1513. Lemon Tale

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!?
Posted by KIRILL(ArcSTU) 17 Jan 2007 21:29
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!?
Posted by Roma Labish[Lviv NU] 17 Jan 2007 22:56
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!?
Posted by Todor Tsonkov 21 Feb 2007 01:16
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)